Stacks and Queues

Topics to be covered :
What are stacks and queues?
Terminology
How are they implemented?
Example uses of stacks and queues

Data Structures and Algorithms

Stacks
A stack is a list in which all insertions and deletions are made
at one end, called the top. The last element to be inserted into
the stack will be the first to be removed. Thus stacks are
sometimes referred to as Last In First Out (LIFO) lists.
top

Data Structures and Algorithms

Stack Interface
The following operations can be applied to a stack:
InitStack(Stack):
Push (Item):
Pop(Stack):
Top(Stack):
isEmpty(Stack):

creates an empty stack

pushes an item on the stack
removes the first item from the stack
returns the first item from the stack
w/o removing it
returns true is the stack is empty

Data Structures and Algorithms

Push

5
4
3
2
1

Push(41)
21
12
5

Data Structures and Algorithms

5
4
3
2
1

41
21
12
5

Pop

5
4
3
2
1

41
21
12
5

x = Pop()

Data Structures and Algorithms

5
4
3
2
1

21
12
5

Stack Implementation using Arrays

(quick and dirty)
int StackArray[50]; // StackArray can contain
// up to 50 numbers
int top=-1;
// index of the top element of the stack
// -1 used to indicate an empty stack
void Push(int elem)
{
top++;
StackArray[top] = elem;
}
int Pop()
{
int elem = StackArray[top];
top--;
return elem;
}

Data Structures and Algorithms

Problem
The previous solution works on a fixed array. What if we want
to have multiple stacks in a program? Copy code?
int StackArray2[50];// a second stack
int top2=-1;
// index of the top element of the stack
void Push2(int elem)
{
top2++;
StackArray[top2] = elem;
}
int Pop(){

Bad idea!

How do we make this more efficient?

Data Structures and Algorithms

Abstract Data Type

Definition:
- An Abstract Data Type is some sort of data together
with a set of functions (interface) that operate on the data.
- Access is only allowed through that interface.
- Implementation details are hidden from the user.

Data Structures and Algorithms

The Stack-ADT
#define STACKSIZE 50
struct Stack
{
int item[STACKSIZE];
int top;
};
void
void
int
int
bool

Stack specification

InitStack(Stack &st);
Push(Stack &st, int elem);
Pop (Stack &st);
Top (Stack st);
isEmpty(Stack st);

stack.h
Only defines the interface!
Data Structures and Algorithms

Using the Stack ADT

#include "stack.h"
void main()
{
Stack st1, st2;

// declare 2 stack variables

InitStack(st1);
InitStack(st2);

// initialise them

Push(st1, 13);
Push(st2, 32);

// push 13 onto the first stack

// push 32 onto the second stack

int i = Pop(st2); // now popping st2 into i

int j = Top(st1); // returns the top of st1 to j
// without removing element
};
Data Structures and Algorithms

10

Application of Stacks
e.g.
Evaluation of arithmetic expressions:
Usually, arithmetic expressions are written in infix notation, e.g.
A+B*C
An expression can as well be written in postfix notation (also
called reverse polish notation):
A+B
becomes
AB+
A*C
becomes
AC*
A+B*C
becomes
ABC*+
(A+B)*C
becomes
AB+C*
Data Structures and Algorithms

11

Evaluating expressions
Given an expression in postfix notation. Using a stack they can
be evaluated as follows:
- Scan the expression from left to right
- When a value (operand) is encountered, push it on the stack
- When an operator is encountered, the first and second element
from the stack are popped and the operator is applied
- The result is pushed on the stack
Data Structures and Algorithms

12

Evaluating Expressions (2)

Example:

7 1 3 + - 4 *

Stack

Data Structures and Algorithms

13

Another Stack Example

- Are stacks only useful for making sense of postfix notation
expressions?
- Not so, Stacks have many uses!
- Another e.g. : Reversing word order
STACKS
SKCATS
- Simply push each letter onto the stack, then pop them
back off again and hey presto!
Data Structures and Algorithms

14

Another Stack Example(2)

STACKS

SKCATS

Data Structures and Algorithms

15

Queues
Definition:
A Queue is an ordered collection of items from which items may be
deleted at one end (called the front of the queue) and into which items may
be inserted at the other end (the rear of the queue).

Data Structures and Algorithms

16

Queue Interface
The following operations can be applied to a queue:
InitQueue(Queue):

creates an empty queue

Join (Item):

inserts an item to the rear of the queue

Leave(Queue):

removes an item from the front of the queue

isEmpty(Queue):

returns true is the queue is empty

Data Structures and Algorithms

17

Queues (FIFO-lists)
21 55 7 12
Rear
Join(36);

Front

36 21 55 7 12
Rear

Front

Elements can only be added to the rear of the queue and removed
from the front of the queue.

Data Structures and Algorithms

18

Queues (contd.)
36 21 55 7 12
Rear
Leave();

Front

36 21 55 7
Rear

Front

Data Structures and Algorithms

19

Implementation of Queues
Removing an element from the queue is an expensive operation
because all remaining elements have to be moved by one position.
A more efficient implementation is obtained if we consider
the array as being circular:
Problem:
How do we know if queue is full/empty?

rear
[2]
e3
[1] e2
e1
[0]

[n-2]
[n-1]

front
Data Structures and Algorithms

20

Joining the Queue

Initially, the queue is empty, i.e. front == rear. If we add an element to
the queue we
1) check if the queue is not full
2) store the element at the position indicated by rear
3) increase rear by one, wrap around if necessary (in this case rear always points
to the last item in the queue the rear item)
Adding one element:
if (rear == QSIZE -1)
rear = 0;
else
rear = rear+1;
add an element to the queue

Data Structures and Algorithms

21

Application of Queues
In a multitasking operating system, the CPU time is shared between multiple
processes. At a given time, only one process is running, all the others are
sleeping. The CPU time is administered by the scheduler. The scheduler keeps
all current processes in a queue with the active process at the front of the queue.

next process

Process
Queue

A
running
process

Data Structures and Algorithms

22

Round-Robin Scheduling
Every process is granted a specific amount of CPU time, its
quantum. If the process is still running after its quantum run out,
it is suspended and put towards the end of the queue.
next process

A
running
process

Process
Queue

Data Structures and Algorithms

23

The Queue-ADT
#define QSIZE 50
struct
{
int
int
int
};
void
void
int
bool

Queue
items[QSIZE];
rear;
front;

InitQueue(Queue &q);
Join(Queue &q, int elem);
Leave(Queue &q);
isEmpty(Queue q);
queue.h

Data Structures and Algorithms

24