Unit IV

Stacks, Queues, Recursion

 • Queue
*Stack
– Basic principles
*Basic principles – Operation of
*Operation of stack queue
*Stack using Array – Queue using
Array
*Stack using – Queue using
Linked List Linked List
*Applications of – Applications of
stack queue

2
 What is a Stack?
• Stack of Books

3
 What is a Stack?
• Definition: A stack is a sequential collection of elements into which
new elements are inserted and deleted only at one end called top.
• As all the insertion and deletion in a stack is done from the top of
the stack, the lastly added element will be first to be removed from
the stack. That is the reason why stack is also called Last-In-First-
Out (LIFO) data structure.
• The operations: push (insert) and pop (delete)
pop push(o)

Top 3
2
7
6
Operations on Stack

push

pop

create
STACK
Isempty/
Underflow
Isfull/
Overflow

5
 Stack Implementation

• Stack can be implemented using-

– Array
– Linked Link
Stack Representation using Array
Initial Condition:
#define MAX 5
top=-1;
int stack[Max];

To perform push
operation:
-1 top++;
stack[top]=value;

If top reaches to MAX-1;

Stack will be full and
further data can’t be
inserted(pushed).
To perform pop operation:
top --;
While removing the data if
top reaches to -1, stack will
be empty. Further data
can’t be deleted(popped)
 Stack Operations using Array
• Push() Operation: • Pop() peration:
// Global declaration of variables int pop()
#define MAX 5 {
int st[MAX], top=-1; int val=-1;
void push(int val) if(top==-1)
{ printf(“Stack is empty”);
if(top==MAX-1) else
printf(“Stack is full”); {
else val=st[top];
{ top--;
top++; }
st[top]=val; return(val);
} }
}
 Stack Operations using Array
• isempty() Operation: • Display() peration:
int isempty() void display()
{ {
if(top==-1) int i;
return(1); if(top==-1)
return(0); printf(“Stack is empty”);
} else
• isfull() Operation: {
int isfull() for(i=0;i<=top;i++)
{ printf(“%d\t”,st[i]);
if(top==MAX-1) }
return(1); }
return(0);
}
Implementation of Stack using Linked
List :
• To represent the stack using Linked List, we
will have the following constraints :

– Add the element from only one end

– Delete the element from the same end.

Stack Representation using Linked List
Stack Representation using Linked List
Stack Representation using Linked List
Stack operation using Linked List
Push Operation
 Applications of Stacks :
• Expression conversion and evaluation.

• Reversing a string.

• Parsing

• Well formed parentheses

• Decimal to Binary Conversion

Expression conversion and evaluation.
Mathematical expression; An expression is
defined as the number of operands or data items
combined with several operators
1. Infix Expression
2. Prefix Expression
3. Postfix Expression
Expression conversion and evaluation.
Infix Expression is what we come across in our general
mathematics,

where the operator is written in-between the operands.

For example :
A+B
operator ‘+’ is written in between the operands A and B.
Expression conversion and evaluation.
The same expression when written in
Prefix notation: Polish notation:
+AB
As the operator ‘+’ is written before the operands A and B,
this notation is called prefix (pre means before).

Postfix notation :
AB+
the operator(s) are written after the operands, so it is called
the postfix notation (post means after), it is also known as
suffix notation or reverse polish notation.
Expression conversion and evaluation.

2*4+3^2÷(4+5)–6=

Using infix notation, one cannot tell the order

in which operators should be applied
Conversion of an infix notation to postfix :
Example:
A/B^C + D * C – A * C

Completely parenthesize this expression by using

priority and left to right scan.

((( A / (B^C)) + (D * E)) – (A * C)).

Move each operator to its corresponding right

parentheses:
Conversion of an infix notation to postfix :

• Arrows indicating, where the operator will be

placed. (Relative right parenthesize is its
position).
• Now remove all the brackets, and shift the
operator as indicated by the arrows.

ABC^/DE* + AC* –
 prefix notation.
• Here, we first write the operator and then the
operands. To convert the infix expression to
prefix expression, the steps :
(i) Completely parenthesize the infix
expression, according to order of priority.
(ii) Move each operator to its corresponding
left parentheses.
 prefix notation.
• Convert, A/B^C + D * E – A * C to prefix
notation.

• Parenthesization gives :

• Now remove brackets, place the operators in

the places directed by arrows, we get :
+/A^BC – *DE*AC.
The importance of postfix and prefix notations
• In parsing arithmetic expressions is that these
notations are completely free of parentheses.

• Consequently, an expression in postfix or prefix

notation is unique form.

• In the design of compilers, this parsing of an

expression into postfix form is crucial because having
an unique form for an expression greatly simplifies its
evaluation
Conversion of Infix Expression to Prefix Expression :

a*b+c String

STACK
Conversion of Infix Expression to Prefix Expression :

c
a*b+c String

STACK
Conversion of Infix Expression to Prefix Expression :

c
a*b+c String

PUSH

STACK
Conversion of Infix Expression to Prefix Expression :

c
a*b+c String

+ STACK
Conversion of Infix Expression to Prefix Expression :

c
a*b+c String

+ STACK
Conversion of Infix Expression to Prefix Expression :

b c
a*b+c String

+ STACK
Conversion of Infix Expression to Prefix Expression :

b c
a*b+c String

PUSH

+ STACK
Conversion of Infix Expression to Prefix Expression :

b c
a*b+c String

*
+ STACK
Conversion of Infix Expression to Prefix Expression :

b c
a*b+c String

*
+ STACK
Conversion of Infix Expression to Prefix Expression :

a b c
a*b+c String

*
+ STACK
Conversion of Infix Expression to Prefix Expression :

a b c
a*b+c String

*
+ STACK
Conversion of Infix Expression to Prefix Expression :

a b c
a*b+c String

POP

*
+ STACK
Conversion of Infix Expression to Prefix Expression :

* a b c
a*b+c String

POP

+ STACK
Conversion of Infix Expression to Prefix Expression :

* a b c
a*b+c String

POP

+ STACK
Conversion of Infix Expression to Prefix Expression :

+ * a b c
a*b+c String

POP

STACK
Conversion of Infix Expression to Prefix Expression :
Conversion of Infix Expression to Prefix Expression :
Conversion of Infix Expression to Prefix Expression :
 Reversing a String

M A T H S
String
String

PUSH

STACK
 Reversing a String

M A T H S
String
String

M STACK
 Reversing a String

M A T H S
String
String

PUSH

M STACK
 Reversing a String

M A T H S
String
String

A
M STACK
 Reversing a String

M A T H S
String
String

PUSH

A
M STACK
 Reversing a String

M A T H S
String
String

PUSH
T
A
M STACK
 Reversing a String

M A T H S
String
String

H PUSH
T
A
M STACK
 Reversing a String

M A T H S
String
String

S
H PUSH
T
A
M STACK
Reversing a String

String

S
H POP
T
A
M STACK
Reversing a String

String

S
H POP ‘S’
T
A
M STACK
Reversing a String

S
String

H POP
T
A
M STACK
Reversing a String

S H
String

H POP ‘H’
T
A
M STACK
Reversing a String

S H T
String

POP ‘T’
T
A
M STACK
Reversing a String

S H T A
String

POP ‘A’

A
M STACK
Reversing a String

S H T A M
String

POP ‘M’

M STACK
Reversing a String

S H T A M
String

STACK
Reversing a String :
Reversing a String :
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1;

return n * fact_rec(n-1);
}

STACK
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1;

return n * fact_rec(n-1);
}

n←4
return ← ?

STACK
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1;

return n * fact_rec(n-1);
}

n←4
return ← 4 * ?

STACK
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1;

return n * fact_rec(n-1);
}

n←3
return ← ?
n←4
return ← 4 * ?

STACK
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1;

return n * fact_rec(n-1);
}

n←3
return ← 3 * ?
n←4
return ← 4 * ?

STACK
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1;

return n * fact_rec(n-1);
}
n←2
return ← ?
n←3
return ← 3 * ?
n←4
return ← 4 * ?

STACK
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1;

return n * fact_rec(n-1);
}
n←2
return ← 2 * ?
n←3
return ← 3 * ?
n←4
return ← 4 * ?

STACK
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1;

return n * fact_rec(n-1); n←1

} return ← ?
n←2
return ← 2 * ?
n←3
return ← 3 * ?
n←4
return ← 4 * ?

STACK
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1;

return n * fact_rec(n-1); n←1

} return ← 1 * ?
n←2
return ← 2 * ?
n←3
return ← 3 * ?
n←4
return ← 4 * ?

STACK
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1; n←0
return ← ?
return n * fact_rec(n-1); n←1
} return ← 1 * ?
n←2
return ← 2 * ?
n←3
return ← 3 * ?
n←4
return ← 4 * ?

STACK
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1; n←0
return ← 1
return n * fact_rec(n-1); n←1
} return ← 1 * ?
n←2
return ← 2 * ?
n←3
return ← 3 * ?
n←4
return ← 4 * ?

STACK
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1;

return n * fact_rec(n-1); n←1

} return ← 1 * 1
n←2
return ← 2 * ?
n←3
return ← 3 * ?
n←4
return ← 4 * ?

STACK
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1;

return n * fact_rec(n-1);
}
n←2
return ← 2 * 1
n←3
return ← 3 * ?
n←4
return ← 4 * ?

STACK
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1;

return n * fact_rec(n-1);
}

n←3
return ← 3 * 2
n←4
return ← 4 * ?

STACK
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1;

return n * fact_rec(n-1);
}

n←3
return ← 6
n←4
return ← 4 * 6

STACK
 Recursive factorial
int fact_rec(int n)
{
if (n == 0)
return 1;

return n * fact_rec(n-1);
}
24

n←4
return ← 24

STACK
 Queues :
• Definition :
A queue is logically a first in first out (FIFO
or first come first serve) linear data structure.

– The items can be inserted only at one end

– And removed at the other end.
Stack vs Queue
 Queues
• Operations

– Enqueue - Add an item to the queue

QUEUE

Before Enqueue
 Queues
• Operations

– Enqueue - Add an item to the queue

65
QUEUE

Before Enqueue
 Queues
• Operations

– Enqueue - Add an item to the queue

65
QUEUE

Before Enqueue
 Queues
• Operations

– Enqueue - Add an item to the queue

72 65
QUEUE

After Enqueue
 Queues
• Operations

– Enqueue - Add an item to the queue

81 72 65
QUEUE

After Enqueue
 Queues
• Operations

– Enqueue - Add an item to the queue

81 72 65
QUEUE

After Enqueue
 Queues
• Operations

– Dequeue - Remove an item from the queue

81 72 65
QUEUE

Before Dequeue
 Queues
• Operations

– Dequeue - Remove an item from the queue

81 72 65
QUEUE

After Dequeue
 Queues
• Operations

– Dequeue - Remove an item from the queue

81 72
QUEUE

After Dequeue
 Queue using Array
1. elements are added from one end (i.e. rear
end or tail of Queue) and

2. deleted from another end (i.e. front end or

head of the queue).
 Queue using Array

45 61 56 72 81
front end or head QUEUE rear end or tail

45 61 56 72 81
rear end or tail QUEUE front end or head
 Queue using Array
rear end = -1

4 3 2 1 0
81

front end = 0
 Queue using Array
rear end = 0

4 3 2 1 0
81 81

front end = 0

Rear =Rear+1
 Queue using Array
rear end = 0

4 3 2 1 0
23 81

front end = 0
 Queue using Array
rear end = 1
0

4 3 2 1 0
23 23 81

front end = 0
 Queue using Array
rear end = 2
1

4 3 2 1 0
45 45 23 81

front end = 0
 Queue using Array
rear end = 3
2

4 3 2 1 0
61 61 45 23 81

front end = 0
 Queue using Array
rear end = 4
3

4 3 2 1 0
37 37 61 45 23 81

front end = 0
 Queue using Array
rear end = 4

4 3 2 1 0
11 37 61 45 23 81

front end = 0

Queue is full or Overflow

 Queue using Array
rear end = 4

4 3 2 1 0
37 61 45 23 81

front end = 0

Delete from queue

Queue using Array
rear end = 4

4 3 2 1 0
37 61 45 23 81

front end = 1
0
Queue using Array
rear end = 4

3 2 1 0 0
37 61 45 23

front end = 2
1
Queue using Array
rear end = 4

4 3 2 1 0
37 61 45

front end = 32
Queue using Array
rear end = 4

4 3 2 1 0
37 61

front end = 43
 Queue using Array
rear end = 4

4 3 2 1 0
37

front end = 4

Now Queue is empty resetting queue

 Queue using Array
rear end = 4

4 3 2 1 0

front end = 5

Now Queue is empty as front>rear

EXPT 7 – A:

PROGRAM FOR
QUEUE USING ARRAY
 Expt 7-A:
Program overview
• Delaration
─ Header
─ Global array

• Function for INSERT

• Function for DELETE
• Function for DISPLAY

• Menu using switch case

─ INSERT
─ DELETE Main function
─ DISPLAY
─ EXIT
Queue using Array

• Delaration
─ Header
─ Global array
Queue using Array
#include<stdio.h>

#define MAX 5 /* Global declarations */

int que[MAX];

int rear = - 1;

int front = 0;
Queue using Array
Main function ?
Queue using Array
void main ()
{
while(1)
{
switch case
{
[Link]
[Link]
[Link]
[Link]
}
}
}
void main()
{
int choice;
while (1)
{
printf("\[Link] \n [Link]\n [Link]\n [Link]\n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1: insert();
break;
case 2: del();
break;
case 3: display();
break;
case 4: exit(1);
default: printf("Wrong choice\n");
break;
}
}
}
Queue using Array

• DISPLAY function
rear end = -1

4 3 2 1 0

front end = 0

If the front >rear queue is empty

Queue using Array

• DISPLAY function
rear end = 4 front end = 0

4 3 2 1 0
37 61 45 23 81

For display use for loop

i= front to rear ; i++
void display()
{
int i;
if (front >rear)
printf("\n Queue is empty\n");
else
{
printf ("\n Queue is :\n");
for (i = front; i <= rear; i++)
printf ("%d \t ", que[i]);
printf ("\n");
}
}
Queue using Array

• INSERT function
rear end = 4

4 3 2 1 0
13 96 67 45 34

front end = 0

1) If the rear = max queue is full

void enque( )
{
int val;
if (rear = = MAX - 1)
printf("\nQueue Overflow\n");
else
{
rear ++;
printf("\n\n Input the element for adding in queue : ");
scanf("%d", &que[rear]);
}
}
Queue using Array

• DELETE function
rear end = -1

4 3 2 1 0

front end = 0

If the front >rear queue underflow / empty

Queue using Array

• DELETE function
rear end = 2

4 3 2 1 0
45 11 21
If we delete 2 elements front end = 0
then….
Queue using Array

• DELETE function
rear end = 2

4 3 2 1 0
45
Again 1 delete front end = 2
Queue using Array

• DELETE function
rear end = 2

4 3 2 1 0

front end = 2
void deque()
{
if (front > rear)
{
printf("\n Queue Underflow\n");
}
else
{
printf("\n Element deleted from queue is : %d\n",que[front]);
front ++;
}
}
Queue using Linked List ...?

1. Use struct to implement Linked List.

2. Implement Linked List as Queue.

Queue using Linked List

Data 2 •
Head Data 1 •
NULL
NULL

Initial ... Adding data

Queue using Linked List

Data 2 •
Head Data 1 •
NULL
Queue using Linked List

Head Data 1 • Data 2 •

NULL

Where will be
front & rear?
Queue using Linked List
Front NULL
Data 1 •

Initial

Rear NULL
Queue using Linked List
Front = NULL
Data 2 •

Data 1 • Initial
new1
NULL

Rear = NULL
Queue using Linked List
Front
Data 3 •
new1

Data 1 • Data 2 •

Rear
Queue using Linked List
Front
Data 4 •
new1

Data 1 • Data 2 • Data 3 •

Rear
Queue using Linked List
Front

new1

Data 1 • Data 2 • Data 3 • Data 4 •

Rear
Queue using Linked List

Front

Data 1 • Data 2 • Data 3 • Data 4 •

Rear

Now deleting
Queue using Linked List
Copy front to temp Data •
TEMP
Front

Data 1 • Data 2 • Data 3 • Data 4 •

Rear

Now deleting
Queue using Linked List
Point front
towhere
Copy front temp
temp is pointing
Data 1 •
TEMP
Front

Data 1 • Data 2 • Data 3 • Data 4 •

Rear

Now deleting
Queue using Linked List
Point front
towhere
Copy front temp
temp is pointing
Data 2 •
TEMP
Front

Data 2 • Data 3 • Data 4 •

Rear

Now deleting
EXPT 7 – B:

PROGRAM FOR
QUEUE USING LINKED LIST
 Expt 7-B:
Program overview
• Delaration
─ Header
─ Global Linked List

• Function for ENQUEUE

• Function for DEQUEUE
• Function for DISPLAY

• Menu using switch case

─ ENQUEUE
─ DEQUEUE Main function
─ DISPLAY
─ EXIT
Queue using Linked List

• Delaration
─ Header
─ Global Linked List
Queue using Linked List
#include<stdio.h>
#include<stdlib.h>
/* Global declarations of Linked List*/
typedef struct node
{
int data;
struct node *next; Data •
} Que; info next
Que *front, *rear; struct node
Queue using Linked List

Data • Data • Data •

info next info next info next

struct node struct node struct node

Queue using Linked List
Main function ?
Queue using Linked List
void main ()
{
while(1)
{
switch case
{
1. ENQUEUE
[Link]
[Link]
[Link]
}
}
}
void main()
{
int ch;
rear = NULL; front = NULL;
while (1)
{
printf("\n\n*** QUEUE Implemenation using LINKED LIST ***");
printf("\nEnter:\n1->ENQUEUE\n2->DEQUEUE\n3->DISPLAY\n4->EXIT\n");
scanf("%d", &ch);
switch (ch)
{
case 1: enqueue();
break;
case 2:dequeue();
break;
case 3:display();
break;
case 4:printf("\n~~~Exit~~~");
exit(1);
default:printf("\nInvalid choice please reenter : ");
break;
}
}
}
 DISPLAY function
Front NULL

If
Queue is empty

Rear NULL
 DISPLAY function

Front If

Data 1 • Data 2 • Data 3 • Data 4 •

Rear

• Temp = front
• While front ! = NULL
• Print (info)
void display()
{
node * temp;

if (front == NULL)
{
printf("\nQueue is empty");
}
else
{
temp = front;
printf("\nQueue is : \n");
while (temp != NULL)
{
printf(" %d->", temp->data);
temp = temp->next;
} printf(“-> NULL ");
}
}
 ENQUEUE function
Front
NULL

Data 1 • First copy the data

TEMP to a temp struct
Rear NULL and then enqueue
NULL
 ENQUEUE function
Front

TEMP

Data 1 • Data 2 • Data 3 • Data 4 •

Rear

First copy the data to temp struct

Rear = temp
void enqueue()
{
int ele;
Que *new1;
printf("\nEnter The Element Value : ");
scanf("%d", &ele);
new1 = (node*)malloc(sizeof(node));
new1->data = ele;
new1->next = NULL;
if (front == NULL)
front = rear=new1;
else
{
rear->next = new1;
rear = new1;
}
}
 DEQUEUE function
Front NULL

If
Queue Underflow

Rear NULL
 DEQUEUE function

Point front
towhere
Copy front temp
temp is pointing
Data 1 •
TEMP
Front

Data 1 • Data 2 • Data 3 • Data 4 •

Rear
void dequeue()
{
struct node *temp;
int ele;

if (front == NULL)
{
printf("\nUnder Flow");
}
else
{
temp = front;
ele = temp->data;
front = front->next;
free(temp);
printf("\nThe deleted element = %d\n", ele);
}

}
 Front & Rear positions

relative positions of qFront and qRear are important!

Comparing queue implementations
Array vs Linked List (Memory Requirement)

If queue data is a string (80-bytes)

Comparing queue implementations
Array vs Linked List (Memory Requirement)

If queue data is an int (2-byte)

The Queue Abstract Data Type

What kind of functions can be used in

queue program…?
 The Queue Abstract Data Type

EmptyQueue :?

IsFull :?
Comparing queue implementations
Big-O Comparison of Queue Operations
Operation Array Linked
Implementation Implementation
MakeEmpty O(1) O(N)
IsFull O(1) O(1)
IsEmpty O(1) O(1)
Enqueue O(1) O(1)
Dequeue O(1) O(1)
A circular linked queue design
Circular Queue :
 Circular Queue :

Initial ... Where will be front & rear?

Adding only one data

Circular Queue :

Adding 5 more data

Circular Queue :

Deleting one data

Circular Queue :

Adding 1 more data 164

Circular Queue :

Deleting one data 165

Circular Queue :

Where...?

Adding 1 more data 166

Circular Queue :

Deleting one data 167

 Circular Queue :

Where...will be front & rear?

Deleting 4 data 168

Circular Queue :

Deleting one data 169

 Circular Queue :

Initial ...
 Double-Ended Queues
• Queue has a front and a rear.
• Elements can be added at the rear &
• Removed at the front.

• Now we also want to add elements at the front and remove

them at the rear.

• A double-ended queue (deque) is a queue that supports

insertion and deletion at both the front and the rear of the
queue.

• pronounced as “deck” or “dequeue”

Implementing a Deque with a Doubly Linked List

Example:

header trailer

Toronto Baltimore Rome Seattle

Insertion of an Element at the Head

header trailer

Baltimore Rome Seattle

Insertion of an Element at the Head

header trailer

Baltimore Rome Seattle

Toronto
Deleting an Element at the tail

header trailer

Toronto Baltimore Rome

Seattle
The Deque Abstract Data Type

What kind of functions can be used in

deque program…?
 Priority queue

• A stack is first in, last out

• A queue is first in, first out

• A priority queue is highest-first-out

– Depending upon priority setting

Note : priority queue "first in first out" does not apply.

177
 Priority Queue
• Collection of elements.
• Each element has a priority or key.
• Order in which elements are deleted / processed
depends upon priority.
• Highest priority is accessed first & so on….
• If priority is same elements are accessed in the
ordered they were added to the queue.
 Applications of Priority queue
• Job scheduling by OS.

• Simulation of systems where priority

corresponds to time event.
 Priority Queues

Two kinds of priority queues:

1. Min priority queue.

2. Max priority queue.

 A priority queue ADT
1. insert(item i) : enqueue a new item
2. delete() : dequeue the member with the min/max priority
3. find() : the item with the min/max priority
4. decreasePriority() : decrease the priority of an item
5. increasePriority() : decrease the priority of an item
6. isEmpty :
7. Size :
8. get element with min/max priority:

181
Infix to Postfix Conversion