In addition to defining the vector and list classes,
the Standard Template Library (STL) also defines two related classes,
stack and queue.
Just like vector and list, the stack and
queue classes store linear sequences of values. Visually,
you should pictures stacks and queues like you would
a vector or list.
Also like vector and list, stack and queue are templated classes, so we can talk about a stack of ints, stack<int>, or a queue of doubles, queue<double>. As you might expect, we find these classes defined
in the stack and queue libraries, respectively.
The difference between all four of these classes are the operations
that are permitted on them. We've already seen the vector
and list classes in action, so how are the stack and
queue different?
stackA stack has the following operations:
stack() constructor builds a new stack.empty() method returns true if the stack
is empty, false otherwise.top() method returns the first element on the top of
the stack.push(e) method adds the element e to the top of the stack.pop() method removes the element at the top of the
stack.All of the operations of a stack operate on the one end of
the 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 stack, you're
out of luck (unless you pop() everything else off
first). If you're using a stack, you get access only to the
top.
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.
queueA queue has the following operations:
queue() constructor constructs a new queue.empty() method returns true if the queue is empty, code false otherwise.front() method returns the first element at the front
of the queue.back() method returns the first element at the back of
the queue.push(e) method adds the element e to the back of the queue.pop() method removes the element at the front of the
queue.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 e)e 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 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.