449,402 Members | 1,099 Online
Need help? Post your question and get tips & solutions from a community of 449,402 IT Pros & Developers. It's quick & easy.

# Priority queue help

 P: n/a 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 '07 #1
4 Replies

 P: n/a jj*****@gmail.com wrote: [homework problem redacted] You're in luck!!! That very question was asked an answered here: http://www.parashift.com/c++-faq-lit...t.html#faq-5.2 In other words... DO YOUR OWN HOMEWORK!!! Oct 18 '07 #2

 P: n/a On 2007-10-18 23:09, jj*****@gmail.com wrote: This is a programming assignment. can anyone help me out? Sure, where is your code and what is your problem with it? You might also be interested in FAQ items 5.2 and 5.8: http://www.coders2020.com/cplusplus-...t.html#faq-5.2 http://www.coders2020.com/cplusplus-...t.html#faq-5.8 -- Erik WikstrĂ¶m Oct 18 '07 #3

 P: n/a jj*****@gmail.com 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). Oct 18 '07 #4

 P: n/a 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 using std::cout; #include #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 '07 #5

### This discussion thread is closed

Replies have been disabled for this discussion.