Templates 70319
A stack is a LIFO(last in, first out) structure. The classic analogy for a stack is this: A
stack is like a stack of dishes at a salad bar. You add to the stack by placing a dish on top
(pushing the stack down), and you take from the stack by “popping” the top dish (the
one most recently added to the stack) off the top.
By convention, the open end of a stack is often called the topof the stack, and operations
carried out to a stack are often called pushand pop. The stackclass inherits these con-
ventional terms.The STL stackclass is not the same as the stack mechanism used by compil-
ers and operating systems, in which stacks can contain different types of
objects. The underlying functionality, however, is very similar.NOTE
The Deque Container
A deque is like a double-ended vector—it inherits the vectorcontainer class’s efficiency
in sequential read and write operations. But, in addition, the dequecontainer class pro-
vides optimized front-end and back-end operations. These operations are implemented
similarly to the listcontainer class, where memory allocations are engaged only for
new elements. This feature of the dequeclass eliminates the need to reallocate the whole
container to a new memory location, as the vectorclass has to do. Therefore, deques are
ideally suited for applications in which insertions and deletions take place at either one
or both ends, and for which sequential access of elements is important. An example of
such an application is a train-assembly simulator, in which carriages can join the train at
both ends.The Queues Container
A queueis another commonly used data structure in computer programming. Elements
are added to the queue at one end and taken out at the other.
A queue is like a line at the theater. You enter the queue at the back, and you leave the
queue at the front. This is known as a FIFO(first in, first out) structure; a stack is a
LIFO(last in, first out) structure. Of course, every once in a while, you’re second-to-last
in a long line at the supermarket when someone opens a new register and grabs the last
person in line—turning what should be a FIFO queue into a LIFO stack, and making you
grind your teeth in frustration.
Like the stack, the queueis implemented as a wrapper class to a container. The con-
tainer must support front(),back(),push_back(), and pop_front()operations.