Lab 14: Stacks and Queues


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.

The stack Container

One end of a stack is known as the top of the stack and all of the operations that access or modify a stack's elements are performed at the top. Here are the operations provided for STL's stack container:

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.

The queue

One end of a queue 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:

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.

Similar Interfaces

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.

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 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!

Lab Home Page

Report errors to Larry Nyhoff (