Stack
1
Stack
• Stack is a non-primitive linear data structure
wherein insertion and deletion is always
done from one end known as top of stack
(TOS).
• Stack operates on LIFO (Last In First Out)
principle. Hence, the item inserted in last is
deleted first.
• It is called ‘Stack’ as it behaves like a real-
world stack (pile) of plates, books, discs,
coins etc.
• Stack is an ordered collection of elements
like array, but it has a special feature that
insertion and deletion of elements can be
done from only top end
Ref: [Link] 2
Stack Operations
Some common operations implemented on the stack:
• push(): Inserting an element into the stack. If the stack is full then the overflow condition occurs.
• pop(): Deleting an element from the stack. If the stack is empty then underflow condition occurs.
• isEmpty(): To determine whether the stack is empty or not. Returns true if stack is empty, else false.
• isFull(): To determine whether the stack is full or not. Returns true if stack is full, else false.
• peek(): Returns the top element of the stack.
• count(): Returns the total number of elements available in a stack.
• display(): Prints all the elements present in the stack.
3
PUSH Operation
1. Before inserting an element check if the
stack is full or not.
• If the stack is full, then the overflow
condition occurs.
2. On initialization top is set to -1.
3. When a new element is pushed into the
stack,
• the value of the top gets
incremented, i.e., top=top+1, and
• the element gets placed at the new
position of the top.
4. The elements will be inserted until we
reach the max size of the stack.
Note: TOS increases in push operation
Ref: [Link] 4
POP Operation
1. Before deleting an element check if the
stack is empty or not.
• If the stack is empty, then the
underflow condition occurs.
2. On initialization top is set to -1.
3. If the stack is not empty, access the
element which is pointed by the top.
4. Once the pop operation is performed, the
top is decremented by 1, i.e., top=top-1.
5. The elements will be deleted until top
becomes -1.
Note: TOS decreases in pop operation
Ref: [Link] 5
Stack Implementation
There are two ways to implement stacks:
1. Static – using Array
• Once array size is declared, it can’t be changed during program execution.
• Memory utilization is inefficient - if the number of elements stored is less than array size, then memory is
wasted.
• Suitable only when the exact number of elements to be stored is known.
2. Dynamic – using Linked List
• Stack size can be modified during program execution.
• Memory utilization is efficient - stack size can be increased or decreased at run time as per requirement.
• There is no restriction on the number of elements.
6
Static Implementation of Stack using Array
#include <iostream>
using namespace std; int main()
{
#define STACK_SIZE 10 int j;
int tos = -1; push(1);
int a[STACK_SIZE]; push(2);
push(3);
pop();
push(4);
push(5);
pop();
cout<<"\n Items in the stack are:
";
if(tos==-1)
cout<<"\n Stack is empty";
else {
for(j=tos; j>=0; j--)
cout<<a[j]<<" ";
}
return 0;
}
7
Static Implementation of Stack
Output
8
Dynamic Implementation of Stack
Insertion Deletion
9
Dynamic Implementation of Stack
void push(int data) // insert at beginning
#include <iostream> {
using namespace std; stk_node* new_node = new stk_node();
new_node->data = data;
class stk_node { new_node->next = head;
public: head = new_node;
int data; cout << data << " pushed to stack\n";
}
stk_node *next;
};
int pop() // delete at beginning
{
stk_node *head=NULL, *temp=NULL; if (isEmpty()) {
cout << " Stack Underflow";
int isEmpty() return 0;
{ }
return !head; temp = head;
} head = head->next;
int x = temp->data;
cout << x << " popped from stack\n";
free(temp);
return x;
}
10
Dynamic Implementation of Stack
int main()
{ Output
push(1);
push(2);
push(3);
pop();
push(4);
push(5);
pop();
cout<<"\nItems in the stack are: ";
temp = head;
while(temp != NULL)
{
cout<< temp->data << " ";
temp = temp->next;
}
return 0;
}
11
Recursion working using stack
Every time a function is called (recursive or not), the runtime creates a stack frame and pushes it onto the call
stack.
Each stack frame stores:
1. Return address (where to go back after function finishes) fact(5)
2. function parameters
3. Local variables
4. Saved registers / previous stack pointer
For Factorial program
int fact(int n) {
if (n == 0)
return 1; → 5* fact(4)
return n * fact(n - 1); → fact(3)
} → fact(2)
int main() { → fact(1)
int ans = fact(5); → fact(0)
}
12
Recursion working using stack
In the stack frame of fact(n):
n (parameter),
Return address (where to continue after fact(n-1)) and
Bookkeeping info (saved registers, stack pointer)
Example:
2000 x= CALL fact (1) ; jumps to fact(1)
2004 IMUL x, 2 ; ← return address points HERE
2008 RET
13
Infix to Postfix conversion using Stack
1. Initialize the Stack.
2. Scan the infix expression from left to right.
3. If the scanned character is an operand, output it.
4. Else,
1. If the precedence of the scanned operator is greater than that of the operator in the stack [or the stack is
empty or the stack contains a ( symbol], then push the operator into the stack.
2. Else, pop all the operators from the stack which are greater than or equal to in precedence than that of the
scanned operator. Thereafter, push the scanned operator to the stack. (If you encounter parenthesis while
popping then stop there and push the scanned operator in the stack.)
5. If the scanned character is an ‘(‘, push it to the stack.
6. If the scanned character is an ‘)’, pop the stack and output it until a ‘(‘ is encountered, and discard both the
parenthesis.
7. Repeat steps 2-6 until the complete infix expression is scanned.
8. Print the stack output.
9. Pop and output all characters from the stack until it is not empty.
14
(a+(b*c-(d/e-f)*g)*h)
Infix to
Postfix I Stack P
a ( a
conversion + (+ a
using Stack ( (+( a I Stack P
b (+( ab ) (+(- abc*de/f-
* (+(* ab * (+(-* abc*de/f-
c (+(* abc
g (+(-* abc*de/f-g
- (+(- abc*
) (+ abc*de/f-g*-
( (+(-( abc*
* (+* abc*de/f-g*-
d (+(-( abc*d
h (+* abc*de/f-g*-h
/ (+(-(/ abc*d
e (+(-(/ abc*de
) abc*de/f-g*-h*+
- (+(-(- abc*de/
f (+(-(- abc*de/f
15
Evaluating a Postfix expression using Stack
Let P is expression in postfix notation. Following steps provide procedure to evaluate P.
1. Add a symbol ‘#’ at the end of postfix expression P.
2. Scan symbol left to right from P and repeatedly execute steps 3 and 4 until the symbol ‘#’ is encountered.
3. If the scanned symbol is an operand then push the symbol into stack.
4. If the scanned symbol is an operator, say Θ, then.
1. Pop two items from stack.
2. Store top item in A and next to top item in B.
3. Perform C=B ΘA
4. Push C into stack
5. Repeat steps 2-4 until the complete expression is scanned.
6. Set result = item on the top of stack.
16
Evaluating the Postfix expression PQ+R*S/ where P=2, Q=3,R=4 and S=5
17
Infix to prefix (steps)
[time and space complexity (O(n))
1. When a new operator appears, compare it with the operator on top of the stack.
2. Pop operators from the stack if they have higher precedence, or if they have equal
precedence and the new operator is right-associative (^). Left-associative operators (+, -, *, /)
do not cause a pop.
3. Push the new operator onto the stack.
4. For parentheses (when scanning right to left), push ')' onto the stack, and when '(' is
encountered, pop operators until a ')' is found.
5. At the end, pop all remaining operators from the stack and add them to the result.
6. Finally, reverse the result to obtain the correct prefix expression.
OR
1. Prefix = reverse( postfix( reverse(infix) ) )
18
Infix to prefix (steps) : Approach 2
[time and space complexity (O(n))
Prefix = reverse( postfix( reverse(infix) ) ) or
1. Reverse the infix expression
2. Swap brackets
3. Convert the new expression to postfix (using stack)
4. Reverse postfix → prefix
19
Useful References
• [Link]
• [Link]
• [Link]
• [Link]
• [Link]
20