STACKS AND QUEUES

1. Stacks

In this handout, we will look at how lists are used. We can divide lists into two
basic categories, according to the operations that are required to operate on the
data in the list. These categories are stacks and queues.

A stack is a list of data structure that can only be accessed at one of its ends. In
other words, if we want to add a new value into the stack, or remove a value from
the stack, we can only do so from one end of the list. Consider Figure 1. To begin
with, in Figure 1a, the stack is empty. Then we push the value 6 onto the stack.
The term push is commonly used to refer to the operation of adding a value to a
stack data structure. Next we push the value 11 onto the stack, so 11 becomes the
‘top’ element of the stack, and 6 moves down to second place. In Figure 1c, we
pop an element from the stack. To pop an element from a stack simply means to
remove the top element. In this case, the value 11 is popped. Next the values 8 and
then 5 are pushed onto the stack, so in Figure 1f the top element is 5. Finally the
top element, 5, is popped from the stack. Stacks are often referred to as a LIFO
structure: Last In/First Out. You can think of stacks as similar to a pile of trays in
a cafeteria. Trays are put on the top of the pile and removed from the top. The last
tray put on the pile is the first one removed. A tray can only be taken if there are
trays in the pile, and a tray can be added to the pile only if there is enough room,
i.e. if the pile is not too high.

A stack is defined in terms of the operations that we need to manipulate its

elements. The operations are as follows:
 clear() – Remove all elements from the stack.
 isEmpty() – Check to see if there are elements on the stack.
 push(el) – Put the element el on the top of the stack.
 pop() – Take the topmost element from the stack.
 topEl() – Return the topmost element in the stack without removing it.

Figure 1 – The operation of a stack

When are stacks useful? One common application is in writing compilers.

Whenever a function call is made, the code generated by the compiler must store
the values of all local variables ready for when program execution returns from
the function call. Within the called function, any number of nested function calls
could be made, and for each of them the values of local variables (the
environment) also needs to be stored. A stack is an ideal data structure for this
task. Before each function call, the current environment is pushed onto a stack,
and as each function finishes execution, the environment is popped from the stack.
Consider the code below.

1
//*************** Function Calls.cpp ****************
// program to illustrate nested function calls

#include <iostream.h>

int f1 (int);
int f2 (int);

main () {
int x = 3;
cout << "f1(f2(3)) = " << f1(x) << endl;
}

int f1 (int a) {
int p = a * 3;
return f2(p + 2);
}

int f2 (int b) {
int q = b * 2;
return q - 1;
}

In the main function, the environment consists of the fact that the local variable x
has the value 3. So when the function f1 is called, this information is pushed onto
the stack. Next, inside f1, the environment contains the information that a is
equal to 3 and p is equal to 9, so when f2 is called this information is pushed onto
the stack. When execution of f2 finishes, the topmost environment is popped
from the stack, and when execution of f1 finishes, the next environment is
popped from the stack. In this way, the correct environment can be restored after
each function call completes. This process is illustrated in Figure 2.

Figure 2 - The use of a stack in storing variable values in code execution

2
2. Queues

A queue is also a type of list, but whereas with a stack the data elements are only
added and removed from the same end of the list, with a queue the elements are
always added to one end of the list, but removed from the other. You can think of
a queue data structure as being like a queue of people waiting to use a payphone,
or to be served at the bank. A queue is a FIFO structure: First In/First Out.

Queue operations are similar to stack operations. The following operations are
needed to properly manage a queue
 clear() – Remove all elements from the queue.
 isEmpty() – Check to see if there are elements in the queue.
 enqueue(el) – Put the element el at the end of the queue.
 dequeue() – Take the first element from the head of the queue.
 firstEl() – Return the first element in the queue without removing it.

A series of enqueue and dequeue operations is shown in Figure 3. This time, the
new data elements are added to one end of the list (the right) and elements are
removed from the other end (the left). For example, after enqueueing 6 and 11, the
first dequeue operation (Figure 3c) removes the data element 6. If this were a
stack data structure, then the last element to be entered (11) would have been
removed. Similarly, at the dequeue in Figure 3f it is the 11 element that is
removed, as this is at the head of the queue.

Figure 3 - The operation of a queue

A potential application of a queue data structure is for multitasking. Often an

operating system will have a number of processes that all need to use the
computer’s CPU. A simple way of allocating CPU time is on a first-come-first-
served basis – the first process to request CPU time is allowed to use it, and
subsequent processes join a queue and are allowed to use the CPU when they
reach the head of the queue.

Another common application of queues is in simulation. As an example, consider

that the Commercial Bank of Ethiopia in Kotebe have a number of clerks serving
customers, with a single queue of customers waiting to be served. How many
clerks should the bank employ? By observing the frequency of arrival of
customers, and the amount of time taken to serve each customer, it is possible to
write a simulation of the operation of the bank, using a queue data structure. This
simulation will predict how many customers will be waiting in the queue on
average, based on the number of clerks. By running the simulation for different
numbers of clerks, the bank can decide on the optimal number of clerks required.

It is possible to implement a queue data structure using an array, in a similar way

to the stack implementation described above. However, there are difficulties with

3
such an implementation. Consider the sequence of enqueue and dequeue
operations illustrated in Figure 4. Here we are using an array of fixed length 5 to
implement the queue data structure. What happens when the final enqueue
operation (Figure 4h) is requested? There is no space left to add the new data
element at the end of the array, but there is free space at the beginning. These cells
should not be wasted. Therefore we can add the new data to the beginning of the
array. But now the beginning and end of the queue can potentially be anywhere in
the array, so we need to remember where they are. Figure 5a shows the array after
enqueueing the data element 2. The new element has been added to the beginning
of the list but the last variable has been updated to indicate this fact. Sometimes it
is easier to visualise such an array as a circular array, as in Figure 5b. Note that
this is for visualisation purposes only, it does not change the actual
implementation.

We can now define the enqueue operation as follows:

 If the last element is in the last cell, and there are free cells at the
beginning of the list, add the new value at the beginning of the list.
 If the last element is in any other position, then put the new value in the
cell after the last value, if it is free.
Both the enqueue and dequeue operations are executed in constant time O(1), but
the queue is of limited length. Queues can also be implemented using dynamic
data structures, which avoid the problems described above.

Figure 4 - The operation of a queue using a fixed-length array implementation

Figure 5 – Two different ways of visualising a fixed-length array implementation of a queue

4
3. Deques

A deque (pronounced like “deck”) is a variation on the standard queue data

structure. The word deque is an acronym derived from double-ended queue.
Deques extend the basic queue data structure by allowing elements to be enqueued
or dequeued from either end of the deque. The following operations are required
to maintain a deque data structure:
 clear() – Remove all elements from the queue.
 isEmpty() – Check to see if there are elements in the queue.
 enqueueHead(el) – Put the element el at the head of the queue.
 enqueueTail(el) – Put the element el at the tail of the queue.
 dequeueHead() – Take the first element from the head of the queue.
 dequeueTail() – Take the last element from the tail of the queue.
 head() – Return the first element in the queue without removing it.
 tail() – Return the last element in the queue without removing it.

Figure 6 illustrates the operation of a deque. Note that we can think of a deque as
a generalisation of the stack and queue data structures. If we only use the
enqueueHead() and dequeueHead() operations then a deque behaves like a stack.
If we only use the enqueueHead() and dequeueTail() operations then it behaves
like a queue.

Figure 6 – The operation of a deque

4. Priority Queues

Often, the basic queue data structure is not appropriate. For example, consider the
multitasking application described in Section 2 above. With the standard queue
data structure processes are executed by the CPU on a first-come-first-served
basis. Sometimes this is what is required. However, occasionally a process will
arrive at the end of the queue that is more urgent than the processes ahead of it.
For example, this may be an error-handling process. In this case, we want the
urgent process to jump the queue, and be executed before the existing processes in
the queue. In situations like this, a variation on the queue, called a priority queue,
is needed. In priority queues, elements arrive in an arbitrary order, but are

5
 enqueued with information about their priority. Elements are dequeued according
to their priority and their current queue position.

Priority queues are usually implemented using dynamic data structures. A number
of different possible implementations exist, but we will not cover them in this
course.

5. The Standard Template Library

Although implementations of lists, stacks, queues and other data structures have
been provided in these handouts, there is an existing C++ library of templated data
structures, called the Standard Template Library (STL). The STL contains built-in
classes for storing lists, stacks, queues, deques and priority queues. Many C++
textbooks contain details of the STL. For example, see “C++ Program Design” by
Cohoon & Davidson, p486.

6
Summary of Key Points

The following points summarize the key concepts in this handout:

 A stack is a list data structure that can only be accessed at one end.
 Data elements are added to a stack using the push operation, and removed
using the pop operation.
 A stack is a LIFO (Last In/First Out) data structure.
 Stacks can be implemented using either C++ arrays or linked lists.
 A queue is a list data structure in which data elements are added to one end of
the list, and removed from the other.
 A queue is a FIFO (First In/First Out) data structure.
 Queues can be implemented using either C++ arrays or linked lists.
 A deque (double-ended queue) is a queue in which data elements can be added
or removed from either end of the list.
 A priority queue is a queue in which data elements are removed according to
their priority.
 The Standard Template Library in C++ contains templated classes for lists,
stacks, queues, deques and priority queues.