Stacks & Queues

Chapter 4 Part 2
 Stack
• Linked list and arrays allow one to insert and delete
elements at any place in the list
– At the beginning
– At the end or
– In the middle

• There are frequent situations where one wants to restrict

insertions and deletions so they can take place only at
the beginning or the end of the list, not in the middle

• Two of the data structures that are useful in such

situations are
– stacks and
– queues
2
 Cont’d…
• A stack is a linear data structure (a list of
elements) that has restricted data access

• Items (or elements) may be added (or inserted)

and removed only at one end (usually called
top)

• It operates on Last-In First-Out (LIFO) basis

• A stack has two basic operations, push and pop

• push
– Is a term used for inserting or adding data (or
element) at the top of the stack or into the stack
3
 Cont’d…
• pop
– Is a term used to delete or remove an element
or data from the top of the stack

4
 Stacks
• A simple data structure, in which insertion and deletion
occur at the same end is called a stack.
• It is a Last In First Out (LIFO) structure
• The operations of insertion and deletion are called PUSH and
POP
• Push - push (put) item onto stack
• Pop - pop (get) item from stack
Initial Stack Push(8) Pop

TOS=> 8
TOS=> 4 4 TOS=> 4
1 1 1
3 3 3
6 6 6
5
 Cont’d…
push adds an item to a stack
pop extracts the most recently pushed item from the stack
Other methods such as
top returns the item at the top without removing it
isEmpty() determines whether the stack has anything in it
isFull() determines whether the stack is full or not

6
… Stack operations
• Top (or Peek):
• This operation allows viewing the element at the top of the stack
without removing it. It simply returns the value of the topmost
element.
• IsEmpty:
• This operation checks whether the stack currently contains any
elements. It returns a boolean value (true if empty, false otherwise).
• This is crucial for preventing underflow errors during pop operations.
• IsFull:
• This operation, primarily relevant for fixed-size stack implementations
(e.g., array-based), checks if the stack has reached its maximum
capacity. It returns a boolean value (true if full, false otherwise).
• This is important for preventing overflow errors during push
operations.

7
 Array implementation of Stack
• //array implementation of stack
#include<iostream>
const int size=10;
int Num[size],top=-1;

int isFull()
{
return (top>=size-1);
}
int isEmpty()
{
return top==-1;
}
void push(int x)
{
if( !isFull() )
Num[++top]=x;
else cout<<"\nStack overflow";
}
8
 Cont’d…
int pop()
{
if( !isEmpty() )
return Num[top--];
else {
cout<<"\nStack underflow";
return 0;
}
}
int topData()
{
if(!isEmpty())
return Num[top];
else{
cout<<"\nEmpty stack";
return top;
}
}
int stackSize()
{
return (top+1);
} 9
 Cont’d…
int main() Result
{
for(int i=0;i<20; i +=2)
if( !isFull() )
push(i);
cout<<"\npop(): "<<pop();
push(55);
push(77);
cout<<"\nTop data: "<<topData();
cout<<"\nStack size: "<<stackSize();
cout<<endl;
while( !isEmpty() )
cout<<pop()<<" ";
pop();
}

10
 Linked list implementation of stack
#include<iostream.h>
struct stack{
int num;
stack *next;
};
stack *top=NULL;
void push()
{
stack *newptr=new stack;
cout<<"\n Enter a number: ";
cin>>newptr->num;
newptr->next=NULL;
if(top==NULL)
top=newptr;
else
{
newptr->next=top;
top=newptr;
}
}
11
 Cont’d…
void pop()
{
stack *ptr;
if(top!=NULL)
{
ptr=top;
top=top->next;
delete ptr;
}
else
cout<<"\n Stack underflow!";
}
void display()
{
stack *ptr;
ptr=top;
while(ptr!=NULL)
{
cout<<ptr->num<<'\t';
ptr=ptr->next;
}
}

12
 Cont’d…
int main()
{
int option;
do{
cout<<"\n 1. Insert node... ";
cout<<"\n 2. Delete node... ";
cout<<"\n 3. Display stack...";
cout<<"\n 4. Exit stack...";
cout<<"\n Enter option for stack...";
cin>>option;
switch(option)
{
case 1: push(); break;
case 2: pop(); break;
case 3: display(); break;
}
}while(option!=4);
}
13
 Cont’d…
•

14
 Stack Applications
• Surprisingly, stacks have many application

• Most compilers use stacks to analyze the syntax of a

program

• Stacks are used

– To keep track of local variables when a program is run
– To search a maze or family tree or other types of
branching trees

15
 …Applications of stack
• Conversion of infix to postfix notations and
evaluation postfix expressions
• Recursive functions
– Recursive binary searching, Recursive
function to solve towers of Hanoi problem,
etc.
• Text Editing
– Typing text
– Undo & Redo commands use stack
• Checking Bracket matching
16
 Queue
• Is an ordered collection of items from which items may
be deleted at one end (called front of the queue) and
into which items may be inserted at the other end
(called the rear of the queue)

• That is, it is a data structure that has access to its data at

the front and rear
• Operates at First In First Out (FIFO) bases

17
 Queue
• Has three primitive operations applied to it

– enqueue(q,x) also called insert(q,x)

• Inserts item (data) x at the rear of the queue q

– X=dequeue(q) also called remove(q)

• Deletes the front element (data) from the queue q and sets X
to its content

– empty(q)
• Returns false or true depending on whether or not the queue
contains any elements

18
 Simple array implementation of Queue
#include<iostream>
Using namespace std;
const MAX_SIZE=100;
int NUM[MAX_SIZE],Front=-1,Rear=-1,Queuesize=0;
void Enqueue(int x)
{
if(Rear<MAX_SIZE-1){
NUM[++Rear]=x;
if(Front==-1) Front++;
Queuesize++;
}
else cout<<"\nQueue overflow";
}
int Dequeue()
{
if(Queuesize>0){
Queuesize--;
return NUM[Front++];
}
else
{
cout<<"\n Queue underflow.";
return -1;
}
} 19
 Cont’d…
int main()
{
for(int i=2;i<=20;i+=2)
Enqueue(i);
cout<<"\n Queue elements \n";
for(int k=Front;k<=Rear;k++)
cout<<" "<<NUM[k];
cout<<"\n Dequeue \n";
for(i=1;i<=10;i++)
cout<<" "<<Dequeue();
cout<<"\nDequeue: "<<Dequeue();
cout<<"\nDequeue: "<<Dequeue();
}

ple
m f
Sa un o
r he m
t ra
r og
p 20
 Linked list implementation of Queue
#include<iostream>
Using namespace std;

struct Number{
int num;
Number *next;
};
Number *Front=NULL,*Rear=NULL;
void enqueue(int x)
{
Number *Newptr;
Newptr=new Number;
if(Newptr!=NULL){
Newptr->num=x;
Newptr->next=NULL;
if(Front==NULL)
Front=Newptr;
else Rear->next=Newptr;
Rear=Newptr;
}
else cout<<"\nQueue overflow";
} 21
 Cont’d…
int dequeue()
{
int y; Number *p;
if(Front!=NULL){
y=Front->num;
p=Front;
Front=Front->next;
delete p;
return y;
}
else{
cout<<"\nQueue underflow";
return -1;
}
}
22
 Cont’d…
int main()
{
Number *k;
for(int i=2;i<=30;i+=2)
enqueue(i);
cout<<"\nQueue elements\n";
for(k=Front;k!=NULL;k=k->next)
cout<<"-> "<<k->num;
cout<<"\ndequeue(): "<<dequeue();
cout<<"\ndequeue(): "<<dequeue();
cout<<endl;
enqueue(44);
cout<<endl;
while(Front!=NULL)
cout<<" "<<dequeue();
cout<<"\ndeq: "<<dequeue();
}

23
 Cont’d…

• Sample run of the program

24
 Circular array implementation of Queue
• The circular array implementation of a queue
with capacity QUEUESIZE can be simulated
as follows: 13
12 11
10
9

MAX_SIZE - 1 8

0 7

1 6

2 5
3 4

• if we have free slot we can use it

• In any case, queue[rear] is the last entry in the
queue

25
#include<iostream>
Circular Queue
using namespace std;

const MAX_SIZE=10;
int NUM[MAX_SIZE],Front=-1,Rear=-1,Queuesize=0;
void enqueue(int x)
{
if(Queuesize<MAX_SIZE){
Rear++;
if(Rear==MAX_SIZE)
Rear=0;
NUM[Rear]=x;
if(Front==-1) Front++;
Queuesize++;
}
else cout<<"\nQueue overflow";
}
int dequeue()
{
if(Queuesize>0){
int y=NUM[Front];
Front++;
if(Front==MAX_SIZE)
Front=0;
Queuesize--;
return y;
}
else return -1;
} 26
 Cont’d…
int main()
{ Result of the program
for(int i=2;i<=20;i+=2)
enqueue(i);
enqueue(30);
cout<<endl;
cout<<"\nQueue elements\n";
for(int k=Front;k<=Rear;k++)
cout<<" "<<NUM[k];
cout<<"\n dequeue: "<<dequeue();
cout<<"\n dequeue: "<<dequeue();
enqueue(22);
enqueue(24);
cout<<"\nQueue elements\n";
while(Queuesize>0)
cout<<dequeue()<<" ";
}

27
 Priority Queue
• Using a queue ensures that customers are served in the exact
order in which they arrive

• However, we often want to assign priorities to customers and

serve the higher priority customers before those of lower
priority

• In fact, in many situations, simple queues are inadequate since

first-in-first-out scheduling has to be overruled using some
priority criteria

• Examples

– A hospital emergency room will handle most severely

injured patients first, even if they are not “first in line”

• In situations like this, a modified queue, or priority queue, is

needed
28
 Priority Queue
• Is a data structure that stores entries along with a priority for
each entry

• Is a queue where each element has an associated key which

indicates priority of the elements

• This key is provided at the time of insertion

• Entries are removed in order of priorities

• The highest priority entry is removed first

• If there are several entries with equal high priorities, then the
one that was placed in the priority queue first is the one
removed first

29
 Priority Queue
• That is, in priority queues, elements are dequeued according to

– Their priority and

– Their current queue position

• Elements arrive randomly to the priority queue

• Thus, there is no guarantee that the front elements will be the

most likely to be dequeued and the elements put at the end will
be the last candidates for dequeueing

30
 Priority Queue
• A wide spectrum of possible criteria can be used to
prioritize elements in different cases
– Frequency of use
– Birth date
– Salary
– Position
– Status
– gender

31
 Priority queue enqueue and dequeue operations
• Dequeue operation deletes data having highest priority in
the list

• One of the previously used dequeue or enqueue operations

has to be modified

• Example:

– Consider the following queue of persons where females

have higher priority than males (gender is the key to give
priority).

Abebe Alemu Aster Belay Kedir Meron Yonas

Male Male Female Male Male Female Male
32
 Priority queue enqueue and dequeue operations
• Dequeue() deletes Aster

Abebe Alemu Belay Kedir Meron Yonas

Male Male Male Male Female Male

• Dequeue() deletes Meron

Abebe Alemu Belay Kedir Yonas

Male Male Male Male Male

• Now the queue has data having equal priority and dequeue
operation deletes the front element like in the case of ordinary
queues.
33
 Priority queue enqueue and dequeue operations

• Dequeue() deletes Abebe

Alemu Belay Kedir Yonas

Male Male Male Male

• Dequeue() deletes Alemu

Belay Kedir Yonas

Male Male Male
• Thus, in the above example the implementation of the
dequeue operation need to be modified.

34
 Types of Priority queues
• There are two types of priority queues, ascending priority
queue and descending priority queue

35
 Ascending Priority Queue
• Is a collection of items into which items can be inserted
arbitrarily and from which only the smallest item can be
removed

– The operation enqueue(pq,x) insrtes element x into the pq

and

– The operation dequeue(pq) removes the minimum element

from pq and returns its value the queue

36
 Descending Priority Queue
• Is a collection of items into which items can be inserted
arbitrarily and from which only the largest item can be
removed

– The operation enqueue(pq,x) inserts element x into the pq

and is logically identical with the enqueue(pq,x) operation
for an ascending priority queue

– The operation dequeue(pq) removes the maximum element

from pq and returns its value

37