Data Structures and Algorithms

Chapter Four: Stacks and Queues

This chapter covers:
Stack
Queue

Stacks and queues are data structures that have restricted

data access, which can be accessed from end or start of the
list.

2
 Stack
It is a data structure that has access to its data only
at the end or top of the list.
It operates on LIFO (last in first out) basis.
Stack uses a single pointer or (index) to keep track
of the information or data on the stack.
It has two basic operations:
Push: inserting or adding data at the top of the stack,
Pop: removing data from the top of the stack.

3
 …

A stack of
coins

4
 …
Push Pop

Pop 15
………………..
Push(5) 9 Push(7) 12
………………. 7
Push (6) 6 Push(12) 6
Push (9) 5 Push(15) 5

12
pop 7
6
5

5
 Array implementation of push and pop
operation
Analysis:
suppose the stack has the following structure.
int num[max-size];
We need to have an integer variable that
stores an index value that tells us:
the position where to store a new value
the total number of elements stored in the
stack
int top =-1;

6
To push/add an element to the stack

Check if there is enough space in the

stack
To add new value we should have to
check the space left
top<max_size-1?
Yes – increment top , store the element in
num[top]
No – stack overflow

7
To pop or remove an element from the
stack

check if there is data in the stack

top>=0?
Yes: - copy/remove data at num[top],
decrement top
No: - stack underflow

8
 Implementation – push

int num[max_size];
int top=-1; //initial
void push(int x)
{
if (top<max_size-1)
{
top++;
num[top]=x;
}
else
cout<<“stack overflow”;
}
9
 Implementation - pop
int pop()
{
int x;
if(top>=0)
{
x=num[top];
top --;
}
else
cout<<“stack underflow”’;
return x;
} 10
 Implementation ...
Size of stack
int sizeofstack()
{
return(top+1)
}
Is empty?
Bool isempty()
{
return (top==-1)
}
Is full?
Bool isFull()
{
Return(top==max_size – 1)
} 11
Linked List Implementation of Push
and Pop operations
Definition
struct number
{
int num;
Botptr
number *next;
};

Topptr

12
 Analysis:
We need two pointers (Botptr and topptr) that points to first and
last node of the stack
number *botptr=NULL, *topptr=NULL;
To push data to the stack
Check if there is enough space in the stack – i.e free memory
space. We need a pointer that points to the newly created -
newnumptr = new number;
newnumptr !=NULL→ there is free Memory space pointed by newnumptr
Yes: - copy/store the pushed value to newly created node
Create the link between the last node and the new node….

13
 (continued)…
Make topptr to point to the last node (newly created node) →
cin>>newnumptr->num; newnumptr->next=NULL;
NO: stack overflow

Botptr

newnumptr
Topptr
14
 POP
Check if there is data in the stack
bottomptr!=NULL???
Yes: - topptr should point to the previous node. When we have only
one node botptr and topptr should point to NULL
Deleting the last node
No: - stack underflow

prevptr
botptr lastptr

15
 Exercise
Write the complete code of stack implementation using
single linked list.

16
 Application of Stack
1. Variable declaration
Void main()
{int i, n;
for (i=0;i<=10;i++)
{int m;
cin>>n;
cin>>m;
cout<<m*n;
} Used to hold
cout<<n; m variables when
}
n declared

i
17
 Application of Stack
2. function calling
Void main(){
Func1();
Func2();} Func3()
Void func1(){ Func1() Func1()
Cout<<“selam”;
Main() Main() Main()
Func3();
}
Void func2(){ 1 2 3 4
Cout<<“Hi”;
}
Void func3(){
Cout<<“Hello”;
Func1() Func2()
} Main() Main() Main()
}
5 6 7
Note : The one that is found on the top of the stack is currently executed.
When empty stack remain, the program will halt 18
 Application of Stack
3. recursive programming
int factorial (int n) Factorial(0) = 1
{ Factorial(1) = 1
if(n==0 || n==1)
Factorial(2)= 2
return (1);
else .
return(factorial(n-1)*n)
.
}
.
Factorial(n-2)
Factorial(n-1)
Factorial(n)
19
 4. Evaluation of Algebraic Expressions
Ex. 4 + 5 * 5
= 45 using simple calculator
= 29 scientific calculator
To solve this problem we need to restructure in a way that can
be resolved by computer without ambiguity.
Types of expressions are; humans use infix form – where
operators come in between operands.
Prefix / Postfix are when operators come before and after
operands correspondingly. Or polish and reverse polish.
4 5 5 * + postfix
+ 4 * 5 5 prefix
In postfix parenthesis are unnecessary and easy for computer
to evaluate arithmetic expression.
20
 …
Infix to postfix conversion
Infix Notation Postfix Notation prefix Notation
A+B AB+ +AB
Eg.
(A+B)*C AB+C* *+ABC
(A+B)*(C-D) AB+CD-* *(A+B)(C-D)
*+AB-CD
*+-EF,
E=AB, F=CD

21
 …
Computing Postfix Notation
AB+

+ Op=pop()
B Op1=pop()
A Op2=pop()
Result
Op2 op op1 = result
Push (result)

22
 …
example
AB+C*
+ *
B C
A Result1 Result1 Result2

Eg. 4 5 +2* + *
5 2
4 9 18
23
 Exercise
1.Write a program that convert infix to postfix notation
2. write a program that computes a given postfix notation

24
 QUEUE
A queue is an ordered collection of items for which we can
only add an item at the back or remove an item from the front.

It operates on FIFO (first in first out) basis

The queue is yet another data structure, much like a stack, but
with a much more limited set of operations.
 Queue operations
It has two operations
Enqueue: adding data at the end of the list
Dequeue: deleting data at the head of the list
E.g.,
Enqueue(c)
Enqueue (B) C | B| A
Enqueue(A)
Dequeue() | B| A
Enqueue(D)
| B| A| D
Dequeue()
A|D

26
 Simple array implementation of
enqueue and dequeue

Analysis – consider the following structure

int num[max-size];
We need the following variables
int rear=-1, front=-1, queuesize=0;

27
 To enqueue
Check if there is space
Queuesize<max-size or //rear< max-size?
Yes: queuesize==0?
Yes: increment front
No: Increment rear and queuesize, Store the data in data in num[rear]
No: queue overflow

28
 To dequeue
Check if there is data
Queuesize>0?
Yes:
Copy the data in num[front]
Increment front
Decrement queuesize
No: queue underflow

29
 example
Enqueue(5) →5
Enqueue(7) →5,7
Enqueue(4) →5,7,4
Dequeue() →7,4
Enqueue(2) →7,4,2
F R

|7|4|2

30
 Exercise
Write a simple array implementation of queue data
structure (including the operations enqueue, dequeue,
isempty, isfull, an so on)

31
 Circular queue
Rear of the queue is somewhere clockwise from the front
To enqueue an element, we move rear one position
clockwise and write the element in that position
To dequeue, we simply move front one position clockwise
Queue migrates in a clockwise direction as we enqueue and
dequeue
emptiness and fullness to be checked carefully.

32
 Array implementation of Circular
Queue
Limitation of simple array implementation is, as we keep
on dequeueing an element from the array, front may exceed
maxsize, while we have some free spaces
E.g num[5]
dequeue(), dequeue(), dequeue(), dequeue(), dequeue(),
Enqueue(3) impossible
F R
5 | 7 | 6 | 11 | 8

F R
| | | |
33
Array implementation of Circular
queue

34
 To enqueue

Check if there is space

Quesize<max-size??
Yes:
Queuesize==0??
Yes: increment front
Increment rear and Queuesize
Rear==maxsize??
Yes: rear=0
Store the data in num[rear]

No: queue overflow

35
 To dequeue
Check if there is data
Queuesize>0???
Yes:
Copy the data in num[front]
Increment front
Front==max-size??
Yes:Front=0;
Decrement queuesize
No: queue underflow

36
 Exercise
Write the array implementation of circular queue data
structure

37
 Linked List Implementation of
enqueue and dequeue
Enqueue – inserting node at the end of the list.
Dequeue – deleting the first node in the list.
Implementation – exercise, just see the linked list adding at
the end and deleting at the start example from the previous
chapter

38
 Different types of queue
Deque:
 is also double ended queue
Insertion and deletion are possible at both ends
Implementation are the same as that of queue
Is best implemented by double linked list
Implementation: exercise

39
 Priority queue
In priority queues, elements arrive in an arbitrary order, but
are enqueued with information about their priority.
It is a queue where each element has an associated key
value at the time of insertion.

40
 e.g.
Original queue
Sara Abdi Ahmed Meron Abiy saba
F M M F M F

Female Queue
Sara Meron Saba

Male Queue
Solomon Ahmed Abiy
41
 continued….
While (original queue is not empty)
{
Data=dequeueOriginalQueue();
If(gender of data is male)
Enqueue male queue(data);
Else
Enqueue Female queue(data)
}

42
 To create priority queue
While (female queue is not empty)
Enqueue to priority queue (dequeue female queue())
While (males queue is not empty)
Enqueue to priority queue
Priority queue

Sara Meron saba Solomon Ahmed Abiy

F F F M M M

43
 e.g.2
The data with the largest element with higher priority

A B C F E D H
40 30 25 15 18 20 12

Dequeue() A will be selected

Dequeue() B >>
Dequeue() C >>
Dequeue() D >>

44
 Exercise

Write a program that merges two priority queues,

sorted in ascending order of priority, to create a single
queue.
E.g
A C D F
40 25 20 15 A B C D E F H G
40 30 25 20 18 15 12 10
B E H G
30 18 12 10

45
 Application of Queue
1. printserver
Print()
{
Enqueue printqueue(document)
}

End_of_print()
{
Dequeue printqueue()
}

Document1.doc letter.doc assign.cpp

46
 Application of queue
2. disk driver, the one first inserted will have first letter (eg.
A:, B:, C:, D:, E…

3. Task scheduler in multiprocessing system

Eg. Printing 16, searching 5, browsing 17, opening 7

47
 Application of queue
4. telephone calls in a busy environment
5. simulation of waiting line
Line in a supermarket
Line at cafeteria, bank and so on…

48