HP Integrity NonStop H-Series - Manual (Page 110)

Click on the banner to return to the user guide home page.
©Copyright 1996 Rogue Wave Software
Overview
Most people have a good intuitive understanding of the stack and queue data abstractions,
based on experience with everyday objects. An excellent example of a stack is a pile of papers
on a desk, or a stack of dishes in a cupboard. In both cases the important characteristic is that it
is the item on the top that is most easily accessed. The easiest way to add a new item to the
collection is to place it above all the current items in the stack. In this manner, an item removed
from a stack is the item that has been most recently inserted into the stack; for example, the top
piece of paper in the pile, or the top dish in the stack.
LIFO and FIFO
An everyday example of a queue, on the other hand, is a bank teller line, or a line of people
waiting to enter a theater. Here new additions are made to the back of the queue, as new people
enter the line, while items are removed from the front of the structure, as patrons enter the
theater. The removal order for a queue is the opposite of that for a stack. In a queue, the item
that is removed is the element that has been present in the queue for the longest period of time.
In the standard library, both stacks and queues are adaptors, built on top of other containers
which are used to actually hold the values. A
stack can be built out of either a vector or a deque ,
while a queue can be built on top of either a list or a deque. Elements held by either a stack or
queue must recognize both the operators < and ==.
Because neither stacks nor queues define iterators, it is not possible to examine the elements of
the collection except by removing the values one by one. The fact that these structures do not
implement iterators also implies that most of the generic algorithms described in Sections 12
and 13 cannot be used with either data structure.