6 Queues A simple linkedlist implementation of a Queue is liable to have poor performance time for Enqueue(). It will be necessary to scan the list each time in order to find the end. This will cause O(n) performance. Therefore, two pointers are kept to the list, a pointer to the front and a pointer to the rear. Unlike Pop() for Stack, Dequeue() does not return void, it returns (a copy of) the front Element. As with Stack, the storage requirements are O(n) for the array and list implementations of Queue. The list implementation requires storage for the pointers in addition to storage for the data. 6.1 List Implementation of Queue The list implementation of Queue is very similar to that for Stack. The major difference is that a pointer is maintained to the "rear" of the queue to make the Enqueue operation efficient (namely O(1)).The Queue Node class
template <class T> class Queue; // forward declaration of Queue
template <class Etype>
class Node
{
protected:
Etype Element;
Node *Next;
Node( Etype E = 0, Node *N = NULL )
: Element( E ), Next( N ) {}
friend class Queue;
};
The Queue class
Private members are index to first and last entries in the queue
template <class Element_Type>
class Queue
{
private:
// The queue is a linked list with no header.
Node<Element_Type> *Queue-Front;
Node<Element_Type> *Queue-Rear;
public:
Queue( ) : Queue_Front ( NULL ), Queue_Rear (NULL) {}
Queue( Queue & Value );
~Queue( );
const Queue & operator = ( const Queue & Value );
void Enqueue( const Element_Type & X );
Element_Type Dequeue( );
int Is_Empty( ) const
{ return Queue_Front == NULL; }
};
Dequeue -- remove the "front" element from the queue
template <class T>
T Queue<T>::Dequeue()
{
if (Queue_Front == NULL)
{
Error("Attempt to dequeue an empty queue");
return ???;
}
T element = Queue_Front>Element;
Node<T> * P = Q_Front;
Queue->Front = Q_Front>Next;
delete P;
if (!Queue_Front) // list has become empty
Queue_Rear = NULL;
return element;
}
Enqueue --- add an element to the end of the queue
template <class T>
static const Default_Size = 100;
template <class Element_Type>
public:
};
Incrementing the cursors (indices) in a Queue is done by modular arithmetic.
template <class Element_Type>
Enqueue --- add an element to the end of the queue (array version)
template <class Element_Type> ;
7 Stack and Queue and Tree Traversals
Depthfirst and Breadthfirst traversals of trees can be related
Breadthfirst uses a queue
Queue<Tree_Node> q;
q.Enqueue(Root);
while (!q.Is_Empty())
Depthfirst uses a stack
Stack<Tree_Node> s;
s.Push(Root);
while (!s.Is-Empty())
void Queue<T>::Enqueue(const T & element)
{
if (Queue_Front == NULL) // initially empty queue
{
Queue_Front = new Node<T>(element, NULL);
Queue_Rear = Queue_Front;
}
else
{
// build queue to the right
Queue_Rear>Next = new Node
Queue_Rear = Queue_Rear>Next;
}
}
6.2 Array Implementation of Queue
In the array implementation, cursors (indices) are kept to the front and
rear of the Queue. The values of Full_Queue and Q_Size are used to
determine when the Queue is full.
Unlike the list implementation, the array implementation can
overflow (the Queue can become full).
An empty Queue is characterized by Q_Size==0
A full Queue is characterized by Q_Size==Full_Queue
A Queue is constructed with ¨
Q_Front==1, Q_Rear==0, and Q_Size==0
Incrementing the cursors (indices) in a Queue is done by modular arithmetic.
The Array implementation of the Queue
The cursors "wraparound" the end of the array.
class Queue
{
private:
unsigned int Full_Queue; // max size of the queue
int Q_Front;
int Q_Rear;
int Q_Size;
Element_Type *Q_Array;
void Increment( int & X );
Queue( unsigned int Max_Size = Default_Size );
Queue( const Queue & Value );
~Queue( )
{ delete [ ] Q_Array; }
const Queue & operator = ( const Queue & Value );
void Enqueue( const Element_Type & X );
Element_Type Dequeue( );
void Make-Empty( );
int Is_Empty( ) const { return Q_Size == 0; }
int Is_Full( ) const { return Q_Size == Full_Queue; }
The cursors "wraparound" the end of the array.
void Queue<Element_Type>:: Increment( int & X )
{
if( ++X == Full_Queue )
X = 0;
}
void Queue<Element_Type>:: Enqueue( const Element_Type & X )
{
if( Is_Full( ) )
Error( ''Queue is full'' );
else
{
Q_Size++;
Increment( Q_Rear );
Q_Array[ Q_Rear ] = X;
}
}
to stack and queue operations.
Tree_Node node;
{
node = q.Dequeue();
Visit(node);
for (each child of node)
q.Enqueue(child);
}
Tree_Node node;
{
node = s.Top();
s.Pop();
Visit(node);
for (each child of node)
s.Push(child);
}
Figure below shows a general tree. The contents of the queue and stack are
as shown below. The traversal order, in each case, is given by the left
hand column.
Queue Stack
A A B C D D C B C D E F J I C B D E F G H I I C B E F G H I J C B F G H I J H G B G H I J G B H I J B I J F E J E