Stack
A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. A
stack has only one end known as top of the stack. Stack can also be defined as a container
in which insertion(push) and deletion(pop) can be done from the one end only i.e. the top
of the stack
Stack
Basic Operations:
push() − Inserting an element on the stack.
pop() − Removing an element from the stack.
To check the status of stack, the following functionality is added to stack
peek() − get the top data element of the stack, without removing it.
isFull() − check if stack is full.
isEmpty() − check if stack is empty.
Q. Program to implement stack using array
#include <stdio.h>
#include <conio.h>
const int MAXSIZE = 5;
int stack[MAXSIZE];
int top = -1;
int isEmpty()
{
if(top == -1)
return 1;
else
return 0;
}
int isFull()
{
if(top == MAXSIZE-1)
return 1;
else
return 0;
}
int peek()
{
return stack[top];
}
int pop()
{
int data;
if(isEmpty())
{
printf("Stack is empty!");
return 0;
}
else
{
data = stack[top];
top = top - 1;
return data;
}
}
void push(int data)
{
if(isFull())
{
printf("Stack is full!\n");
}
else
{
top = top + 1;
stack[top] = data;
}
}
void main()
{
clrscr();
int data;
// push elements on to the top of the stack
push(3);
push(5);
push(9);
push(1);
push(12); // top=4
push(15); // Stack is full
push(100); // Stack if full
printf("\nElement at top of stack is %d\n" ,peek());
printf("Elements are: \n");
// print stack data
while(!isEmpty())
{
data = pop();
printf("%d\n",data);
}
data=pop(); // Stack is empty
getch();
}
Output:
Q. Program to implement stack using linked list
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct NODE
{
int data;
struct NODE *next;
}*head;
void push()
{
intval;
struct NODE *ptr = (struct NODE*)malloc(sizeof(struct NODE));
if(ptr == NULL)
{
printf("Could not push element!");
}
else
{
printf(" Enter the value:");
scanf("%d",&val);
if(head==NULL)
{
ptr->data = val;
ptr -> next = NULL;
head=ptr;
}
else
{
ptr->data = val;
ptr->next = head;
head=ptr;
}
printf(" The element %d is pushed!\n",val);
}
}
void pop()
{
int item;
struct NODE *ptr;
if (head == NULL)
{
printf(" Stack is Empty!");
}
else
{
item = head->data;
ptr = head;
head = head->next;
free(ptr);
printf(" Item %d is popped",item);
}
}
void display()
{
struct NODE *ptr;
ptr=head;
if(ptr == NULL)
{
printf(" Stack is empty!\n");
}
else
{
printf("The Stack elements are...\n");
while(ptr!=NULL)
{
printf("%d\n",ptr->data);
ptr = ptr->next;
}
}
}
void main ()
{
clrscr();
int choice=0;
while(choice != 4)
{
printf("\n---------MENU--------");
printf("\n Push 1");
printf("\n Pop 2");
printf("\n Show 3");
printf("\n Exit 4");
printf("\n Enter your choice->");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("Exiting...");
break;
}
default:
{
printf("Enter a valid choice!");
}
};
}
getch();
}
Output:
Applications of Stack:
1. Evaluation of Arithmetic Expressions
2. Backtracking
3. Delimiter Checking
4. Reverse a Data
5. Processing Function Calls
Infix, prefix and post expression:
The way of writing an arithmetic expression is known as a [Link] arithmetic expression
such as A*B, where the variable A is being multiplied by the variable [Link] the
multiplication operator * appears between A and B in the expression, therefore, this type of
expression is referred to as infix expression since the operator is in between the two operands.
Prefix expression requires that the operator precede the two operands that they work on. An
arithmetic expression such as A*B is written as *AB in prefix notation. Similarly the infix
expression A + B * C will be + A*BC in prefix [Link] notation is also known as Polish
Notation.
Postfix, on the other hand, requires that its operator come after the corresponding operands. An
arithmetic expression such as A*B is written as AB* in postfix notation. And the infix
expression A + B * C will be ABC*+ in postfix [Link] notation is known as Reversed
Polish Notation.
Examples of Infix, Prefix, and Postfix expressions
Infix Expression Prefix Expression Postfix Expression
A+B*C+D ++A*BCD ABC*+D+
(A + B) * (C + D) *+AB+CD AB+CD+*
A*B+C*D +*AB*CD AB*CD*+
A+B+C+D +++ABCD AB+C+D+
A/ B + C / D + / AB / CD AB / CD / +
(A + B) * (C + D) * + AB + CD AB + CD + *
((A + B) * C) –D - * + ABCD AB + C * D -
We follow the operator and precedence and associativity rule wile converting infix to prefix
and postfix expression.
Expression Tree:
Expression tree is a binary tree in which each internal node corresponds to the operator and
each terminal node corresponds to the operand. For example the expression tree for 3+(5+9)*2
is as follows
3 *
+ 2
5 9
Infix to postfix conversion:
Infix Expression: A+ (B*C-(D/E^F)*G)*H, where ^ is an exponential operator.
We add one ‘)’ to the end of the given expression i.e. A+ (B*C-(D/E^F)*G)*H)
Resultant Postfix Expression: ABC*DEF^/G*-H*+
Algorithm for Infix to Postfix conversion:
1. Push ‘(‘ on the stack and add ‘)’ to the end of the given infix expression.
2. Scan each character from left to right of the given infix expression
3. If an operand is encountered, Output it to the postfix expression.
4. If a left parenthesis is encountered, Push it on to the stack
5. If a right parenthesis is encountered, then:
Pop the top elements and output it to the postfix expression until ‘(’ is
encountered. Pop ‘(’ from the stack but don’t output.
6. If operator is encountered, then:
If top of the stack is not an operator,
Push the scanned operator to the stack.
Else,
If precedence of the scanned character is less than or equal to the
operator at top of the stack, then:
Pop the top of the stack and output in postfix expression.
Push the scanned character on top of the stack
Else,
Push the scanned character on top of the stack.
Endif
Endif
Ex: Convert the infix ((A + B) * C) – D to postfix expression:
We add one ‘)’ to the end of the given expression i.e. ((A + B) * C) – D)
S. No. Scanned Stack Postfix Expression
1 (
2 ( ((
3 ( (((
4 A ((( A
5 + (((+ A
6 B (((+ AB
7 ) (( AB+
8 * ((* AB+
9 C ((* AB+C
10 ) ( AB+C*
11 - (- AB+C*
12 D (- AB+C*D
13 ) Empty AB+C*D-
Result:AB+C*D-
Infix to Prefix Conversion:
1. Reverse the infix expression, while keeping the positions of parentheses correct.
2. Replace ‘(‘ with ‘)’ and vice-versa.
3. Convert the reversed expression to postfix using a stack using the following algorithm
a. Push ‘(‘ on the stack and add ‘)’ to the end of the given infix expression.
b. Scan each character from left to right of the given infix expression
c. If an operand is encountered, Output it to the postfix expression.
d. If a left parenthesis is encountered, Push it on to the stack
e. If a right parenthesis is encountered, then:
i. Pop the top elements and output it to the postfix expression until ‘(’ is
encountered. Pop ‘(’ from the stack but don’t output.
f. If operator is encountered, then:
If top of the stack is not an operator,
Push the scanned operator to the stack.
Else,
If precedence of the scanned character is less than or equal to the
operator at top of the stack, then:
Pop the top of the stack and output in postfix expression.
Push the scanned character on top of the stack
Else,
Push the scanned character on top of the stack.
Endif
Endif
4. Finally, reverse the postfix expression to get the prefix expression.
Example: Convert the infix expression (A + B) * (C - D) to prefix expression.
Infix: (A + B) * (C - D)
• Step 1: Reverse the expression and Swap ‘(‘ with ‘)’ and vice versa →(D-C)*(B+A)
• Step 2: Convert to postfix as usual → DC - BA + *
• Step 3: Reverse → * + A B - C D
Input : (D-C)*(B+A) )
Sr. No Scanned Stack Postfix expression Remarks
1 (
2 ( ((
3 D (( D
4 - ((- D
5 C ((- DC
6 ) ( DC-
7 * (* DC-
8 ( (*( DC-
9 B (*( DC-B
10 + (*(+ DC-B
11 A (*(+ DC-BA
12 ) (* DC-BA+
13 ) Empty DC-BA+*
Reversing this postfix to get prefix expression: *+AB-CD
Evaluation of postfix Expression:
It is not a very efficient to design an algorithm to parse infix notations for computation by the
compiler as compiler scans from left to right. Instead, these infix notations are first converted
into either postfix or prefix notations and then computed.
Algorithm for Postfix expression evaluation:
Postfix_Evaluation
Begin
for each character ch in the postfix expression, do
if ch is an operator ⨀in postfix expression, then
a := pop first element from stack
b := pop second element from the stack
result := b ⨀ a
push result into the stack
else if ch is an operand, then
push ch into the stack
endfor
return the element on stack top
End
Example: Evaluation of Postfix expression: 23+45+*
Step No Token Action Stack status
1 2 Push 2 to the stack [2]
2 3 Push 3 to the stack [2, 3]
3 + Pop 3 from the stack [2]
Pop 2 from the stack []
Push 2+3=5 on the stack [5]
4 4 Push 4 to the stack [5,4]
5 5 Push 5 to the stack [5, 4, 5]
6 + Pop 5 from the stack [5, 4]
Pop 4 from the stack [5 ]
Push 4+5=9 on the stack [5, 9]
7 * Pop 9 from the stack [5]
Pop 5 from the stack []
Push 5*9=45 on the stack [45]
8 Pop result from the stack and
display.
Result=45
Q. Evaluate the following postfix expression:
Postfix: 2536+**5/2-
Result: 16
Recursion
Recursion is a technique where a function a calls itself. Recursion involves several numbers of
recursive calls. However, it is important to impose a termination condition of recursion. A
recursive function performs the tasks by dividing it into the subtasks. There is a termination
condition defined in the function which is satisfied by some specific subtask. The case at which
the function doesn't recur is called the base case.
If a function calls itself then it is a direct recursion. But if the function calls another
functions and then that function calls back the original function then it is called indirect
recursion.
(i) Head recursion: If a recursive function calling itself is the first statement in the
function then it’s known as Head Recursion.
(ii) Tail recursion: If a recursive function calling itself is the last statement in the
function then it’s known as Tail Recursion.
(iii) Nested recursion: One function call is nested by another call
int test(int n)
{
if(n>0)
{
printf("Hi\n");
return test(test(n-3));
}
else
return 0;
}
void main()
{
clrscr();
test(3);
getch();
}
Output: Hi
(iv) Tree recursion:
void test(int n)
{
if(n>0)
{
test(n-1);
printf(“%d “,n);
test(n-1);
}
}
void main()
{
test(3);
}
Output:1 2 1 3 1 2 1
Tower of Hanoi:
The Tower of Hanoi also known as the Tower of Brahma or the Lucas Tower, is a mathematical
puzzle that consists of three pegs with ’n’ number of disks of different diameters.
The objective is to shift the entire stack of disks from source peg to the destination peg
following the three rules:
• Only one disk can be moved at a time.
• Only the topmost disk from one stack can be moved on to the top of another stack or
an empty peg.
• Larger disks cannot be placed on the top of smaller disks.
Our task is to move all the disks to destination. The steps would be:
• First, we move the smaller (top) disk from source to aux peg.
• Then, we move the larger (bottom) disk from source to destination peg.
• And finally, we move the smaller disk from aux to destination peg.
Source Auxiliary Destination
So now, we are in a position to design an algorithm for Tower of Hanoi with more than two
disks. We divide the stack of disks in two parts. The largest disk (nth disk) is in one part and all
other (n-1) disks are in the second part.
The steps for n number of disks would be as follows
Step 1 :Move n-1 disks from source to aux
Step 2 : Move nth disk from source to destination
Step 3 : Move n-1 disks from aux to destination
Algo TowerOfHanoi(n, source, dest, aux)
If n>0
Tower(n-1, source, aux, dest)
Print “Move nthdisk from source to destination”
Tower(n-1, aux, dest, source)
Endif
Example: Tower of Hanoi with n=3 disks. Show each move required.
Note: Disk 1 now at the top, Disk 2 in the middle, Disk 3 at the bottom.
1. Move disk 1 from S to D.
2. Move disk 2 from S to A.
3. Move disk 1 from D to A.
4. Move disk 3 from S to D.
5. Move disk 1 from A to S.
6. Move disk 2 from A to D.
7. Move disk 1 from S to D
Tower of Hanoi with n disks can be solved in minimum 2n -1 steps. This example shows that
a puzzle with 3 disks has taken 23 - 1 = 7 steps.
Implementation of Tower of Hanoi.
#include <stdio.h>
#include <conio.h>
void towerOfHanoi(int n, char from[], char to[], char aux[])
{
if (n >0)
{
towerOfHanoi(n-1, from, aux, to);
printf("\n Move disk %d from peg %s to peg %s", n, from, to);
towerOfHanoi(n-1, aux, to, from);
}
}
void main()
{
clrscr();
int n;
printf("Enter the number of disks:");
scanf("%d",&n); // Number of disks
towerOfHanoi(n,"source", "dest", "aux"); // names of the pegs
getch();
}
Complexity of Tower of Hanoi:
Total time taken can be expressed with recurrence relation, T(n) = T(n-1)+ 1 + T(n-1)
T(n) = 2T(n-1) + 1———- (1)
Now, putting n = n-1 in eq 1, we will get
T(n-1) = 2T(n-2) + 1——— (2)
Again, putting n = n-2 in eq 1, we get
T(n-2) = 2T(n-3) + 1——— (3)
Putting the value of T(n-2) in the eq2. we get
T(n-1) = 2(2T(n-3) + 1) + 1 -----------(4)
Putting the value of T(n-1) from eq4 in eq1, we get
T(n) = 2(2(2T(n-3)+1)+1)+1
T(n) = 23T(n-3) + 22 + 21 + 1
After Generalization,
T(n) = 2k T(n-k) + 2(k-1) + 2(k-2) + ………. + 22 + 21 + 20
From our base condition T(1) =1.[ i.e. with 1 disk, 1 unit of time will be consumed ]
n–k=1
=>k = n-1
Now put k = n-1 in above equation,
T(n) = 2k T(n-(n-1)) + 2(k-1) + 2(k-2) + ………. + 22 + 21 + 20
T(n) = 2k T(1) + 2(k-1) + 2(k-2) + ………. + 22 + 21 + 20
T(n) = 2k .1 + 2(k-1) + 2(k-2) + ………. + 22 + 21 + 20
T(n) =20 + 21 + 22+ … + 2(k-2) + 2(k-1) + 2k [ Rearranging]
It is in a GP with common ratio r = 2
First term, a=20=1
Sum of G.P. = Sn = a(1-rn) / (1-r)
T(n) = 1.(1-2k+1))/(1-2) [ There are total k+1 terms in the GP series]
T(n) = 2(k+1) – 1
From the above equation,
T(n) = 2 (n-1+1) – 1
T(n) = 2n – 1
Time Required: 2n – 1
T(n)= O( 2n – 1) , or We can say time complexity is O(2n)