Test: Stacks & Queues

To keep the Last In First Out order, a stack can be implemented using linked list in two ways:

a) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from beginning.

b) In push operation, if new nodes are inserted at the end of linked list, then in pop operation, nodes must be removed from end.

Since the stack data structure follows LIFO order. When we pop() items from stack, they are popped in reverse order of their insertion (or push())

At the end of while loop, we must check whether the stack is empty or not. For input ((()), the stack doesn’t remain empty after the loop. 

The algorithm for evaluating any postfix expression is fairly straightforward:

1. While there are input tokens left
    o Read the next token from input.
    o If the token is a value
       + Push it onto the stack.
    o Otherwise, the token is an operator 
      (operator here includes both operators, and functions).
       * It is known a priori that the operator takes n arguments.
       * If there are fewer than n values on the stack
        (Error) The user has not input sufficient values in the expression.
       * Else, Pop the top n values from the stack.
       * Evaluate the operator, with the values as arguments.
       * Push the returned results, if any, back onto the stack.
2. If there is only one value in the stack
    o That value is the result of the calculation.
3. If there are more values in the stack
    o (Error)  The user input has too many values.

Let us run the above algorithm for the given expression.
First three tokens are values, so they are simply pushed. After pushing 8, 2 and 3, the stack is as follows

8, 2, 3

When ^ is read, top two are popped and power(2^3) is calculated

8, 8

When / is read, top two are popped and division(8/8) is performed

1

Next two tokens are values, so they are simply pushed. After pushing 2 and 3, the stack is as follows

1, 2, 3

When * comes, top two are popped and multiplication is performed.

1, 6

If we are to use space efficiently then size of the any stack can be more than MAXSIZE/2.
Both stacks will grow from both ends and if any of the stack top reaches near to the other top then stacks are full. So the condition will be top1 = top2 -1 (given that top1 < top2)

Any expression can be converted into Postfix or Prefix form.

Prefix and postfix evaluation can be done using a single stack.

For example : Expression ’10 2 8 * + 3 -‘ is given.
PUSH 10 in the stack.
PUSH 2 in the stack.
PUSH 8 in the stack.
When operator ‘*’ occurs, POP 2 and 8 from the stack.
PUSH 2 * 8 = 16 in the stack.
When operator ‘+’ occurs, POP 16 and 10 from the stack.
PUSH 10 * 16 = 26 in the stack.
PUSH 3 in the stack.
When operator ‘-‘ occurs, POP 26 and 3 from the stack.
PUSH 26 – 3 = 23 in the stack.
So, 23 is the answer obtained using single stack.

f(S) = 0, max(f(S), 0) = 0, i = 2
f(S)new = max(f(S), 0) + i = 0 + 2 = 2

f(S) = 2, max(f(S), 0) = 2, i = -3
f(S)new = max(f(S), 0) + i = 2 – 3 = -1

f(S) = -1, max(f(S), 0) = 0, i = 2
f(S)new = max(f(S), 0) + i = 0 + 2 = 2

f(S) = 2, max(f(S), 0) = 2, i = -1
f(S)new = max(f(S), 0) + i = 2 – 1 = 1

f(S) = 1, max(f(S), 0) = 1, i = 2
f(S)new = max(f(S), 0) + i = 1 + 2 = 3

 
Thus, option (C) is correct.

The function of the program is:-

1) If the current character is a digit it pushes into stack
2) Else if the current character is operator,  it pops two elements and then performs the operation.
Finally it pushes the resultant element into stack.
Initially stack s is empty. 5 2 * 3 3 2 + * +
1) 5 -> It pushes into s
2) 2 -> It pushes into s
3) * -> It pops two elements n = 2, m=5 n*m = 10 It pushes 10 into s
4) 3 -> It pushes into s
5) 3 -> It pushes into s
6) 2 -> It pushes into s
7) + -> n=2, m=3 n+m=5 It pushes 5 into s
8) * -> n=5, m=3 n*m=15 It pushes 15 into s
9) + -> n=15, m=10 n+m = 25 It pushes 25 into s.

We are implementing a STACK using Priority Queue. Note that Stack implementation is always last in first out (LIFO) order.

As given “POP is implemented as DELETEMIN(Q)” that means Stack returns minimum element always.

So, we need to implement PUSH(C) using INSERT(Q, C, K) where K is key chosen from strictly-decreasing order(only this order will ensure stack will return minimum element when we POP an element). That will satify Last In First Out (LIFO) property of stack.

That is answer, option (D) is true.

Option (A) non-increasing order can not be true because two same (identical) numbers can not have same priority as priority should be distinguishable for each number.

In fig:-1 elements are inserted into a stack then in fig:-2 top 5 elements are popped and these 5 elements are inserted into a queue which is shown in fig:-3, now first two elements are deleted from queue and pushed into stack one by one which is shown in fig:-5.
At top of the stack element B is presented.
So, option (B) is correct.

The pop sequence can be seen from the following table:

Let’s construct an empty stack and do the operations. Stack follows LIFO order.

1.Push(54) // (54)
2.Push(52) // (54,52)
3.Pop() // (54)
4.Push(55) //(54,55)
5.Push(62) //(54,55,62)
6.s=pop() // (54,55)
s=62;

Let’s construct an empty queue and do the operations. Queue follows FIFO order.

1.Enqueue(21) // [21]
2.Enqueue(24) // [21,24]
3.Dequeue() // [24]
4.Enqueue(28) // [24,28]
5.Enqueue(32) // [24,28,32]
6.q=Dequeue() // [28,32]
q=24;

s+q=62+24

So, s+q=86 . 

 (A + B^ D) / (E – F) + G
= (A + B^ D)(E – F)/ + G
= (A + B^ D)(E – F)/G+
= A + BD^(E – F)/G+
= ABD^+EF-/G+
So, option (A) is correct.

When five items: A, B, C, D, and E are pushed in a stack: Order of stack becomes: A, B, C, D, and E (A at the bottom and E at the top.) stack is popped four items and each element is inserted in a queue: Order of queue: B, C, D, E (B at rear and E at the front) Order of stack after pop operations = A. Two elements deleted from the queue and pushed back on the stack: New order of stack = A, E, D(A at the bottom, D at the top) As D is on the top so when pop operation occurs D will be popped out. So, correct option is (D).
 

Option (A):
Pop a from stack A
Push a to stack B
Print b
Print a from stack B
Print c from stack A
Order = b a c

Option (B):
Pop a from stack A
Push a to stack B
Print b from stack A
Print c from stack A
Print a from stack A
Order = b c a

Option (C):
Pop a from stack A
Push a to stack B
Pop b from stack A
Push b to stack B
Print c from stack A
Now, printing a will not be possible.
So, option (C) is incorrect.