MODULE 2:STACK ASSIGNMENT
Ques 1)Explain and four operation on stack
ANS)
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 the stack is full then the overflow
condition occurs.
2)pop()
When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no
element exists in the stack, this state is known as an underflow state.
Once the pop operation is performed, the top is decremented by 1, i.e., top= top-1.
3)isEmpty()
It determines whether the stack is empty or not.
This operation is used to check whether stack is empty or not. It checks stack top position. If stack top is -1 then stack is
empty.
)isFull():
It determines whether the stack is full or not.'
This operation is used to check whether stack is full or not. It checks stack top position. If stack top is maximumsize -1
then stack is full.
Ques 2)Write Algorithm for push and pop operation
ANS)
PUSH (STACK, TOP, MAX, ITEM)
This procedure pushes an ITEM onto a stack
If TOP = MAX-1, then Print: OVERFLOW, and Return.
Set TOP := TOP + 1 [Increases TOP by 1]
Set STACK [TOP] := ITEM. [Insert ITEM in TOP position]
Return
Module 2: STACK NOTES BY KASHIF SIR 9819421144 Page 1|3
ALGORITHM/PROCEDURE FOR POP OPERATION
POP (STACK, TOP, ITEM)
This procedure deletes the top element of STACK and assign it to the variable ITEM
If TOP = -1, then Print: UNDERFLOW and Return.
Set ITEM = STACK[TOP]
Set TOP = TOP - 1 [Decreases TOP by 1]
Return
QUES 3)Explain multiple stack with example
ANS)
While implementing a stack using an array, we had seen that the size of the array must be known in advance.
If the stack is allocated less space, then frequent OVERFLOW conditions will be encountered.
To deal with this problem, the code will have to be modified to reallocate more space for the array.
In case we allocate a large amount of space for the stack, it may result in sheer wastage of memory. Thus, there lies a
trade-off between the frequency of overflows and the space allocated.
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 below illustrates this concept.
In the above diagram, 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. While operating on these stacks, it
is important to note one thing—Stack A will grow from left to right, whereas Stack B will grow from right to left at the
same time.
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]. This is shown in below
Ques 4)Convert the following infix expression to postfix expression
((A+B)*D) ^(E - F)
and evaluate the following postfix expression P : 5,6,2,+,*,12,4,/,-
ANS)
Add ‘(‘ at the beginning and ‘)’ at the end of the expression
SR.N SYMBOL SCANNED STACK POSTFIX
O
1 ( ( -
2 (( (( -
3 ((( ((( -
4 A ((( A
5 + (((+ A
6 B (((+ AB
7 ) (( AB+
8 * ((* AB+
Module 2: STACK NOTES BY KASHIF SIR 9819421144 Page 2|3
9 D ((* AB+D
10 ) ( AB+D*
11 ^ (^ AB+D*
12 ( (^( AB+D*E
13 E (^( AB+D*E
14 - (^(- AB+D*E
15 F (^(- AB+D*EF
16 ) (^ AB+D*EF-
17 Empty Empty AB+D*EF-^
Evaluate of posfix expression P : 5,6,2,+,*,12,4,/,-
Sr. No. Symbol Scanned STACK
1 5 5
2 6 5,6
3 2 5,6,2
4 + 5,8
5 * 40
6 12 40,12
7 4 40,12,4
8 / 40,3
9 - 37
10 )
QUES 5)What is the result of performing the following operations on a stack (initially empty)?
1)Push 10 2)Push 20 3)Pop 4)Push 30 5)Pop
9 9 9 9 9 9
8 8 8 8 8 8
7 7 7 7 7 7
6 6 6 6 6 6
5 5 5 5 5 5
4 4 4 4 4 4
3 3 3 3 3 3
2 2 2 2 2 2
top
1 1 20 1 top→ 1 30 1
1 →
top top
top→ 0 10 0 10 0 10 0 10 0 10
0 → →
Empty,
Push Push Push
top=- Pop Pop
10 20 30
1)
Module 2: STACK NOTES BY KASHIF SIR 9819421144 Page 3|3