.png)
Mobiprep has created last-minute notes for all topics of Stacks to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Stacks.
Data Structure
Linked List
Doubly Linked List
Circular Linked List
Queues
Stacks
Hashing and Searching
Sorting
Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.
Question 1 - What is a Stack Data Structure?
Answer - A stack is a linear ordered Abstract Data Type (ADT) in which all the insertions and deletions are done on the same end called top. It follows the Last In First Out (LIFO) or First In Last Out (FILO) order. i.e., the first element inserted is the last to be deleted (or) the last element inserted is the first to be removed from the stack. The concept of stacks can be clearly explained using the example of a pile of plates. The plate which is kept first is taken out at last.
So if you want to remove the yellow plate, you need to pick black and red plate.
Question 2 - What are the different operations that can be performed on Stack?
Answer - The two main operations that can be performed on the stack are push and pop.
Push: Inserting an element into the stack is called push operation.
Pop: Deleting or removing an element from the stack is called the pop operation
Traverse: Traversing operation involves processing all the elements of the stack and printing them (or performing some other operation).
For example, consider the stack as follows:
Thus, removing 22 implies, pop the element 22.
Similarly, adding implies push the element 55.
The order as clear is Last in, First Out(LIFO) or First in, Last Out(FILO).
The other auxillary stack operations that can be performed on the stack are:
top(): returning the element indicated by the top pointer
size(): Number of elements in the stack is returned
isEmpty(): checks whether the stack is empty or not
isFull(): checks whether the stack is full
Question 3 - What is Infix, Prefix and Postfix Notations? How are they evaluated?
Answer - Infix notation: In an infix expression, the operator is between the two operands of an operation. The infix expression can be interpreted and evaluated directly without converting it to any other notation.
Example:
5+2*3
In the above expression, the operator appears between the operands. This expression can be evaluated by applying the basic mathematical expression simplification rules. 5+2*3 = 5+6 = 11
Prefix notation: In a prefix expression, the operators precede the corresponding operands on which they work. The prefix expression can be evaluated only after converting it to infix notation.
Example:
*-40/8 2 - /200 10 4
The infix notation of the given prefix expression is ((40-(8/2))*((200/10)-4). This infix expression can be simplified as (40-4)*(20-4) = 36*16 = 576
Postfix notation: In a postfix expression, the operators come after the corresponding operands on which they work. The postfix expression can be evaluated only after converting it to infix notation.
Example:
30 2*4+
The infix notation of the above postfix expression is ((30*2)+4). By evaluating the infix notation, we get 60+4 = 64. So, 64 is the answer for the given postfix expression.
Question 4 - Explain with example the conversion of Infix to Postfix.
Answer - Steps to convert Infix expression to Postfix
Scan all the characters one by one from left to right.
If the character is an operand, then print it.
Else,
If the precedence of the operator scanned is greater than that of the operator on the top of the stack, then push the scanned operator into the stack.
Else, pop and print all the operators from the stack until the operator at the top of the stack has lower precedence that that of the scanned operator.
If the character is ‘(‘, then push it into the stack.
If the character is ‘)’, then print all the elements in the stack until ‘(‘ is encountered.
Repeat the steps ii) and iii) until the entire infix expression is scanned.
Pop and print the remaining elements from the stack
Example
Infix expression: (A+B)*C/D
Step | Scanned Character | Stack | Postfix Expression |
1 | ( | ( | |
2 | A | ( | A |
3 | + | (+ | A |
4 | B | (+ | AB |
5 | ) | | AB+ |
6 | * | * | AB |
7 | C | * | AB+C |
8 | / | */ | AB+C |
9 | D | */ | AB+CD |
| | | AB+CD/* |
C Code
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include <string.h>
char infix_string[20], postfix_string[20];
int top;
int stack[20];
int pop();
int precedence(char symbol);
int isEmpty();
void infix_to_postfix();
int check_space(char symbol);
void push(long int symbol);
int main()
{
int count, length;
char temp;
top = -1;
printf("\nEnter the infix expression ");
scanf("%s", infix_string);
infix_to_postfix();
printf("\nThe Postfix expression is: %s\n", postfix_string);
return 0;
}
/* Function to convert from infix to postfix */
void infix_to_postfix()
{
unsigned int count, temp = 0;
char next;
char symbol;
for(count = 0; count < strlen(infix_string); count++)
{
symbol = infix_string[count];
if(!check_space(symbol))
{
switch(symbol)
{
case '(': push(symbol);
break;
case ')':
while((next = pop()) != '(') // pop until '(' is encountered
{
postfix_string[temp++] = next;
}
break;
case '+':
case '-':
case '*':
case '/':
case '%':
case '^':
while(!isEmpty() && precedence(stack[top]) >= precedence(symbol)) // Check precedence and push the higher one
postfix_string[temp++] = pop();
push(symbol);
break;
default:
postfix_string[temp++] = symbol;
}
}
}
while(!isEmpty())
{
postfix_string[temp++] = pop();
}
postfix_string[temp] = '\0';
}
/* Function to check precedence of operators */
int precedence(char symbol)
{
switch(symbol)
{
case '(': return 0;
case '+':
case '-':
return 1;
case '*':
case '/':
case '%':
return 2;
case '^':
return 3;
default:
return 0;
}
}
int check_space(char symbol)
{
if(symbol == '\t' || symbol == ' ' )
{
return 1;
}
else
{
return 0;
}
}
void push(long int symbol)
{
if(top > 20)
{
printf("Stack Overflow\n");
exit(1);
}
top = top + 1;
stack[top] = symbol; // Push the symbol and make it as TOP
}
int isEmpty()
{
if(top == -1)
{
return 1;
}
else
{
return 0;
}
}
int pop()
{
if(isEmpty())
{
printf("Stack is Empty\n");
exit(1);
}
return(stack[top--]); // Pop the symbol and decrement TOP
}
Question 5 - Explain with example the conversion of Postfix to Infix.
Answer - Steps to convert Postfix Expression to Infix
Scan the Postfix expression from Left to Right
If the character scanned is an operand, push it into the stack
If the scanned character is an operator, pop the top element from the stack and print it. Then, print the scanned operator. Next, pop another element from the stack and print it.
Repeat the steps ii) and iii) until the whole expression is scanned.
Pop the remaining element from the stack and print it.
Example
Postfix expression: 7 5 + 3 *
Step | Scanned Character | Stack | Infix Expression |
1 | 7 | 7 | |
2 | 5 | 7,5 | |
3 | + | 7+5 | 7+5 |
4 | 3 | 7+5,3 | |
5 | * | | |
| | | 7+5*3 |
C Code
#include <stdio.h>
#include <stdlib.h>
int top = 10;
struct node
{
char ch;
struct node *next;
struct node *prev;
} *stack[11];
typedef struct node node;
void push(node *str)
{
if (top <= 0)
printf("Stack is Full ");
else
{
stack[top] = str;
top--;
}
}
node *pop()
{
node *exp;
if (top >= 10)
printf("Stack is Empty ");
else
exp = stack[++top];
return exp;
}
void convert(char exp[])
{
node *op1, *op2;
node *temp;
int i;
for (i=0;exp[i]!='\0';i++)
if (exp[i] >= 'a'&& exp[i] <= 'z'|| exp[i] >= 'A' && exp[i] <= 'Z')
{
temp = (node*)malloc(sizeof(node));
temp->ch = exp[i];
temp->next = NULL;
temp->prev = NULL;
push(temp);
}
else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/' ||
exp[i] == '^')
{
op1 = pop();
op2 = pop();
temp = (node*)malloc(sizeof(node));
temp->ch = exp[i];
temp->next = op1;
temp->prev = op2;
push(temp);
}
}
void display(node *temp)
{
if (temp != NULL)
{
display(temp->prev);
printf("%c", temp->ch);
display(temp->next);
}
}
void main()
{
char exp[50];
clrscr();
printf("Enter the postfix expression :");
scanf("%s", exp);
convert(exp);
printf("\nThe Equivalant Infix expression is:");
display(pop());
}
Question 6 - Explain with example the conversion of Prefix to Infix.
Answer - Steps to convert Prefix expression to Infix
Scan the prefix expression from right to left.
If the scanned character is an operand, then push it into the stack
If the scanned character is an operator, pop two elements from the top of the stack and print them in the following format operand1 + operator + operand2
Repeat the steps ii) and iii) until the entire expression is scanned.
Example
Prefix expression: +*3 5 10
Step | Scanned Scanner | Stack | C Code |
1 | 10 | 10 | |
2 | 5 | 10,5 | |
3 | 3 | 10,5,3 | |
4 | * | 10,5*3 | 5*3 |
5 | + | | 10+5*3 |
C Code
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <conio.h>
char opnds[50][80],oprs[50];
int topr=-1,topd=-1;
pushd(char *opnd)
{
strcpy(opnds[++topd],opnd);
}
char *popd()
{
return(opnds[topd--]);
}
pushr(char opr)
{
oprs[++topr]=opr;
}
char popr()
{
return(oprs[topr--]);
}
int empty(int t)
{
if( t == 0) return(1);
return(0);
}
void main()
{
char prfx[50],ch,str[50],opnd1[50],opnd2[50],opr[2];
int i=0,k=0,opndcnt=0;
printf("Give an Expression = ");
gets(prfx);
printf(" Given Prefix Expression : %s\n",prfx);
while( (ch=prfx[i++]) != '\0')
{
if(isalnum(ch))
{
str[0]=ch; str[1]='\0';
pushd(str); opndcnt++;
if(opndcnt >= 2)
{
strcpy(opnd2,popd());
strcpy(opnd1,popd());
strcpy(str,"(");
strcat(str,opnd1);
ch=popr();
opr[0]=ch;opr[1]='\0';
strcat(str,opr);
strcat(str,opnd2);
strcat(str,")");
pushd(str);
opndcnt-=1;
}
}
else
{
pushr(ch);
if(opndcnt==1)opndcnt=0; /* operator followed by single operand*/
}
}
if(!empty(topd))
{
strcpy(opnd2,popd());
strcpy(opnd1,popd());
strcpy(str,"(");
strcat(str,opnd1);
ch=popr();
opr[0]=ch;opr[1]='\0';
strcat(str,opr);
strcat(str,opnd2);
strcat(str,")");
pushd(str);
}
printf(" Infix Expression: ");
puts(opnds[topd]);
getch();
}
Question 7 - Explain with example the conversion of Prefix to Postfix.
Answer - Steps to convert Prefix expression to postfix
Scan the prefix expression from right to left.
If the scanned character is an operand, then push it into the stack
If the scanned character is an operator, pop two elements from the top of the stack and print them in the following format operand1 + operand2 + operand2
Repeat the steps ii) and iii) until the entire expression is scanned.
Example
Prefix expression: - * 5 6 /25 5
Step | Scanned Character | Stack | Postfix Expression |
1 | 5 | 5 | |
2 | 5, 25 | | |
3 | / | 25 / 5 | 25 5 / |
4 | 6 | 25 5 / , 6 | |
5 | 5 | 25 5 / , 6, 5 | |
6 | * | 25 5 / , 5 6 * | 25 5 / 5 6 * |
7 | - | | 25 5 / 5 6 * - |
C Code
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define BLANK ' '
#define TAB '\t'
#define MAX 50
char *pop();
char prefix[MAX];
char stack[MAX][MAX];
void push(char *str);
int isempty();
int white_space(char symbol);
void prefix_to_postfix();
int top;
int main()
{
top = -1;
printf("Enter Prefix Expression : ");
gets(prefix);
prefix_to_postfix();
}/*End of main()*/
void prefix_to_postfix()
{
int i;
char operand1[MAX], operand2[MAX];
char symbol;
char temp[2];
char strin[MAX];
for(i=strlen(prefix)-1;i>=0;i--)
{
symbol=prefix[i];
temp[0]=symbol;
temp[1]='\0';
if(!white_space(symbol))
{
switch(symbol)
{
case '+':
case '-':
case '*':
case '/':
case '%':
case '^':
strcpy(operand1,pop());
strcpy(operand2,pop());
strcpy(strin,operand1);
strcat(strin,operand2);
strcat(strin,temp);
push(strin);
break;
default: /*if an operand comes*/
push(temp);
}
}
}
printf("\nPostfix Expression :: ");
puts(stack[0]);
}/*End of prefix_to_postfix()*/
void push(char *str)
{
if(top > MAX)
{
printf("\nStack overflow\n");
exit(1);
}
else
{
top=top+1;
strcpy( stack[top], str);
}
}/*End of push()*/
char *pop()
{
if(top == -1 )
{
printf("\nStack underflow \n");
exit(2);
}
else
return (stack[top--]);
}/*End of pop()*/
int isempty()
{
if(top==-1)
return 1;
else
return 0;
}
int white_space(char symbol)
{
if(symbol==BLANK || symbol==TAB || symbol=='\0')
return 1;
else
return 0;
}
Question 8 - How can we evaluate Arithmetic Expressions using Stack? Explain with example.
Answer - Evaluating postfix expression using stack
Scan all the characters in the postfix expression from left to right.
If the character is an operand, push it into the stack
Else, pop two operands from the stack and perform the corresponding operation on the popped elements. Then, push the result into the stack.
Repeat the above two steps until the expression is processed completely.
The remaining element in the stack is the result.
Example: 2 5 + 6* 7/
Step | Character | Operation | Stack | Calculation |
1 | 2 | Push | 2 | |
2 | 5 | Push | 2, 5 | |
3 | + | Pop | 7 | 2+5 = 7 |
4 | 6 | Push | 7, 6 | |
5 | * | Pop | 42 | 7*6=42 |
6 | 7 | Push | 42, 7 | |
7 | / | Pop | 6 | 42/7=6 |
Evaluating prefix expression using stack
Reverse the prefix expression
Now, evaluate the resulting postfix expression using the above mentioned method.
Example
* 12 + 50 4
After reversing the above expression, we get, 4 50 + 12 *
Step | Character | Operation | Stack | Calculation |
1 | 4 | Push | 4 | |
2 | 50 | Push | 4, 50 | |
3 | + | Pop | 54 | 4+50=54 |
4 | 12 | Push | 54, 12 | |
5 | * | Pop | 648 | 54*12=648 |
Question 9 - Write a function for traversing elements of a Stack?
Void traverse_stack()
{
int i;
printf(“The elements in the stack are:\n”);
for(i=top;i>0;i--)
{
Printf(“%d ”, stack[top]);
}
The above function traverses all the elements of the stack, until ‘top’ becomes zero. top==0 indicates that the stack is empty.
Question 10 - Explain time complexity of different operations on Stacks?
PUSH: time complexity is O(1)
POP: time complexity is O(1)
TRAVERSE: time complexity is O(n), where n is the number of elements in the stack. The traverse operation has a linear time complexity, because all the elements in the stacks are processed one by one to give the output.
Question 11 - Explain the tower of Hanoi Problem with the help of Stack.
Answer - Tower of Hanoi Problem
The Tower of Hanoi is a mathematical puzzle in which three rods are given. Disks of different sizes are placed one over the other on one of the three rods (or poles) in ascending order. Our aim is to find the number of moves and the order in which the disks have to be moved, to move all the given disks from the first rod(source) to the third rod(destination) in the same order. The only condition is that a disk cannot be placed over another disk that is smaller than itself.
The Tower of Hanoi problem can be solved by using recursive approach or by using iterative approach(using stacks).
For 1 box: 1 move is required
For 2 box: 21=2 moves are required
For 3 box:
The procedure can be seen as follows:
Thus, moves required=23-1=7
And so on, for n blocks, moves required=2n – 1
i.e. for n box, total 2n-1 function calls are made.
Recursive Equation: T(n)=2*T(n-1)+1
TC=O(2n)
Solution for The Tower of Hanoi Problem using Stacks
Steps:
If there are ‘n’ disks, then (2n-1) moves are required to arrive at the final solution.
If ‘n’ is even, the destination pole (third rod) and the intermediate (or middle) pole can be interchanged.
While iterating through the loop which runs from 1 to the total number of moves
if i%3 == 1, the top disk on the first pole(source) should be moved to the third pole (destination).
If i%3 == 2, the top disk on the first pole(source) should be moved to the middle pole (or second pole).
If i%3 == 0, the top disk on the middle pole should be moved to the third pole (or destination).
C Code:
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
// Creating a stack structure
struct Stack
{
unsigned int capacity;
int top;
int *array;
};
// Creating a stack of given capacity
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack =
(struct Stack*) malloc(sizeof(struct Stack));
stack -> capacity = capacity;
stack -> top = -1;
stack -> array =
(int*) malloc(stack -> capacity * sizeof(int));
return stack;
}
int isFull(struct Stack* stack)
{
return (stack->top == stack->capacity - 1);
}
int isEmpty(struct Stack* stack)
{
return (stack->top == -1);
}
void push(struct Stack *stack, int item)
{
if (isFull(stack))
return;
stack -> array[++stack -> top] = item;
}
int pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack -> array[stack -> top--];
}
//Function to show the movement of disks
void moveDisk(char fromPeg, char toPeg, int disk)
{
printf("Move the disk %d from \'%c\' to \'%c\'\n",
disk, fromPeg, toPeg);
}
// Moving disks between the poles
void moveDisksBetweenTwoPoles(struct Stack *src,
struct Stack *dest, char s, char d)
{
int pole1TopDisk = pop(src);
int pole2TopDisk = pop(dest);
// When pole 1 is empty
if (pole1TopDisk == INT_MIN)
{
push(src, pole2TopDisk);
moveDisk(d, s, pole2TopDisk);
}
// When pole2 pole is empty
else if (pole2TopDisk == INT_MIN)
{
push(dest, pole1TopDisk);
moveDisk(s, d, pole1TopDisk);
}
// When top disk of pole1 > top disk of pole2
else if (pole1TopDisk > pole2TopDisk)
{
push(src, pole1TopDisk);
push(src, pole2TopDisk);
moveDisk(d, s, pole2TopDisk);
}
// When top disk of pole1 < top disk of pole2
else
{
push(dest, pole2TopDisk);
push(dest, pole1TopDisk);
moveDisk(s, d, pole1TopDisk);
}
}
//Function to implement TOH puzzle
void tohIterative(int num_of_disks, struct Stack
*src, struct Stack *aux,
struct Stack *dest)
{
int i, total_num_of_moves;
char s = 'S', d = 'D', a = 'A';
//If number of disks is even, then interchange
//destination pole and auxiliary pole
if (num_of_disks % 2 == 0)
{
char temp = d;
d = a;
a = temp;
}
total_num_of_moves = pow(2, num_of_disks) - 1;
//Larger disks will be pushed first
for (i = num_of_disks; i >= 1; i--)
push(src, i);
for (i = 1; i <= total_num_of_moves; i++)
{
if (i % 3 == 1)
moveDisksBetweenTwoPoles(src, dest, s, d);
else if (i % 3 == 2)
moveDisksBetweenTwoPoles(src, aux, s, a);
else if (i % 3 == 0)
moveDisksBetweenTwoPoles(aux, dest, a, d);
}
}
int main()
{
unsigned num_of_disks;
printf(“Enter the number of disks”);
scanf("%d", &num_of_disks);
struct Stack *src, *dest, *aux;
//Creating 3 stacks which represent the 3 poles
src = createStack(num_of_disks);
aux = createStack(num_of_disks);
dest = createStack(num_of_disks);
tohIterative(num_of_disks, src, aux, dest);
return 0;
}
Output
Question 12 - Implement Stack using Heap.
Answer - A Heap is similar to priority queue. Each element in a heap has a priority associated with it. So, in order to make a heap work like a stack, we must keep tract of the count of the elements that are pushed into the heap. This count variable for each element determines the priority of that element. The element with the minimum count value has the highest priority. As the minimum value of count has the highest priority, we use min heap for this purpose. Each node in the heap has a key-value pair, where the count acts as the key.
C++ code
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
class Stack
{
int cnt;
priority_queue<pair<int, int> > pq;
public:
Stack():cnt(0){}
void push(int n);
void pop();
int top();
bool isEmpty();
};
// push function increases cnt by 1 and
// inserts this cnt with the original value.
void Stack::push(int n){
cnt++;
pq.push(pi(cnt, n));
}
// pops element and reduces count.
void Stack::pop(){
if(pq.empty()){ cout<<"Nothing to pop!!!";}
cnt--;
pq.pop();
}
// returns the top element in the stack using
// cnt as key to determine top(highest priority),
// default comparator for pairs works fine in this case
int Stack::top(){
pi temp=pq.top();
return temp.second;
}
// return true if stack is empty
bool Stack::isEmpty(){
return pq.empty();
}
// Driver code
int main()
{
Stack* s=new Stack();
s->push(1);
s->push(2);
s->push(3);
while(!s->isEmpty()){
cout<<s->top()<<endl;
s->pop();
}
}
Comments