Java Reference
In-Depth Information
/
**
QueueADT
*
/
publicinterfaceQueue<E>{
/
**
Reinitializethequeue.Theuserisresponsiblefor
reclaimingthestorageusedbythequeueelements.
*
/
publicvoidclear();
/
**
Placeanelementattherearofthequeue.
@paramitTheelementbeingenqueued.
*
/
publicvoidenqueue(Eit);
/
**
Removeandreturnelementatthefrontofthequeue.
@returnTheelementatthefrontofthequeue.
*
/
publicEdequeue();
/
**
@returnThefrontelement.
*
/
publicEfrontValue();
/
**
@returnThenumberofelementsinthequeue.
*
/
publicintlength();
}
Figure4.24
The Java ADT for a queue.
Recursive algorithms lend themselves to efficient implementation with a stack
when the amount of information needed to describe a sub-problem is small. For
example, Section 7.5 discusses a stack-based implementation for Quicksort.
4.3
Queues
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 oper-
ate like standing in line at a movie theater ticket counter.
1
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. 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.” Figure 4.24 shows a sample
queue ADT. This section presents two implementations for queues: the array-based
queue and the linked queue.
4.3.1
Array-Based Queues
The array-based queue is somewhat tricky to implement effectively. A simple con-
version of the array-based list implementation is not efficient.
1
In Britain, a line of people is called a “queue,” and getting into line to wait for service is called
“queuing up.”
