Priority queue help

[jjh5030]

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?

 

[red floyd]

[homework problem redacted]

You're in luck!!! That very question was asked an answered here:

http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.2

In other words... DO YOUR OWN HOMEWORK!!!

 

[Guest]

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-explained/how-to-post.html#faq-5.2
http://www.coders2020.com/cplusplus-explained/how-to-post.html#faq-5.8

 

[Andre Kostur]

(e-mail address removed) wrote in @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).

 

[jjh5030]

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 >:rint() 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