## Pages

The greatest mistake you can make in life is to be continually fearing you will make one

## Thursday, 4 February 2010

### Problems Based On Stack

Problem 1: What would be the state of a stack after the following operations
create stack
push A on to stack
push F on to stack
push X on to stack
pop item from stack
push B on to stack
pop item from stack
pop item from stack.
Solution:
Stack

create stack                          -->      Empty stack
push A on to stack                -->      A
push F on to stack                 -->     FA
push X on to stack                -->      XFA
pop item from stack              -->      FA
push B on to stack                -->      BFA
pop item from stack              -->      FA
pop item from stack.             -->      A

Finally the stack contains A only

Problem 2: Show the state of the stack and the value of each variable after execution of
each of the following statements:
A = 5 B = 3 C = 7
(a) create stack
push A onto stack
push C*C onto stack
pop item from stack and store in B
push B+A onto stack
pop item from stack and store in A
pop item from stack and store in B
(b) create stack
push B onto stack
push C onto stack
push A onto stack
A = B * C
push A+C onto stack
pop item from stack and store in A
pop item from stack and store in B
pop item from stack and store in C

Solution for a:

operation               Stack
create stack                                                                  Empty stack
push A onto stack                             Push 5                5
push C*C onto stack                        push 7*7            49 5
pop item from stack and store in B    pop 49& B=49   5

push B+A onto stack                         push 54               54 5
pop item from stack and store in A    pop 54& A=54   5
pop item from stack and store in B    pop 5 & B=5       Empty stack

Now A=54,B=5 and C=7

Solution for b:
Stack
create stack                                                   Empty stack
push B onto stack                                         3
push C onto stack                                         7 3
push A onto stack                                        5 7 3
A = B * C-->A=21
push A+C onto stack -->21+7->28            28 5 7 3
pop item from stack and store in A->A=28  5 7 3
pop item from stack and store in B->B=5     7 3
pop item from stack and store in C->C=7     3

Now A=28,B=5 and C=7

Problem 3:A function f defined on stacks of integers satisfies the following properties. f(∅)= 0 and f(push(S,i))=max⁡(f(S),0)+ i for all stacks S and integers i.
If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?
(a) 6
(b) 4
(c) 3
(d) 2

Solution:
Initially stack is empty. S->{}. so f(S)=0
Push 2 in to stack S.
f(push(S,2)=f(push({},2)=max(f(S),0)+2=max(0,0)+2=0+2=2
now S->{2} and f(S)=2
push -3 in to Stack S
f(push({2},-3))=max(f(S),0)+(-3)=max(2,0)+(-3)=2-3=-1
now S->{2,-3} and f(s)=-1
push 2 in to stack S
f(push({2,-3},2)=max(-1,0)+2=0+2=2
now S->{2,-3,2} and f(S)=2
push -1 in to stack S
f(push({2,-3,2},-1))=max(2,0)+(-1)=2-1=1
now S->{2,-3,2,-1} and f(S)=1
push 2 in to stack S
f(push({2,-3,2,-1},2))=max(1,0)+2=1+2=3
now S->{2,-3,2,-1,2} and f(S)=3

so finally f(S)=3

Problem 4:Suppose that a client performs an intermixed sequence of (stack) push and pop operations. The push operations put the integers 0 through 9 in order on to the stack; the pop operations print out the return value. Which of the following sequences could not occur?
(a) 4 3 2 1 0 9 8 7 6 5
(b) 4 6 8 7 5 3 2 9 0 1
(c) 2 5 6 7 4 8 9 3 1 0
(d) 4 3 2 1 0 5 6 7 8 9
(e) 1 2 3 4 5 6 9 8 7 0
(f) 0 4 6 5 3 8 1 7 2 9
(g) 1 4 7 9 8 6 5 3 0 2
(h) 2 1 4 3 6 5 8 7 9 0

Solution
Sequence b,f,g couldn't occur

Problem 5:
Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is (GATE CS 2003)
a) n(X+ Y)
b) 3Y + 2X
c) n(X + Y)-X
d) Y + 2X

Solution