Lab 15: Stacks and Queues


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?

The stack

A stack has the following operations:

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.

The queue

A queue has the following operations:

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.

Similar Interfaces

The methods provided by these two container classes are very similar. The main difference is in the pop() operation. The push(e) operation always adds 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.

The Experiments

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.


back, front, stack, stack, top
Lab Home Page | Prelab Questions | Homework Projects
© 2003 by Prentice Hall. All rights reserved.
Report all errors to Jeremy D. Frens.