Like the stack, the queue is a list-like structure that
provides restricted access to its elements.
Queue elements may only be inserted at the back (called an
enqueue operation) and removed from the
front (called a dequeue operation).
Queues operate like standing in line at a movie theater ticket
counter.
If nobody cheats, then newcomers go to the back of the line.
The person at the front of the line is the next to be served.
Thus, queues release their elements in order of arrival.
In Britain, a line of people is called a “queue”,
and getting into line to wait for service is called “queuing up”.
Accountants have used queues since long before the
existence of computers.
They call a queue a “FIFO” list, which stands for
“First-In, First-Out”.
Here is a sample queue ADT.
This section presents two implementations for queues:
the array-based queue and the linked queue.
publicinterfaceQueue{// Queue class ADT// Reinitialize queuepublicvoidclear();// Put element on rearpublicbooleanenqueue(Objectit);// Remove and return element from frontpublicObjectdequeue();// Return front elementpublicObjectfrontValue();// Return queue sizepublicintlength();// Return true if the queue is emptypublicbooleanisEmpty();}
publicinterfaceQueue<E>{// Queue class ADT// Reinitialize queuepublicvoidclear();// Put element on rearpublicbooleanenqueue(Eit);// Remove and return element from frontpublicEdequeue();// Return front elementpublicEfrontValue();// Return queue sizepublicintlength();//Tell if the queue is empty or notpublicbooleanisEmpty();}
Assume that there are n elements in the queue. By analogy to the array-based list implementation, we could require that all elements of the queue be stored in the first $n$ positions of the array.
A more efficient implementation can be obtained by relaxing the requirement that all elements of the queue must be in the first $n$ positions of the array. We still require that the queue be stored be in contiguous array positions, but the contents of the queue will be permitted to drift within the array.
The "drifting queue" problem can be solved by pretending that the array is circular and so allow the queue to continue directly from the highest-numbered position in the array to the lowest-numbered position.
If the value of front is fixed, then n+1 different
values for rear are needed to distinguish among the n+1
states.
However, there are only n possible values for rear unless
we invent a special case for, say, empty queues.
This is an example of the Pigeonhole Principle.
The Pigeonhole Principle states that, given n pigeonholes
and n+1 pigeons, when all of the pigeons go into the holes we
can be sure that at least one hole contains more than one pigeon.
In similar manner, we can be sure that two of the n+1 states
are indistinguishable by the n relative values of front
and rear.
We must seek some other way to distinguish full from empty queues.
One obvious solution is to keep an explicit count of the number of
elements in the queue, or at least a Boolean variable that indicates
whether the queue is empty or not.
Another solution is to make the array be of size n+1,
and only allow n elements to be stored.
Which of these solutions to adopt is purely a matter of the
implementor’s taste in such affairs.
Our choice here is to use an array of size n+1.
classAQueueimplementsQueue{privateObjectqueueArray[];// Array holding queue elementsprivatestaticfinalintDEFAULT_SIZE=10;privateintmaxSize;// Maximum size of queueprivateintfront;// Index of front elementprivateintrear;// Index of rear element// ConstructorsAQueue(intsize){maxSize=size+1;// One extra space is allocatedrear=0;front=1;queueArray=newObject[maxSize];// Create queueArray}AQueue(){this(DEFAULT_SIZE);}// Reinitializepublicvoidclear(){rear=0;front=1;}// Put "it" in queuepublicbooleanenqueue(Objectit){if(((rear+2)%maxSize)==front)returnfalse;// Fullrear=(rear+1)%maxSize;// Circular incrementqueueArray[rear]=it;returntrue;}// Remove and return front valuepublicObjectdequeue(){if(length()==0)returnnull;Objectit=queueArray[front];front=(front+1)%maxSize;// Circular incrementreturnit;}// Return front valuepublicObjectfrontValue(){if(length()==0)returnnull;returnqueueArray[front];}// Return queue sizepublicintlength(){return((rear+maxSize)-front+1)%maxSize;}// Check if the queue is emptypublicbooleanisEmpty(){returnfront-rear==1;}}
classAQueue<E>implementsQueue<E>{privateEqueueArray[];// Array holding queue elementsprivatestaticfinalintDEFAULT_SIZE=10;privateintmaxSize;// Maximum size of queueprivateintfront;// Index of front elementprivateintrear;// Index of rear element// Constructors@SuppressWarnings("unchecked")// Generic array allocationAQueue(intsize){maxSize=size+1;// One extra space is allocatedrear=0;front=1;queueArray=(E[])newObject[maxSize];// Create queueArray}AQueue(){this(DEFAULT_SIZE);}// Reinitializepublicvoidclear(){rear=0;front=1;}// Put "it" in queuepublicbooleanenqueue(Eit){if(((rear+2)%maxSize)==front){returnfalse;// Full}rear=(rear+1)%maxSize;// Circular incrementqueueArray[rear]=it;returntrue;}// Remove and return front valuepublicEdequeue(){if(length()==0){returnnull;}Eit=queueArray[front];front=(front+1)%maxSize;// Circular incrementreturnit;}// Return front valuepublicEfrontValue(){if(length()==0){returnnull;}returnqueueArray[front];}// Return queue sizepublicintlength(){return((rear+maxSize)-front+1)%maxSize;}//Tell if the queue is empty or notpublicbooleanisEmpty(){returnfront-rear==1;}}
In this implementation, the front of the queue is defined to be toward
the lower numbered positions in the array (in the counter-clockwise
direction in the circular array), and the rear is
defined to be toward the higher-numbered positions.
Thus, enqueue increments the rear pointer (modulus maxSize),
and dequeue increments the front pointer.
Implementation of all member functions is straightforward.
