Stack

Stack
• Linear data structure
• Deletion order → reverse order of insertion
• Works on last in first out (LIFO) or first in last out (FILO)
• Both insertion and deletion are performed only at one end
called TOP of stack
• TOP → points to most recently added element
• Insert → PUSH
• Delete → POP
• TOP == -1 → Stack is empty
Application of stack
• Infix to postfix To Delay
• Infix to prefix To postponed decision
 UNDO
• Postfix evaluation
• Recursion
• Parenthesis checking
• Depth first search
PUSH() and POP() operation on stack

PUSH(10)
Empty PUSH(20) POP()

20 TOP
10 TOP
10 TOP 10

PUSH(30)
PUSH(40)
POP() POP()

40 TOP
30 TOP 30 30 TOP
10 TOP 10 10 10
Implementation Of Stack Using Array

STACK
0 1 2 3 4 5 6 7 8 9

Initially TOP = -1

#define SIZE 10
int STACK [SIZE];
int TOP = -1;
PUSH() Algorithm
1. Checks if the stack is full.
2. If the stack is full, produces an error and exit.
3. If the stack is not full, increments top to point next empty space.
4. Adds data element to the stack location, where top is pointing.
5. Returns success
PUSH() operation

STACK 5 10 15 20 25 30 35 40 45 50
Operation TOP 0 1 2 3 4 5 6 7 8 9
- -1
PUSH (5) 0
TOP = -1
PUSH (10) 1
PUSH (15) 2
PUSH (20) 3
void PUSH(int x)
PUSH (25) 4
{
PUSH (30) 5
TOP = TOP + 1;
PUSH (35) 6
STACK[TOP] = x;
PUSH (40) 7
}
PUSH (45) 8
PUSH (50) 9
Stack Overflow

Operation TOP STACK 5 10 15 20 25 30 35 40 45 50 X

- -1
0 1 2 3 4 5 6 7 8 9 10
PUSH (5) 0
PUSH (10) 1
PUSH (15) 2 TOP = -1
PUSH (20) 3
void PUSH(int x)
PUSH (25) 4 {
PUSH (30) 5 if (TOP >= SIZE - 1)
PUSH (35) 6 {
PUSH (40) 7
printf("overflow");
return;
PUSH (45) 8
}
PUSH (50) 9 TOP = TOP++;
PUSH(55) 10 STACK[TOP] = x;
}
POP() Algorithm
1. Checks if the stack is empty.
2. If the stack is empty, produces an error and exit.
3. If the stack is not empty, accesses the data element at which top is
pointing.
4. Decreases the value of top by 1.
5. Returns success.
POP() operation

STACK 5 10 15 20 25 30 35 40 45 50
Operation TOP 0 1 2 3 4 5 6 7 8 9
- 9
POP() 8
TOP = 9
POP() 7
POP() 6
POP() 5
int POP()
POP() 4
{
POP() 3
int temp;
temp = STACK[TOP];
TOP = TOP - 1;
return temp;
}
Stack underflow

Operation TOP STACK 5 10 15 20 25 30 35 40 45 50

- 9 0 1 2 3 4 5 6 7 8 9
POP() 8
POP() 7
POP() 6
TOP = 9
int POP()
POP() 5 {
POP() 4 int temp;
POP() 3 if (TOP <= -1)
{
POP() 2 printf("Underflow");
POP() 1 return INT_MIN;
POP() 0 }
temp = STACK[TOP];
POP() -1 TOP = TOP - 1;
POP() return temp;
}
//stack push pop
#include<stdio.h> PUSH() & POP()
int TOP=-1;

void push(int arr[] , int size);

void pop(int arr[] , int size);

int main()
{
int size,i;
printf("enter size of stack : ");
scanf("%d",&size);
int arr[size];

push(arr,size);
push(arr,size);
push(arr,size);
pop(arr,size);

printf("Element in stack is \n");

for ( i = TOP; i >= 0; i--)
{
printf("\n%d",arr[i]);
}
return 0;
}
void push(int arr[], int size) void pop(int arr[],int size)
{ {
if (TOP >= size -1) if (TOP<= -1)
{ {
printf("full\n"); printf("empty\n");
} }
else else
{ {
int ele; printf("\n%d ele deleted",arr[TOP]);
printf("enter ele : "); TOP--;
scanf("%d",&ele); }
TOP++;
arr[TOP]=ele; }
}

}
Complexity analysis

Operation Time Complexity

PUSH O(1)
POP O(1)

Operation Space Complexity

PUSH O(1)
POP O(1)
Stack permutation
• PUSH order is fix but
• you can pop any time
Total valid stack permutation
Example : n = 3 → 1, 2, 3 2𝑛𝑐𝑛
Total 6 possibilities (3!) =
𝑛+1
i. 1, 2, 3
Catelyn number
ii. 1, 3, 2
iii. 2, 1, 3
iv. 2, 3, 1
v. 3, 1, 2
vi. 3, 2, 1
PUSH order 1, 2, 3
pop order 1, 2, 3

Push(1)
Pop()
Push(2)
Pop() Empty
Push(3) 1
Pop()
PUSH order 1, 2, 3
pop order 1, 3, 2
Push(1)
Pop()
Push(2)
Push(3)
Pop()
Pop()
PUSH order 1, 2, 3
pop order 2, 1, 3

Push(1)
Push(2)
Pop()
Pop()
Push(3)
Pop()
PUSH order 1, 2, 3
pop order 2, 3, 1

Push(1)
Push(2)
Pop()
Push(3)
Pop()
Pop()
PUSH order 1, 2, 3
pop order 3, 1, 2
This is not a valid
Push(1) stack permutation
Push(2)
Push(3)
Pop()
PUSH order 1, 2, 3
pop order 3, 2, 1

Push(1)
Push(2)
Push(3)
Pop()
Pop()
Pop()
Infix, prefix, postfix

• Infix → Operator comes in between operands

• 2+3
• Postfix → Operator comes after operands
• 23+
• Prefix → Operator comes before operands
• +23
Why postfix ?
In infix
i/p : 3 + 4 * 6 / 3 ^ 2 ➔ left to right scan
3 + 4 * 6 / 9 ➔ again, left to right scan
…
multiple scan needed → time consuming
Infix to postfix

• Without using stack

• Using stack
• shortcut
Infix to postfix Without using stack

Example

Input (infix) : 2+3*5 * L to R

+ L to R
2 + [3 5 *]
Output (Postfix) : 2 3 5 *+
Example

Infix : 3+5*6/2^4 ^ R to L
* / L to R
3+5*6/2^4 + - L to R

3 + 5 * 6 / [2 4^]
3 + [5 6*] / [2 4^]
3 + [5 6*24^/]
Postfix: 3 5 6*2 4^/+
Example
Infix : (a + b) * c / d – e ^ f ^ g / h ^ R to L
* / L to R
[ab+] * c / d – e ^ f ^ g / h + - L to R

[ab+] * c / d – e ^ [fg^] / h
[ab+] * c / d – [efg^^] / h
[ab+c*] / d – [efg^^] / h
[ab+c*d/] – [efg^^] / h
[ab+c*d/] – [efg^^h/]
Postfix: ab+c*d/efg^^h/–
Infix to postfix Using stack
➢Important points
• Scan infix expression, if scanned element is operator and stack is empty then
PUSH in stack
• On Scanning infix expression, if scanned element is operator and stack is not
empty and operator at the top of the stack precedence high or same from
current operator than the, the operator at the top of the stack is popped and
added to the output.
• In case of bracket, PUSH left ( into stack and when right ) come then POP all
remaining operator one by one inside ( and )
• When infix expression end then POP operator from TOP of stack one by one
 Examples
Input (infix) : 2+3
input Stack Postfix
Output (Postfix) : 23+ 2 2
+ + 2
3 + 23
23+
Empty

+ TOP
Examples
Input (infix) : 2+3*4
input Stack Postfix
Output (Postfix) : 234*+ 2 2
+ + 2
3 + 23
* +, * 23
Empty * TOP
4 +, * 234
+ TOP +
234*+

Empty

+ TOP
Examples
Input (infix) : a+b-c
input Stack Postfix
Output (Postfix) : ab+c- a a
+ + a
b + ab
- +, - ab+
Empty
c - ab+c
+ TOP + - TOP ab+c-

Empty

- TOP
Examples
Input (infix) : a+b*c/d
input Stack Postfix
Output (Postfix) : abc*d/+ a a
+ + a
b + ab
- +, - ab+
Empty */ TOP
c - ab+c
+ TOP +
ab+c-

Empty TOP
/
+
Examples
Input (infix) : 2+(3*4–6/2)

Output (Postfix) : 234*62/-+

* TOP
Empty ( TOP (
+ TOP + +

/ TOP / TOP
- * - TOP
Empty -
( ( (
+ + +
 input Stack Postfix
2 2
Input (infix) : 2+(3*4–6/2) + + 2
( +, ( 2
Output (Postfix) : 234*62/-+
3 +, ( 23
* +, ( * 23
4 +, ( * 234
- +, ( * - 234*
6 +, ( - 234*6
/ +, ( - / 234*6
2 +, ( - / 234*62
) + 234*62/-
234*62/-+
input
a
Stack Postfix
a
Examples
+ + a
b + ab
* +, * ab
c +, * abc Input (infix) : a+b*c/d–e^f^g+h
/ +, *, / abc*
d +, / abc*d
- +, /, - abc*d/ Output (Postfix) : abc*d/+efg^^-h+
e - abc*d+/e
^ -, ^ abc*d/e
f -, ^ abc*d/ef
^ -, ^, ^ abc*d/ef
g -, ^, ^ abc*d/efg If associative is R to L then same
priority operator also store in
+ -, ^, ^, + abc*d/efg^^- stack
h + abc*d/efg^^-h
abc*d/efg^^-h+
Infix to prefix

• Without using stack

• Using stack
• shortcut
Infix to prefix Without using stack

Example

Input (infix) : a+b*c

a + [*bc]
Output (Prefix) : +a*bc
Example

Infix : a+b*c–d/e^f^g

a + b * c – d / e ^ [^f g]
a + b * c – d / [^e ^f g]
a + [*b c] – d / [^e ^f g]
a + [*b c] – [/d ^e ^f g]
[+a *b c] – [/d ^e ^f g]
– +a *b c /d ^e ^f g
Prefix: – +a *b c /d ^e ^f g
Example

Infix : (a + b * c) – d / (e ^ f ^ g + h)

(a + [*b c]) – d / (e ^ f ^ g + h)
[+a *b c] – d / (e ^ f ^ g + h)
[+a *b c] – d / (e ^ [^f g] + h)
[+a *b c] – d / ([^e ^f g] + h)
[+a *b c] – d / [+^e ^f g h]
[+a *b c] – [/d +^e ^f g h]
Prefix: – +a *b c /d +^e ^f g h
Infix to prefix Using stack
➢Important points
• Reverse the infix expression
• Scan infix expression, if scanned element is operator and stack is empty then
PUSH in stack
• On Scanning infix expression, if scanned element is operator and stack is not
empty and operator at the top of the stack precedence high from current
operator than the, the operator at the top of the stack is popped and added to
the output.
• In case of bracket, PUSH right ) into stack and when left ( come then POP all
remaining operator one by one inside ) and (
• When infix expression end then POP operator from TOP of stack one by one
• Again reverse the output
Examples
Input (infix) : 2+3
Reverse of infix: 3+2 input Stack Postfix
Output : 32+ 3 3
Reverse of output : +2 3 + + 3
2 + 32
3 2+
Reverse +2 3
Empty

+ TOP
 Examples
input Stack Postfix
c c
- - c
infix: a+b-c b - cb
Reverse of infix: c–b+a + -, + cb
Output : cba+- a -, + cba
Reverse of output : -+abc cba+-
Reverse - + a b c

Empty Empty
+ TOP
- TOP -
 Examples
input Stack Postfix
4 4
* * 4
infix: 2+3*4 3 * 43
Reverse of infix: 4*3+2 + *+ 43*
Output : 43*2+ 2 + 43*2+
Reverse of output : +2*34 Reverse +2*3 4

Empty
Empty
* TOP * + TOP + TOP
 Examples input Stack Postfix
(
e ( e
/ (, / e
infix: a + (b * c – d / e)
d (, / ed
Reverse of infix: )e / d – c * b( + a - (, /, - ed/
Output : e d /c b * - a+ c (, - e d /c
Reverse of output : +a - * b c/d e * (, -, * e d /c
b (, -, * e d /c b * -
+ + e d /c b * -
a + e d /c b * -a
e d /c b * -a+
* Reverse +a-*bc/d e
) / - + TOP
 Examples

infix: A + (B * C ^ D ^ E – F) input Stack Postfix

Reverse of infix: )F - E ^ D ^ C * B(+A

Output : FED^C^B*-A+
Reverse of output : +A-*B^C^DEF

TOP
Postfix evaluation
• Infix to postfix : stack → operator
• Postfix evaluation : stack →operand

• In postfix expression when operand comes then it PUSH in to stack

one by one and when operator comes POP two operand from stack
and evaluate and result PUSH in to again stack.
Postfix evaluation using stack

Infix : 2+3*5
Postfix : 235*+ POP 15
POP 5
POP 2
POP 3
15 + 2 = 17
5 * 3 = 15
PUSH 17
PUSH 15

5
Empty 3 3 15
2 2 2 2 17

Answer = 17
Example POP 4 POP 12
POP 3 POP 2
4 * 3 = 12 12 + 2 = 14
Infix : 2+3*4–6/2 PUSH 12 PUSH 14

Postfix : 2 3 4 *+ 6 2 / -

4
Empty
3 3 12
2 2 2 2 14

POP 3 POP 2
POP 14 POP 6
3 / 14 = 11 2/6=3
PUSH 11 PUSH 3
Answer = 11
2
6
3
11 14
14
Postfix evaluation without stack
• In postfix expression go left to right and if operator comes then take
two recent previous operand and evaluate
Example
Postfix : 2 3 4 *+ 6 2 / -
234*+62/-
2 12 + 6 2 / -
14 6 2 / -
14 3 –
11
Prefix evaluation
• Infix to prefix : stack → operator
• Prefix evaluation : stack →operand

• Reverse prefix expression and then perform postfix evaluation means

• when operand comes then it PUSH in to stack one by one and when
operator comes POP two operand from stack and evaluate and result
PUSH in to again stack.
Postfix evaluation using stack
Infix : 2+3*5
Prefix: +2*35 POP 5 POP 2
Postfix : 53*2+ POP 3 POP 15
5 * 3 = 15 2 + 15 = 17
PUSH 15 PUSH 17

Empty 3 2
5 5 15 15 17

Answer = 17
Prefix evaluation without stack
• In prefix expression go right to left and if operator comes then take
two recent previous operand and evaluate
Example
Prefix : +2*35
+2*35
+ 2 15
17
Queue
Queue
• Linear data structure
• Deletion order → order of insertion
• Works on first in first out (FIFO) or first out first in (FOFI)
• insertion and deletion are performed by two pointer REAR & FRONT
• Insertion : REAR
• Deletion : FRONT
• REAR → index of most recently added element
• FRONT → index of element that can be deleted from Queue
• REAR == FRONT == -1 → Queue is empty
Application of Queue
• CPU scheduling
• Spooling
• Synchronization
Enqueue & dequeue
Insert(10)
Insert(20)
Delete()
Insert(30)
Delete()
Insert(40)
Insert(50)
Delete()
 Array implementation
#define SIZE 5
int Queue[SIZE];
int FRONT;
int REAR;

Enqueue & dequeue

Queue is empty
Front = -1
Rear = -1 -1 0 1 2 3 4

Front
Rear
Enqueue Algorithm

1. Check if the queue is full: If the queue is already full, display an error
message and exit.
2. Add the new element to the end of the queue: If the queue is not full, add
the new element to the end of the queue.
3. Update the rear pointer: Move the rear pointer to the newly added
element.
Dequeue Algorithm

1. Check if the queue is empty: If the queue is already empty, display

an error message and exit.
2. Remove the front element from the queue: If the queue is not
empty, remove the front element from the queue.
3. Update the front pointer: Move the front pointer to the next
element in the queue
Front & Rear are same
Case 1: when there is single element in queue
Front = Rear = -1
Case 2: when queue is empty
Front = Rear = -1

When only single element in queue

Enqueue Dequeue
REAR = REAR + 1; REAR = -1;
Queue[REAR] = ele; FRONT = -1;
Enqueue & dequeue (FIFO)
Elements : 10, 20, 30, 40, 50
-1 0 1 2 3 4
Front Rear
Front
Initially -1 -1
Rear
Insert(10) 0 0
Insert(20) 0 1
10
Insert(30) 0 2
-1 0 1 2 3 4
Delete 1 2
Delete 2 2
Front
Insert(40) 2 3 Rear
Insert(50) 2 4
Delete 3 4
Delete 4 4
Complexity analysis

Operation Time Complexity Space Complexity

Enqueue O(1) O(1)
Dequeue O(1) O(1)
Insertion (Enqueue) Implementation
void EnQueue(int ele)
{
if (REAR == SIZE - 1)
{
printf("Overflow");
return ;
}
else if (FRONT == -1)
{
FRONT = 0;
REAR = 0;
}
else
REAR = REAR + 1;

Queue[REAR] = ele;

}
Deletion (Dequeue) Implementation
void DeQueue()
{
int temp;
if (FRONT == -1)
{
return INT_MIN;
}
else if (FRONT == REAR)
{
temp = Queue[FRONT];
FRONT = -1;
REAR = -1;
}
else
{
temp = Queue[FRONT];
FRONT = FRONT + 1;
}
return temp;
}
Disadvantage of simple Queue
Elements : 10, 20, 30, 40, 50, 60
-1 0 1 2 3 4
Front Rear
Front
Initially -1 -1
Rear
Insert(10) 0 0
Insert(20) 0 1
Insert(30) 0 2
Insert(40) 0 3
Insert(50) 0 4
Delete 1 4 40 50
Delete 2 4
-1 0 1 2 3 4
Delete 3 4
Insert(60) Overflow
Front
Because REAR == SIZE - 1 Rear
Circular Queue
• A queue where the last element is connected to the first element,
forming a circle.
• This type of queue is useful when the queue needs to be reused

0
1

0 1 2 3 4 4

3
 Insertion and Deletion in circular Queue
Elements : 10, 20, 30, 40, 50, 60

Front Rear 60 40 50
Initially -1 -1 -1 0 1 2 3 4
Insert(10) 0 0
Insert(20) 0 1 Front
Insert(30) 0 2 Rear
Insert(40) 0 3
Insert(50) 0 4
Delete 1 4
Delete 2 4
Delete 3 4 Enqueue Dequeue
Insert(60) 3 0 rear = (rear+1)%SIZE; front = (front+1)%SIZE
Queue[rear] = ele;
Enqueue in Circular Queue
void insert(int item)
{
if ((rear >= SIZE-1 && front == 0) || front == (rear+1)%SIZE)
{
printf("overflow \n");
return;
}
else if (rear == -1)
{
rear = front = 0;
queue[rear] = item;
}
else
{
rear = (rear+1)%SIZE;
queue[rear] = item;
}

}
Dequeue in Circular Queue
void del()
{
if (front == -1)
{
printf("queue is empty\n");
return;
}
else if (rear == front)
{
int item;
item = queue[front];
rear = front = -1;
printf("%d is deleted=\n",item);
}
else
{
int item;
item = queue[front];
front = (front+1)%SIZE;
printf("%d is deleted\n",item);
}
}
void display()
{
if (front==-1)
{
printf("queue is empty\n");
}
else if (front<=rear)
{
int i;
for ( i = front; i <= rear; i++)
{
printf("%d\n",queue[i]);
}
}
else
{
int i;
for ( i = front; i <= SIZE-1; i++)
{
printf("%d\n",queue[i]);
}
int j;
for ( j = 0; j <= rear; j++)
{
printf("%d\n",queue[j]);
}

}
}
Priority Queue
• A queue where elements are assigned a priority, and the highest-
priority element is removed first.