Stack

Introduction

A stack is a linear data structure that follows the precept of Last In First Out (LIFO). This means the last element inserted within the stack is removed first.

Mainly, the following operations are executed in the stack:

Push: adds an object in the stack, and if the stack is complete, it is stated to be an Overflow situation.

Pop: removes an item from the stack in the reversed order in which they're pushed. If the stack is empty, it is an Underflow circumstance.

Peek: Returns the first/top element from the stack.

isEmpty: Returns false if the stack is non-empty, else true.

Questions

1. Consider the following series of operations on an empty stack.

push(54);
push(52);
pop();
push(55);
push(62);
s=pop();

Consider the following series of operations on an empty queue.

enqueue(21);
enqueue(24);
dequeue();
enqueue(28);
enqueue(32);
q=dequeue();

The value of s+q is ___________.

(A) 86

(B) 68

(C) 24

(D) 94

Solution: (A) 86

Stack: Last in First out data structure. So, s = pop() = 62

Queue: First in First out data structure. So q = dequeue() = 24

Therefore,

s+q = 62+24 = 86

2. Suppose a stack is applied with a linked list instead of an array. What will be the impact at the time complexity of the push and pop operations of the stack implemented using linked list(Assuming stack is implemented successfully)?

(A) O(1) for insertion and O(n) for deletion

(B) O(1) for insertion and O(1) for deletion

(C) O(n) for insertion and O(1) for deletion

(D) O(n) for insertion and O(n) for deletion

Solution: (B) O(1) for insertion and O(1) for deletion

A stack may be implemented using a linked list having O(1) bounds for both insertions and deletion by inserting and deleting the element from the start of the list.

3. Consider n elements that are equally disbursed in k stacks, and in each stack, elements are arranged in ascending order (i.e., min is at the top in each stack and after which increasing downwards).

Given a queue of length n wherein we have to place all n elements in increasing order. What is going to be the time complexity of the best-known algorithm?

(A) O(n log k)

(B) O(nk)

(C) O(n2)

(D) O(k2)

Solution: (A) O(n log k)

In (n logk), it can be achieved by creating a min-heap of size k and including all the top–elements of all the stacks. After extracting the min, add the following element from the stack from which we have got our 1st minimum.

Time Complexity = O(k) (For creating Heap of length k) + (n-k)log k (Insertions into the heap).

4. Consider the following C program:

#include 
#define EOF -1
void push (int);
int pop (void);
void flagError ();
int main () {
      while ((c = getchar ()) != EOF)
      { 
if (isdigit (c) )
push (c);
             else if ((c == '+') || (c == '*')) {          
m = pop ();
                    n = pop ();
                    r = (c == '+') ? n + m : n*m;
                    push (r);
             }
             else if (c != ' ') {
flagError ();
             }
printf("% c", pop ());
}

What is the output of the program for the following input?

5 2 * 3 3 2 + * +

(A) 15

(B) 25

(C) 30

(D) 150

Solution: (B) 25

The function of the program is:-

If the character is a digit, it pushes into the stack; else, if the character is an operator, it pops two elements, performs the operation, and finally pushes the resultant element into the stack.

Initially, the stack is empty.

1) 5 -> It pushes into stack

2) 2 -> It pushes into stack

3) * -> It pops two elements n = 2, m=5 n*m = 10 It pushes 10 into stack

4) 3 -> It pushes into stack

5) 3 -> It pushes into stack

6) 2 -> It pushes into stack

7) + -> n=2, m=3 n+m=5 It pushes 5 into stack

8) * -> n=5, m=3 n*m=15 It pushes 15 into stack

9) + -> n=15, m=10 n+m = 25 It pushes 25 into stack

Finally, the result value = 25 which is the only element present in stack.

5. A function f defined on stacks of integer values satisfies the subsequent properties. f(∅) = 0 & f(push (S, i)) = max(f(S), 0) + i for all stacks S and corresponding integers i.

If a stack S contains the values 2, -3, 2, -1, 2 in order from bottom to top, what's f(S)?

(A) 6

(B) 4

(C) 3

(D) 2

Solution: (C) 3

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

6. To evaluate an expression with none embedded function calls:

(A) One stack is enough

(B) Two stacks are required

(C) the same number of stacks as the height of the expression tree is required

(D) A Turing system is required within the general case

Solution: (A) One stack is enough

The expression can be converted into prefix or postfix form, which can be done using a single stack.

For example : Expression ’5 1 4 * + 3 -‘ is given.

PUSH 5 in the stack.

PUSH 1 in the stack.

PUSH 4 in the stack.

When operator '*' occurs, POP 1 and 4 from the stack.

PUSH 1*4 = 4 in the stack.

When operator '+' occurs, POP 4 and 5 from the stack.

PUSH 4+5 = 9 in the stack.

PUSH 3 in the stack.

When operator '-' occurs, POP 9 and 3 from the stack.

PUSH 9–3 = 6 in the stack.

So, 6 is the answer obtained using a single stack.

Thus, option (A) is correct.

7. A priority queue Q is used to enforce a stack that stores characters. PUSH(C) is implemented as INSERT(Q, C, k), in which k is the suitable integer key selected through the implementation. POP is implemented as DELETEMIN(Q). For a chain of operations, the keys chosen are in

(A) Non-increasing order

(B) Non-decreasing order

(C) strictly increasing order

(D) strictly decreasing order

Solution: (D) strictly decreasing order

We're implementing a STACK using a priority Queue. Be aware that stack implementation is always in LIFO order.

As given in the question, POP is implemented as DELETEMIN(Q), which means the stack returns the minimum element.

So, implementing PUSH(C) using INSERT(Q, C, k) in which k is the key chosen from a strictly-decreasing order(only this order will ensure the stack will return the minimal element while we POP an element). That will satisfy the LIFO property of the stack.

Thus, option (D) is correct.

8. Which of the following permutation will be obtained in the identical order using a stack, assuming that the input is the sequence 5, 6, 7, 8, 9 in that order?

(A) 7, 8, 9, 5, 6

(B) 5, 9, 6, 7, 8

(C) 7, 8, 9, 6, 5

(D) 9, 8, 7, 5, 6

Solution: (C) 7, 8, 9, 6, 5

We can obtain the above sequence by performing operations in the manner:

Push 5;Push 6;Push 7;Pop 7;Push 8;Pop 8;Push 9;Pop 9;Pop 6;Pop 5.

Hence, the sequence obtained will be 7,8,9,6,5.

Also read, permutation of string

9. The best data structure to test whether an arithmetic expression has balanced parenthesis is

(A) Queue

(B) Stack

(C) Tree

(D) List

Solution: (B) Stack

Stacks can test equal pair/ balanced pair of parenthesis efficiently. Every time we get an opening parenthesis, we can push it on the stack, and when we get the corresponding closing parenthesis, we can pop it. After performing all push and pop operations, if the expression stack's end becomes empty, the expression has a balanced parenthesis.

10. The five items, i.e., A, B, C, D, and E, are driven in a stack, starting from A. The stack is popped four gadgets, and each popped element is inserted in a queue. The two elements are then deleted from the queue and driven back on the stack. Now, one item is popped again from the stack. The popped item is

(A) A

(B) B

(C) C

(D) D

Solution: (D) D

When five items, i.e., A, B, C, D, and E, are pushed in a stack:

Order of stack turns to be: A, B, C, D, and E where A is at the bottom and E is at the top.)

Now, a stack is popped four items, and each element is inserted in a queue:

Order of queue turns out to be: B, C, D, E (B at rear and E at the front)

Order of stack after pop operations = A

Now, 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 at the top, D will be popped out when a pop operation happens.

11. Stack A has the entries a, b, c (with a on top). Stack B is empty. An entry popped out of stack A may be printed straight away or pushed to stack B. An entry popped out of stack B may be only be printed. Which of the subsequent permutations of a, b, c is not feasible in this arrangement?

(A) b a c

(B) b c a

(C) c a b

(D) a b c

Solution: (C) c a b

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 will not be possible.

12. Which of the subsequent is not an inherent application of stack?

(A) Implementation of recursion

(B) Job scheduling

(C) evaluation of a postfix expression

(D) string reversal

Solution: (B) Job scheduling

We will use the stack for string reversal, evaluation of postfix expression, and the most important is recursion implementation; however, job scheduling isn't executed through the stack.

13. Convert the subsequent infix expression into its equal postfix expression (A + B^ D) / (E – F) + G

(A) ABD^ + EF – / G+

(B) ABD + ^EF – / G+

(C) ABD + ^EF / – G+

(D) ABD^ + EF / – G+

Solution: (A) ABD^ + EF – / G+

(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+

= Option (A) is correct.

Must Read Stack Operations