Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Questions
2.1.
Solution: (A) 86
2.2.
Solution: (B) O(1) for insertion and O(1) for deletion
2.3.
Solution: (A) O(n log k)
2.4.
Solution: (B) 25
2.5.
Solution: (C) 3
2.6.
Solution: (A) One stack is enough
2.7.
Solution: (D) strictly decreasing order
2.8.
Solution: (C) 7, 8, 9, 6, 5
2.9.
Solution: (B) Stack
2.10.
Solution: (D) D
2.11.
Solution: (C) c a b
2.12.
Solution: (B) Job scheduling
2.13.
Solution: (A) ABD^ + EF – / G+
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Stack

Author Manan Singhal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs

  1. Define Stack?
    A stack is a container of objects that performs insertion and removed elements according to the last-in-first-out (LIFO) principle.
     
  2. Explain why stack is known as a recursive data structure?
    A stack is known as a recursive data structure, so it's a stack is either empty or consists of a top and the rest, a stack by itself.
     
  3. Why Are Stacks Useful?
    They're beneficial because they afford you constant time O(1) operations when inserting or removing from the front of a data structure.
     
  4. Can we reverse a string using a stack?
    Yes, reversing a string using a stack is possible.
     
  5. How to implement Linked List using stack?
  • To add an element at the head, push that item onto the stack.
  • To remove an item from the head, pop the item from the stack.
  • To insert into the middle, pop items from the list stack and push them onto some secondary stack until you get to your insertion point and then push the new item onto the list stack, pop from the temporary stack, and push back onto the list stack. Deletion of an arbitrary node is similar.

Key Takeaways

In this article, we have discussed stack previous year's questions. We hope that this blog will help you understand the questions based on the stack that comes in competitive GATE exams. Do upvote our blog to help other ninjas grow.

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!

Previous article
Linked list Gate Questions
Next article
Queue Gate Questions
Live masterclass