Stack

• Stack is a linear data structure which follows a particular order in which the
operations are performed.

i
• Principal: LIFO(Last In First Out) or FILO(First In Last Out).

a lin
Sh
ith
W
a rn
Le

1
 i
a lin
Sh
ith
W
There are many real-life examples of a stack. Consider an example of plates
rn
stacked over one another in the canteen. The plate which is at the top is the
first one to be removed, i.e. the plate which has been placed at the
a
Le

bottommost position remains in the stack for the longest period of time. So, it
can be simply seen to follow LIFO(Last In First Out)/FILO(First In Last Out)
order.

2
A stack can be implemented by means of Array, Structure, Pointer, and
Linked List.
Stack can either be a fixed size one or it may have a sense of dynamic

i
lin
resizing.
Here, we are going to implement stack using arrays, which makes it a fixed

a
size stack implementation.

Sh
ith
W
a rn
Le

3
Stack works on the LIFO pattern.
As we can observe in the below figure there are five memory blocks in the stack; therefore,
the size of the stack is 5.
Suppose we want to store the elements in a stack and let's assume that stack is empty.

i
lin
We have taken the stack of size 5 as shown below in which we are pushing the elements
one by one until the stack becomes full.

a
Sh
ith
W
a rn
Le

4
Stack Operations

The following are some common operations implemented on the stack:

1. push(): When we insert an element in a stack then the operation is known as a push. If

i
the stack is full then the overflow condition occurs.

a lin
2. pop(): When we delete an element from the stack, the operation is known as a pop. If the

Sh
stack is empty means that no element exists in the stack, this state is known as an
underflow state.

ith
3. isEmpty(): It determines whether the stack is empty or not.
W
4. isFull(): It determines whether the stack is full or not.
a rn
5. peek(): It returns the element at the given position.
Le

6. count(): It returns the total number of elements available in a stack.

7. change(): It changes the element at the given position.

8. display(): It prints all the elements available in the stack.

5
PUSH operation:
1. Before inserting an element in a stack, we check whether the stack is full.
2. If we try to insert the element in a stack, and the stack is full, then the overflow
condition occurs.
3. When we initialize a stack, we set the value of top as -1 to check that the stack is

i
lin
empty.
4. When the new element is pushed in a stack, first, the value of the top gets

a
incremented, i.e., top=top+1, and the element will be placed at the new position of

Sh
the top.
5. The elements will be inserted until we reach the max size of the stack.

ith
W
a rn
Le

6
POP operation
1. Before deleting the element from the stack, we check whether the stack is empty.
2. If we try to delete the element from the empty stack, then the underflow condition
occurs.

i
lin
3. If the stack is not empty, we first 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.

a
Sh
ith
W
a rn
Le

7
Implementation of Stack:
There are two ways to implement a stack:

1. Array

i
lin
2. Linked list

a
Sh
ith
W
a rn
Le

8
Array implementation of Stack

1. For implementing a stack using array we need an fixed size array and
Top pointer.

i
lin
2. Initially Top=-1
3. Perform Stack Operation in the manner that it take O(1) time.

a
Sh
ith
W
a rn
Le

9
Adding an element onto the stack (push operation)

Push operation involves following two steps.

1. Increment the variable Top so that it can now refer to the next memory location.

i
2. Add element at the position of incremented top. This is referred to as adding new

lin
element at the top of the stack.

a
Sh
Stack is overflown when we try to insert an element into a completely filled stack
therefore, our main function must always avoid stack overflow condition.

ith
Algorithm:
W
rn
1. begin
a
2. if top = n then stack full
Le

3. top = top + 1
4. stack (top) : = item;
5. end

10
implementation of push algorithm in C language
Time Complexity : o(1)

void push (int val,int n) //n is size of the stack

i
{

lin
if (top == n )

a
printf("\n Overflow");

Sh
else
{

ith
top = top +1;
stack[top] = val;
}
W
rn
}
a
Le

11
Deletion of an element from a stack (Pop operation)

1. The value of the variable top will be incremented by 1 whenever an item is deleted
from the stack.
2. The top most element of the stack is stored in an another variable and then the

i
lin
top is decremented by 1.
3. The operation returns the deleted value that was stored in another variable as the

a
Sh
result.
4. The underflow condition occurs when we try to delete an element from an already

ith
empty stack.

Algorithm : W
rn
1. begin
a

2. if top = -1 then stack empty;

Le

3. item := stack(top);
4. top = top - 1;
5. end;

12
Implementation of POP algorithm using C language
Time Complexity : O(1)

int pop ()

i
lin
{
if(top == -1)

a
{

Sh
printf("Underflow");
return 0;

ith
}
else
{ W
rn
return stack[top - - ];
}
a

}
Le

13
Visiting each element of the stack (Peek operation)

1. Peek operation involves returning the element which is present at the top of
the stack without deleting it.

i
lin
2. Underflow condition can occur if we try to return the top element in an
already empty stack.

a
Sh
Algorithm :

ith
PEEK (STACK, TOP)
1. Begin
2. W
if top = -1 then stack empty
rn
3. item = stack[top]
4. return item
a

5. End
Le

14
Implementation of Peek algorithm in C language
Time complexity: o(n)

i
a lin
int peek()

Sh
{
if (top == -1)

ith
{
printf("Underflow");

}
return 0;
W
rn
else
a

{
Le

return stack [top];

}
}

15
Applications of Stack:
1. Conversion of Infix to Postfix and Prefix Expression
2. Balanced Parenthesis Checking

i
lin
3. Evaluate Postfix Expression
4. Recursion

a
Sh
ith
W
a rn
Le

16
Expression Representation:

There are three popular methods used for representation of an expression:

Operator between

i
Infix A+B

lin
operands.

a
Prefix + AB Operator before operands.

Sh
Postfix AB + Operator after operands.

ith
W
a rn
Le

17
Conversion of Infix to Postfix

i
lin
a
Sh
ith
W
a rn
Le

18
 Algorithm for Infix to Postfix

Step 1: Consider the next element in the input.

i
lin
Step 2: If it is operand, display it.

a
Sh
Step 3: If it is opening parenthesis, insert it on stack.

ith
Step 4: If it is an operator, then
• If stack is empty, insert operator on stack.
W
• If the top of stack is opening parenthesis, insert the operator on stack
rn
• If it has higher priority than the top of stack, insert the operator on stack.
• Else, delete the operator from the stack and display it, repeat Step 4.
a
Le

Step 5: If it is a closing parenthesis, delete the operator from stack and display them until an
opening parenthesis is encountered. Delete and discard the opening parenthesis.

Step 6: If there is more input, go to Step 1.

Step 7: If there is no more input, delete the remaining operators to output.

19
Example: Convert 3*3/(4-1)+6*2 expression into postfix form.

Following table shows the evaluation of Infix to Postfix:

Expression Stack Output

i
lin
3 Empty 3
* * 3

a
Sh
3 * 33
/ / 33*

ith
( /( 33*
4 /( 33*4
- /(- W 33*4
rn
1 /(- 33*41
a
) /(- 33*41-
Le

+ + 33*41-/
6 + 33*41-/6
* +* 33*41-/62
2 +* 33*41-/62
Empty 33*41-/62*+

So, the Postfix Expression is 33*41-/62*+ 20

 Additional Examples of Infix to Postfix Conversion
Infix Expression Postfix Expression

i
a lin
A+B*C+D ABC*+D+

Sh
ith
(A + B) * (C + D) AB+CD+*

W
a rn
A*B+C*D AB*CD*+
Le

A+B+C+D AB+C+D+

21
Conversion of Infix to Prefix

i
lin
a
Sh
ith
W
a rn
Le

22
Conversion of Infix to Prefix
Algorithm for Infix to Prefix Conversion:

Step 1: Reverse the infix expression i.e A+B*C will become C*B+A. Note while
reversing each ‘(‘ will become ‘)’ and each ‘)’ becomes ‘(‘.

i
lin
Step 2: Obtain the postfix expression of the modified expression i.e CB*A+.
Step 3: Reverse the postfix expression. Hence in our example prefix is +A*BC.

a
Sh
ith
W
a rn
Le

23
Example: Convert 3*4+2*7 expression into prefix form.

i
a lin
Sh
ith
W
a rn
Le

24
Example: Convert 3*3/(4-1)+6*2 expression into prefix form.

i
a lin
Sh
ith
W
a rn
Le

25
 Additional Examples of Infix, Prefix, and Postfix

Infix Expression Prefix Expression

i
a lin
A+B*C+D ++A*BCD

Sh
ith
(A + B) * (C + D) *+AB+CD
W
a rn
A*B+C*D +*AB*CD
Le

A+B+C+D +++ABCD

26
 Le
arn
W
ith
Sh
a lin
27
i
Que 1 Assume that the operators +, -, × are left associative and ^ is right associative. The
order of precedence (from highest to lowest) is ^, x , +, -. The postfix expression
corresponding to the infix expression a + b × c - d ^ e ^ f is

i
A abc × + def ^ ^ -

lin
B abc × + de ^ f ^ -

a
C ab + c × d - e ^ f ^

Sh
D - + a × bc ^ ^ def

ith
W
a rn
Le

28
Que 2. To evaluate an expression without any embedded function calls:
A One stack is enough
B Two stacks are needed

i
lin
C As many stacks as the height of the expression tree are needed
D A Turing machine is needed in the general case

a
Sh
ith
W
a rn
Le

29
Que 3. Which of the following permutation can be obtained in the same order
using a stack assuming that input is the sequence 5, 6, 7, 8, 9 in that order?
A 7, 8, 9, 5, 6

i
B 5, 9, 6, 7, 8

lin
C 7, 8, 9, 6, 5

a
D 9, 8, 7, 5, 6

Sh
ith
W
a rn
Le

30
Que 4. If the sequence of operations - push (1), push (2), pop, push (1), push
(2), pop, pop, pop, push (2), pop are performed on a stack, the sequence of
popped out values
A 2,2,1,1,2

i
lin
B 2,2,1,2,2

a
C 2,1,2,2,1

Sh
D 2,1,2,2,2

ith
W
a rn
Le

31