Course Code: 24CS01TH0202
Course: Data Structures
L: 3 Hrs, P: 0Hr, Per Week
Total Credits: 3
II SEM(CSE)
Section – A2
Course Co-ordinator :
Dr. Shubhangi Neware
Dr. Shubhangi Neware
UNIT-II: Stacks and Queues
Stack ADT: Stack implementation using arrays, Applications of stacks –
expression conversion and evaluation, implementation of multiple stacks,
Real life problem implementation using stacks
Queue ADT: Queue implementation using arrays, Circular queue, Real life
problem implementation using Queue, introduction to double-ended
queues and priority queues.
Dr. Shubhangi Neware
Stack (Linear Data structure)
• Stack ADT allows all data operations at one end only (top).
In stack items may be added and deleted only at one end, called
TOP of stack.
• At any given time, we can only access the top element of a stack.
• This feature makes it LIFO data structure. LIFO stands for Last-in-
first-out. Here, the element which is placed (inserted or added)
last, is accessed first. In stack terminology, insertion operation is
called PUSH operation and removal operation is
called POP operation.
Dr. Shubhangi Neware
Stack Representation
• The following diagram depicts a stack and its
operations –
Dr. Shubhangi Neware
Basic Operations
• Stack operations may involve
Create() [ create empty stack , space allocation and top=-1]
• stack is used for the following two primary operations −
• push() − Pushing (storing) an element on the stack. [insert on top]
• pop() − Removing an element from the stack. [delete from top]
• When data is PUSHed onto stack.
• To use a stack efficiently, we need to check the status of stack as well. For the
same purpose, the following functionality is added to stacks −
• isFull() − check if stack is full. Top=MAX-1
• isEmpty() − check if stack is empty. Top= -1
• peek() − get the top data element of the stack, without removing it. i.e. Top()
traverse() / printstack()
• we maintain a pointer to the last PUSHed data on the stack. As this pointer
always represents the top of the stack, hence named top. The top pointer
provides top value of the stack without actually removing it.
Dr. Shubhangi Neware
• Representation of stack
- using 1D Array [Array representation of stack]
- using Single linked list [ link list representation of stack]
Dr. Shubhangi Neware
Push and pop
MAX=5
Top= -1
Push(2)
Top= -1
Dr. Shubhangi Neware
push(value) - Inserting value into the stack
• In a stack, push() is a function used to insert an element
into the stack. In a stack, the new element is always
inserted at top position. Push function takes one integer
value as parameter and inserts that value into the stack.
We can use the following steps to push an element on to
the stack...
• Step 1 - Check whether stack is FULL. (top == SIZE-1)
• Step 2 - If it is FULL, then display "Stack is FULL!!!
Insertion is not possible!!!" and terminate the function.
• Step 3 - If it is NOT FULL, then increment top value by one
(top++) and set stack[top] to value (stack[top] = value).
Dr. Shubhangi Neware
Algorithm Push( stack, Element)
//Here stack is of size MAX , stack [0…MAX-1]
Dr. Shubhangi Neware
pop() - Delete a value from the Stack
• In a stack, pop() is a function used to delete an element
from the stack. In a stack, the element is always deleted
from top position. Pop function does not take any value
as parameter. We can use the following steps to pop an
element from the stack...
• Step 1 - Check whether stack is EMPTY. (top == -1)
• Step 2 - If it is EMPTY, then display "Stack is EMPTY!!!
Deletion is not possible!!!" and terminate the function.
• Step 3 - If it is NOT EMPTY, then return stack[top] and
decrement top value by one (top--).
Dr. Shubhangi Neware
Algorithm Pop(stack)
// Stack is of size MAX , stack [0…MAX-1]
Return
Dr. Shubhangi Neware
Peek Operation Traverse() - Displays the elements of a Stack
• Peek is an operation that returns the value of • We can use the following steps to display the elements of
a stack.
the topmost
• element of the stack without deleting it from Algorithm Traverse(stack)
the stack.
• Step 1 - Check whether stack is EMPTY.
Algorithm Peek(STACK)
If (top == -1) then
Step 1: IF TOP = -1 Print "Stack is EMPTY!!!" and goto step 3.
PRINT “STACK IS EMPTY” and Goto Step 3 Step 2 - If it is NOT EMPTY, then define a variable 'i' and
initialize with top. Display stack[i] value and
Step 2: RETURN STACK[TOP] decrement i value by one (i--) until i value becomes '0'.
for(int i=top;i>=0;i--)
Step 3: END printf("%d ",stack[i]);
• Step 3 - Stop
Dr. Shubhangi Neware
Stack ADT implementation
Dr. Shubhangi Neware
// Creating a stack // Check if the stack is full
int isfull(st *s) {
struct stack {
if (s->top == s->MAX - 1)
int *A; return 1;
int top; else
return 0;
int MAX; }
};
typedef struct stack st;
void createEmptyStack(st *s) { // Check if the stack is empty
s->A=(int*)malloc(sizeof(s->MAX)); int isempty(st *s) {
s->top = -1; if (s->top == -1)
} return 1;
else
return 0;
}
Dr. Shubhangi Neware
// Add elements into stack
void push(st *s, int newitem) {
if (isfull(s)) {
printf("STACK FULL");
} else {
s->top++;
s->A[s->top] = newitem; // Print elements of stack
} void printStack(st *s) {
} printf("Stack: ");
// Remove element from stack for (int i = s->top; i >=0; i--) {
int pop(st *s) { printf("%d ", s->A[i]);
if (isempty(s)) { }
printf("\n STACK EMPTY \n"); return -1; printf("\n");
} else { }
int x= s->A[s->top];
s->top--;
return (x);
}} Dr. Shubhangi Neware
// Driver code printStack(&s);
int main() int x=pop(&s);
{ printf(" %d\t ", x);
int ch; printf("\nAfter popping out\n");
st s; printStack(&s);
printf("\n enter MAX capacity:"); }
scanf("%d",&[Link]);
createEmptyStack(&s);
push(&s, 1);
push(&s, 2);
push(&s, 3);
push(&s, 4);
push(&s, 4);
push(&s, 4); // if MAX=5 then overflow
Dr. Shubhangi Neware
MULTIPLE STACKS
• If we allocate a large amount of space for the stack, it may result in
sheer wastage of memory.
• So, a better solution to deal with this problem is to have multiple
stacks or to have more than one stack in the same array of sufficient
size. Figure illustrates this concept.
• An array STACK[n] is used to represent two stacks, Stack A and Stack
B.
• The value of n is such that the combined size of both the stacks will
never exceed n.
Dr. Shubhangi Neware
Stack A will grow from left to right, whereas Stack B
will grow from right to left at the same time.
push1(int x) –> pushes x to first stack
push2(int x) –> pushes x to second stack
pop1() –> pops an element from first stack and
return the popped element
pop2() –> pops an element from second stack and
return the popped element
Dr. Shubhangi Neware
• Extending this concept to multiple stacks, a stack can also be used
to represent n number of stacks in the same array. That is, if we
have a STACK[n], then each stack I will be allocated an equal
amount of space bounded by indices b[i] and e[i].
Dr. Shubhangi Neware
Multiple Stack ( 2 stack ) ADT implementation }
}
#include <stdio.h>
// Function to push data into stack2
#define SIZE 10 void push2 (ST *s,int data)
{
typedef struct stack
// checking overflow condition
{ int array[SIZE]; // declaration of array type variable. if (s->top1 == s->top2 - 1)
{
int top1 ; printf ("Stack is full..\n");
}
int top2 ; else
}ST; { s->top2--;
s->array[s->top2] = data;
//Function to push data into stack1
void push1 (ST *s,int data) }
}
{
// checking the overflow condition
if (s->top1 == s->top2 - 1)
{
printf ("Stack is full");
}
else
{ s->top1++;
s->array[s->top1] = data; Dr. Shubhangi Neware
//Function to pop data from the Stack1 s->top2++;
int pop1 (ST *s) return(popped_element);
{
// Checking the underflow condition }
if (s->top1 == -1) }
{
printf ("Stack is Empty \n"); return -1;
//Functions to Print the values of Stack1
} void display_stack1 (ST *s)
else {
{ int i;
int popped_element = s->array[s->top1]; for (i = s->top1; i >= 0; i--)
s-> top1--; {
return(popped_element); printf ("%d ", s->array[i]);
} }
} printf ("\n");
// Function to remove the element from the Stack2 }
int pop2 (ST *s) // Function to print the values of Stack2
{ void display_stack2 (ST *s)
// Checking underflow condition {
if (s->top2 == SIZE) int i;
{ for (i = s->top2; i < SIZE; i++)
printf ("Stack is Empty!\n"); return -1; {
} printf ("%d ", s->array[i]);
else }
{ printf ("\n");
int popped_element = s->array[s->top2]; }
Dr. Shubhangi Neware
APPLICATIONS OF STACKS ARE:
Typical problems where stacks can be easily applied for a
simple and efficient solution includes:
• Reversing a list /string
• Parenthesis checker
• Conversion of an infix expression into a postfix
expression
• Evaluation of a postfix expression
• Conversion of an infix expression into a prefix
expression
• Evaluation of a prefix expression
• Recursion
• Tower of Hanoi
Dr. Shubhangi Neware
Evaluating arithmetic expressions:
INFIX notation:
The general way of writing arithmetic
expressions is known as infix notation.
e.g, (a+b)
PREFIX notation:
e.g, +AB
POSTFIX notation:
(suffix)
e.g: AB+
Dr. Shubhangi Neware
Prefix (polish notation)
• In prefix notation the operator proceeds the two operands. i.e.
the operator is written before the operands.
<operator><operand><operand>
infix prefix
2+3 +23
p-q -pq
a+b*c +a*bc
Dr. Shubhangi Neware
Postfix (Reverse Polish Notation)
/ suffix notation
• In postfix notation the operators are written after the operands
so it is called the postfix notation (post means after).
<operand><operand><operator>
infix postfix
2+3 23+
p-q pq-
a+b*c abc*+
Human-readable Good for machines
Dr. Shubhangi Neware
%(MOD)
Dr. Shubhangi Neware
Algorithm to convert infix expression to postfix expression using stack
Dr. Shubhangi Neware
Algorithm for evaluation of postfix/suffix expression
using stack
Dr. Shubhangi Neware
• Remember for Infix to postfix ( when to perform pop() ????)
1. if precedence of operator on stack [top]>=precedence of symbol(operator) scanned then pop operator
from stack and add operator to P i.e postfix expression
2. If scanned symbol ‘)’ encountered check for corresponding ‘(‘ in stack and pop all operators and add
operators to P i.e postfix expression.
Example solved in class : A+B*(C^D-E)
Dr. Shubhangi Neware
Convert infix expression A+(B*C-(D/E^F)*G)*H into its equivalent
postfix expression . A+(B*C-(D/E^F)*G)*H )
Dr. Shubhangi Neware
Dr. Shubhangi Neware
Evaluation of postfix expression (solved in class)
Here 2 is
operand2 and 6 is
operand 1
Dr. Shubhangi Neware output
To do
1) Convert A/(B-C)*D+E to postfix and evaluate postfix expression for
A=50 ,B=70,C=60,D=2,E=6
2) Convert infix to postfix (A+B) * C – ( D- E) * (F+G)
Evaluate postfix expression for
A=10 B=20 C=5 D=50 E=40 F=5 G=6
Dr. Shubhangi Neware
Postfix Expression
A/(B-C)*D+E
Add ) to end of Expression
and push ( to stack
( A/(B-C)*D+E
Dr. Shubhangi Neware
Dr. Shubhangi Neware
(A+B) * C – ( D- E) * (F+G)) Symbol Stack Postfix Expression Remark
(
( ((
A (( A
+ ((+
B ((+ AB
) ( AB+ Pop +
* (*
C (* AB+C
- (- AB+C* Pop * as priority of * is
grt than -
( (-( AB+C*
D (-( AB+C*D
Postfix
- (-(- AB+C*D
AB+C*DE-FG+*-
E (-(- AB+C*DE
) (- AB+C*DE- Pop -
* (- * AB+C*DE-
( (-*( AB+C*DE-
F (-*( AB+C*DE-F
+ (-*(+ AB+C*DE-F
G (-*(+ AB+C*DE-FG
) (-* AB+C*DE-FG+ Pop +
Dr. Shubhangi Neware
) empty AB+C*DE-FG+*- POP *- END
Remember for Infix to prefix ( when to perform pop() ????)
Here stack1 and stack2 are used
1. if precedence of operator on stack1 [top]>precedence of symbol(operator) scanned
then pop operator from stack1 and add operator to stack2
2. If scanned symbol ‘(’ encountered check for corresponding ‘)‘ in stack1 and pop all
operators and add operators to stack2.
finally perform pop() on stack2 until it becomes empty. And put in prefix expression
Dr. Shubhangi Neware
Solved in class: conversion of infix to prefix
Dr. Shubhangi Neware
Answer (pop all symbols stack 2) : +-+A**BC+*M^NPTGH is equivalent prefix
Infix:
A/(B-C)*D+E
Output: prefix:
+*/A-BCDE
solved in class
Dr. Shubhangi Neware
Given prefix expression P: - * 3 + 16 2 / 12 6 Evaluate
Scan P from right to left
Symbol scanned Stack Action performed
6 6 Push operand 6 into stack
12 6,12 Push operand 12 into stack
/ Empty / encountered Pop 12 and 6
Perform 12/6
2 push result 2 on stack
2 2 2 Push operand 2 into stack
16 2 2 16 Push operand 16 into stack
+ 2 18 + operator encountered
Pop 16 and 2 Perform 16+2
Push result on stack
3 2 18 3 Push operand 3 into stack
* 2 54 Operator * encountered
Pop 3 and 18 , perform 3*18 , push result 54 onto stack
top
- 52 Operator - encountered
Pop 54 and 2 , perform 54-2 , push result 52 onto stack
top
Dr. Shubhangi Neware
All symbols are scanned then stop Empty stack Result : 52
APPLICATIONS OF STACKS ARE:
I. Reversing Strings:
• A simple application of stack is reversing strings.
To reverse a string , the characters of string are
pushed onto the stack one by one as the string
is read from left to right.
• Once all the characters
of string are pushed onto stack, they are
popped one by one. Since the character last
pushed in comes out first, subsequent pop
operation results in the reversal of the string.
Dr. Shubhangi Neware
For example:
To reverse the string ‘REVERSE’ the string is read from left to right and its
characters are pushed . LIKE:
onto a stack.
void reverse(char str[],int n)
{
int n,i;
for (i = 0; i < n; i++)
push(&s, str[i]);
// Pop all characters of string and
// put them back to str
for (i = 0; i < n; i++)
str[i] = pop(&s);
}
Dr. Shubhangi Neware
II. Checking the validity of an expression
containing nested parenthesis:
• Stacks are also used to check whether a given
arithmetic expressions containing nested
parenthesis is properly parenthesized.
• The program for checking the validity of an
expression verifies that for each left parenthesis
braces or bracket ,there is a corresponding
closing symbol and symbols are appropriately
nested.
Dr. Shubhangi Neware
For example: 1. Initialize an empty stack to store opening parentheses
encountered while iterating through the string.
VALID INVALID 2. Iterate through each character of the input string
from left to right.
INPUTS INPUTS 3. For each character encountered:
- If it is an opening parenthesis (‘(‘, ‘[‘, ‘{‘), push it
onto the stack.
{} {(} 4. if it is a closing parenthesis (‘)’, ‘]’, ‘}’):
- if the stack is empty. If it is, return false since there is no
({[]}) ([(()]) matching opening parenthesis for the current closing
parenthesis
else pop the top element from the stack and compare it
with the current closing parenthesis:
-if they match (i.e., the current closing parenthesis
corresponds to the top of the stack), continue to the next
{[]()} {}[]) character.
- if they do not match, return false since there is a
[{)}(]}] mismatch in parentheses.
-5. After iterating through the entire string, if the stack is
empty, return true since all parentheses were properly
matched.
6. If the stack is not empty at the end, return false since
thereNeware
Dr. Shubhangi are unmatched opening parentheses.
Dr. Shubhangi Neware
#include <stdio.h>
#include <stdlib.h> Program for valid // Function to pop a character from the stack
parenthesis checker char pop() {
#include <string.h>
if (top == -1) {
printf("Empty stack!\n");
#define MAX_SIZE 100
return ' ';
}
// Global variables for stack and top char data = stack[top];
char stack[MAX_SIZE]; top--;
int top = -1; return data;
}
// Function to push a character onto the stack // Function to check if two characters form a matching pair of parentheses
void push(char data) { int is_matching_pair(char char1, char char2) {
if (top == MAX_SIZE - 1) { if (char1 == '(' && char2 == ')') {
printf("Overflow stack!\n"); return 1;
return; } else if (char1 == '[' && char2 == ']') {
} return 1;
top++; } else if (char1 == '{' && char2 == '}') {
stack[top] = data; return 1;
} } else {
return 0;
}}
Dr. Shubhangi Neware
if (top == -1) {
// Function to check if the expression is balanced return 1; // If the stack is empty, the expression is balanced
int isBalanced(char* text) { } else {
int i; return 0; // If the stack is not empty, the expression is not balanced
for (i = 0; i < strlen(text); i++) { }
if (text[i] == '(' || text[i] == '[' || text[i] == '{') { }
push(text[i]); // Main function
} else if (text[i] == ')' || text[i] == ']' || text[i] == '}') { int main() {
if (top == -1) { char text[MAX_SIZE];
return 0; // If no opening bracket is present printf("Input an expression in parentheses: ");
} else if (!is_matching_pair(pop(), text[i])) { scanf("%s", text);
return 0; // If closing bracket doesn't match the last opening
bracket
// Check if the expression is balanced or not
}
if (isBalanced(text)) {
}
printf("The expression is balanced.\n");
}
} else {
printf("The expression is not balanced.\n");
}
return 0;
}
Dr. Shubhangi Neware
Application of stack
The Tower of Hanoi is a mathematical puzzle. We have
three rods and n number of disks. The objective of the
puzzle is to move the entire stack to another rod, obeying
the following simple rules:
•Only one disk can be moved at a time.
•Each move consists of taking the upper disk from one of
the stacks and placing it on top of another stack i.e. a disk
can only be moved if it is the uppermost disk on a stack.
•No disk may be placed on top of a smaller disk.
Moving 3 disks from A to C via B
When n = 3, source = A, destination = C, auxilliary = B,
[Link] 3 from A to C.
[Link] 2 from A to B.
[Link] 3 from C to B → Disk 2 and 3 Placed at B.
[Link] 1 from A to C → Disk 1 Placed at C.
[Link] 3 from B to A.
[Link] 2 from B to C
[Link] 1 from A to C → Disk 2 and 3 Placed at C.
Dr. Shubhangi Neware
Q1. Convert the following expression to prefix expression using stack
A+B-(C*D/F+G^(H/L*M-K))
[Link] a Stack ADT is already created. Write a function to check
whether the parentheses are balance or not.
Balanced Parentheses : ( ( ) ( ) ( ( ) ) )
Unbalanced Parentheses: ( ( ) ( ) ( ( ) )
Q3
Q4. Suppose that you are part of a team developing a financial application.
One of the functions used in the application is a calculator, for infix arithmetic
expressions. Write an algorithm for this calculator function using two stacks.
Trace the stack content to solve the following expression —
5 * (((9 + 8) *(4 * 6)) + 7)
Dr. Shubhangi Neware
2 (a) Convert the following expression to prefix expression using
stack
A+B-(C*D/F+G^(H/L*M-K))
Dr. Shubhangi Neware
Write an algorithm
- to convert infix to postfix
-to convert infix to prefix
-to evaluate postfix
-to evaluate prefix
Dr. Shubhangi Neware