In addition to vector and list,
the Standard Template Library (STL) provides several other containers.
In this lab exercise, we look at two related ones:
stack and queue.
Like vector and list, the stack and
queue containers store sequences of values. Also, they are
class templates so we can have a stack<int> of
ints, a stack<double>
of doubles; in fact, a stack<T> of
any type T elements; and similarly,
a queue<int> of ints,
a queue<double> of doubles,
..., a queue<>T
of any type T elements.
As you might expect, we find these class templates in the
stack and queue libraries, respectively.
We've already seen vector and list in action.
So how are stack and queue different? The
difference is in the operations that may be performed on them.
stack Containerstack container:
stack() constructor builds a new empty stack.empty() method returns true if the stack
is empty, false otherwise.top() method returns the element on the top of
the stack.push(item) method adds
item to the top of the stack.pop() method removes the element at the top of the
stack.A stack is also known as a LIFO container — Last In, First Out. The last item you push onto a stack will be the first one out.
Here are some examples of stacks from everyday life — you can probably think of others: a stack of cards in a "draw pile" of a card game; a stack of bricks; a stack of plates in a "pop-up" container in a serving line. You can (or should) access only the top of the stack. To access any element other than the top, we have to remove the items above it, beginning with the top.
queuequeue is known as the front of
the queue and the other end is known as the
back and all of the operations that modify the
queue are performed at one of the ends. Here are the operations
provided for STL's queues container:
queue() constructor constructs a new empty queue.empty() method returns true if the
queue is empty, false otherwise.front() method returns the element at the front
of the queue.back() method returns the element at the back of
the queue.push(item) method adds item to the back of the queue.pop() method removes the element at the front of the
queue.A queue is sometimes known as a FIFO container — First In, First Out. The first item added to a queue will be the first one out.
You've likely had experiences with queues — e.g., waiting in line to purchase tickets for a sporting event, concert, and so on. (It's been estimated that the average American spends five years of their life waiting in line.) Such a line is (usually) a queue — you enter the line at the back and you wait until you reach the front of the line to be served. You're not allowed to enter the line in the front or in the middle — no cuts! — and you won't be served if you leave before you reach the front of the line. All the rules you know about such waiting lines apply to queues; in particular, enter at the back, leave at the front.
The methods provided by these two container classes are quite
similar. The main difference is in the pop() operation. The
push() operation always adds an item to the container.
However, a stack's pop() removes and returns
the most recently pushed element while a queue's pop()
removes and returns the oldest.
This lab exercise has two experiments, one using a stack, the
other a queue.
Experiment #1: Working with a stack.
Experiment #2: Working with a queue.
Stacks and queues are used to store values and order them in their own special ways. Both have their uses, and a basic computer couldn't operate at all without both of them.
Question #15.1: What input, when fed into your two programs, will generate the same output?
You must feed the programs some input, and it must contain at least two different words.
The situation will be quite rare, which suggests just how different is the power of these two containers, even though they're different in only one operation!