In addition to defining the
the Standard Template Library (STL) also defines two related classes,
queue classes store linear sequences of values. Visually,
you should pictures
queues like you would
queue are templated classes, so we can talk about a stack of
stack<int>, or a queue of
queue<double>. As you might expect, we find these classes defined
queue libraries, respectively.
The difference between all four of these classes are the operations
that are permitted on them. We've already seen the
list classes in action, so how are the
stack has the following operations:
stack()constructor builds a new
top()method returns the first element on the top of the
push(method adds the element
eto the top of the
pop()method removes the element at the top of the
All of the operations of a
stack operate on the one end of
stack, known as the top of
the stack. If you want to access the second item from the top,
you're out of luck (unless you
pop() the first item). If you
want to access the item at the bottom of the
out of luck (unless you
pop() everything else off
first). If you're using a
stack, you get access only to the
You've seen stacks all of the time---the name is deliberate. Think about a stack of books. If you have a stack of books sitting on your desk, you can "push" another book on top, or you can "pop" one off the top. Trying to grab one from the middle or bottom is tricky at best. You're much safer trying to "push" and "pop" from the top of this stack of books.
queue has the following operations:
queue()constructor constructs a new
queueis empty, code false otherwise.
front()method returns the first element at the front of the
back()method returns the first element at the back of the
push(method adds the element
eto the back of the
pop()method removes the element at the front of the
You've had experience waiting in line. (It's been estimated that the average American spends, all told, five years of their life waiting in line.) 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!"); you won't get service if you leave before you reach the front of the line. In England, these lines are known as "queues", and to avoid ambiguity with the word "line", early computer scientists adopted the British-common term. All the rules you know about real-life lines apply to STL queues: enter in the back, leave in the front.
The methods provided by these two container classes are very
similar. The main difference is in the
pop() operation. The
push( operation always adds
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 those values their own particular ways. Both have their uses, and a basic computer couldn't operate at all without both of them.
Here's a brain teaser to get you to think about how these containers work:
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 very rare, which suggests just how different the power of these two containers are, even though they're different in only one operation!
Turn in the answers to the questions for this lab exercise and its experiments. Turn in your programs and sample executions from those programs.