In addition to
the Standard Template Library (STL) provides several other containers.
In this lab exercise, we look at two related ones:
queue containers store sequences of values. Also, they are
class templates so we can have a
doubles; in fact, a
T elements; and similarly,
of any type
As you might expect, we find these class templates in the
queue libraries, respectively.
We've already seen
list in action.
So how are
queue different? The
difference is in the operations that may be performed on them.
stack()constructor builds a new empty
top()method returns the element on the top of the
itemto the top of the
pop()method removes the element at the top of the
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.
queueis known as the front of the
queueand the other end is known as the back and all of the operations that modify the
queueare performed at one of the ends. Here are the operations provided for STL's
queue()constructor constructs a new empty
front()method returns the element at the front of the
back()method returns the element at the back of the
itemto the back of the
pop()method removes the element at the front of the
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
removes and returns the oldest.
This lab exercise has two experiments, one using a
Experiment #1: Working with a
Experiment #2: Working with a
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!