Priority queue help

Discussion in 'C++' started by jjh5030@gmail.com, Oct 18, 2007.

  1. Guest

    This is a programming assignment. You are asked to work with pointers.
    Be aware that error messages are often not very helpful when your
    pointers
    point to bad locations. Therefore, reserve additional time for
    debugging.
    Implement a data structure Extended Queue using pointers. In addition
    to the usual queue operations Enqueue(x), Dequeue and the trivial
    operations
    Make-empty-queue and the Is-empty test, you are asked to have
    two nonstandard operations.
    · High-priority-enqueue(x) enqueues x at the front of the queue.
    · Medium-priority-enqueue(x) enqueues x in the middle. If the sequence
    has odd length, then x is enqueued just before the middle.
    The elements x of the Extended Queue are integers.
    Pointers are often used for fast algorithms. We use pointers here,
    because
    we require that each of the Extended Queue operations is done in
    (worst
    case) time O(1).
    (a) Describe how you achieve time O(1) for the operation Medium-
    priorityenqueue(
    x).
    (b) Write a program implementing Extended Queue as follows. It starts
    building an empty Extended Queue. Then it reads standard input
    without any prompts until it reaches end-of-file. The input is a
    sequence
    of commands (one command per line) of the form:
    · e x (for Enqueue(x))
    · h x (for High-priority-enqueue(x))
    · m x (for Medium-priority-enqueue(x))
    · d (for Dequeue)
    After reading any command, that command is executed in time O(1).
    On Dequeue, the dequeued element is output. When eof is reached in
    the input, then start a new line and do Dequeue until the Extended
    Queue is empty.
    (c) Run your program on the Command File below

    e 1
    h 2
    m 3
    m 4
    m 5
    d
    h 6
    d
    d
    d
    m 7
    h 8
    h 9
    m 10
    d
    d
    m 11
    e 12
    e 13
    m 14

    can anyone help me out?
    , Oct 18, 2007
    #1
    1. Advertising

  2. red floyd Guest

    red floyd, Oct 18, 2007
    #2
    1. Advertising

  3. =?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=, Oct 18, 2007
    #3
  4. Andre Kostur Guest

    wrote in news:1192741792.546333.67490
    @v23g2000prn.googlegroups.com:

    > This is a programming assignment. You are asked to work with pointers.


    At least you're honest up front.

    [snip homework assignment]

    We're not going to do it for you. You have to try it yourself. When you
    have specific C++ questions (and "How do I do this assignment in C++" isn't
    specific).
    Andre Kostur, Oct 18, 2007
    #4
  5. Guest

    I so far have implemented everything using a linked list, Now I just
    need help making the medium priority queue.

    #ifndef LISTNODE_H
    #define LISTNODE_H

    // forward declaration of class List required to announce that class
    // List exists so it can be used in the friend declaration at line 13
    template< typename NODETYPE > class List;

    template< typename NODETYPE >
    class ListNode
    {
    friend class List< NODETYPE >; // make List a friend

    public:
    ListNode( const NODETYPE & ); // constructor
    NODETYPE getData() const; // return data in node
    private:
    NODETYPE data; // data
    ListNode< NODETYPE > *nextPtr; // next node in list
    }; // end class ListNode

    // constructor
    template< typename NODETYPE >
    ListNode< NODETYPE >::ListNode( const NODETYPE &info )
    : data( info ), nextPtr( 0 )
    {
    // empty body
    } // end ListNode constructor

    // return copy of data in node
    template< typename NODETYPE >
    NODETYPE ListNode< NODETYPE >::getData() const
    {
    return data;
    } // end function getData

    #endif

    ---------------------------------------------------------------------

    #ifndef LIST_H
    #define LIST_H

    #include <iostream>
    using std::cout;

    #include <new>
    #include "Listnode.h" // ListNode class definition

    template< typename NODETYPE >
    class List
    {
    public:
    List(); // constructor
    ~List(); // destructor
    void insertAtFront( const NODETYPE & );
    void insertAtBack( const NODETYPE & );
    bool removeFromFront( NODETYPE & );
    bool removeFromBack( NODETYPE & );
    bool isEmpty() const;
    void print() const;
    private:
    ListNode< NODETYPE > *firstPtr; // pointer to first node
    ListNode< NODETYPE > *lastPtr; // pointer to last node

    // utility function to allocate new node
    ListNode< NODETYPE > *getNewNode( const NODETYPE & );
    }; // end class List

    // default constructor
    template< typename NODETYPE >
    List< NODETYPE >::List()
    : firstPtr( 0 ), lastPtr( 0 )
    {
    // empty body
    } // end List constructor

    // destructor
    template< typename NODETYPE >
    List< NODETYPE >::~List()
    {
    if ( !isEmpty() ) // List is not empty
    {
    cout << "Destroying nodes ...\n";

    ListNode< NODETYPE > *currentPtr = firstPtr;
    ListNode< NODETYPE > *tempPtr;

    while ( currentPtr != 0 ) // delete remaining nodes
    {
    tempPtr = currentPtr;
    cout << tempPtr->data << '\n';
    currentPtr = currentPtr->nextPtr;
    delete tempPtr;
    } // end while
    } // end if

    cout << "All nodes destroyed\n\n";
    } // end List destructor

    // insert node at front of list
    template< typename NODETYPE >
    void List< NODETYPE >::insertAtFront( const NODETYPE &value )
    {
    ListNode< NODETYPE > *newPtr = getNewNode( value ); // new node

    if ( isEmpty() ) // List is empty
    firstPtr = lastPtr = newPtr; // new list has only one node
    else // List is not empty
    {
    newPtr->nextPtr = firstPtr; // point new node to previous 1st
    node
    firstPtr = newPtr; // aim firstPtr at new node
    } // end else
    } // end function insertAtFront

    // insert node at back of list
    template< typename NODETYPE >
    void List< NODETYPE >::insertAtBack( const NODETYPE &value )
    {
    ListNode< NODETYPE > *newPtr = getNewNode( value ); // new node

    if ( isEmpty() ) // List is empty
    firstPtr = lastPtr = newPtr; // new list has only one node
    else // List is not empty
    {
    lastPtr->nextPtr = newPtr; // update previous last node
    lastPtr = newPtr; // new last node
    } // end else
    } // end function insertAtBack

    // delete node from front of list
    template< typename NODETYPE >
    bool List< NODETYPE >::removeFromFront( NODETYPE &value )
    {
    if ( isEmpty() ) // List is empty
    return false; // delete unsuccessful
    else
    {
    ListNode< NODETYPE > *tempPtr = firstPtr; // hold tempPtr to
    delete

    if ( firstPtr == lastPtr )
    firstPtr = lastPtr = 0; // no nodes remain after removal
    else
    firstPtr = firstPtr->nextPtr; // point to previous 2nd node

    value = tempPtr->data; // return data being removed
    delete tempPtr; // reclaim previous front node
    return true; // delete successful
    } // end else
    } // end function removeFromFront

    // delete node from back of list
    template< typename NODETYPE >
    bool List< NODETYPE >::removeFromBack( NODETYPE &value )
    {
    if ( isEmpty() ) // List is empty
    return false; // delete unsuccessful
    else
    {
    ListNode< NODETYPE > *tempPtr = lastPtr; // hold tempPtr to
    delete

    if ( firstPtr == lastPtr ) // List has one element
    firstPtr = lastPtr = 0; // no nodes remain after removal
    else
    {
    ListNode< NODETYPE > *currentPtr = firstPtr;

    // locate second-to-last element
    while ( currentPtr->nextPtr != lastPtr )
    currentPtr = currentPtr->nextPtr; // move to next node

    lastPtr = currentPtr; // remove last node
    currentPtr->nextPtr = 0; // this is now the last node
    } // end else

    value = tempPtr->data; // return value from old last node
    delete tempPtr; // reclaim former last node
    return true; // delete successful
    } // end else
    } // end function removeFromBack

    // is List empty?
    template< typename NODETYPE >
    bool List< NODETYPE >::isEmpty() const
    {
    return firstPtr == 0;
    } // end function isEmpty

    // return pointer to newly allocated node
    template< typename NODETYPE >
    ListNode< NODETYPE > *List< NODETYPE >::getNewNode(
    const NODETYPE &value )
    {
    return new ListNode< NODETYPE >( value );
    } // end function getNewNode

    // display contents of List
    template< typename NODETYPE >
    void List< NODETYPE >::print() const
    {
    if ( isEmpty() ) // List is empty
    {
    cout << "The list is empty\n\n";
    return;
    } // end if

    ListNode< NODETYPE > *currentPtr = firstPtr;

    cout << "The list is: ";

    while ( currentPtr != 0 ) // get element data
    {
    cout << currentPtr->data << ' ';
    currentPtr = currentPtr->nextPtr;
    } // end while

    cout << "\n\n";
    } // end function print

    #endif
    , Oct 20, 2007
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Navhpf

    priority queue

    Navhpf, Feb 23, 2004, in forum: Java
    Replies:
    3
    Views:
    995
    Navhpf
    Feb 23, 2004
  2. Aaron W. LaFramboise

    Stable priority queue

    Aaron W. LaFramboise, Apr 5, 2004, in forum: C++
    Replies:
    19
    Views:
    1,541
    Claudio Puviani
    Apr 7, 2004
  3. Russell Warren

    Is Queue.Queue.queue.clear() thread-safe?

    Russell Warren, Jun 22, 2006, in forum: Python
    Replies:
    4
    Views:
    680
    Russell Warren
    Jun 27, 2006
  4. Marcel Müller
    Replies:
    3
    Views:
    559
    Marcel Müller
    Apr 27, 2009
  5. Kris
    Replies:
    0
    Views:
    479
Loading...

Share This Page