Register

GO Classes DPP | GATE CS, DA | Data Structure | Stack Permutation

• recategorized by
358 views
6 6 votes

Suppose an intermixed sequence of stack push and pop operations is performed. The push operations push the integers $0$ through $9$ in order. The pop operations print the returned values.

Which of the following output sequences could NOT occur?

  1. $\texttt{4 3 2 1 0 9 8 7 6 5}$

  2. $\texttt{4 6 8 7 5 3 2 9 0 1}$

  3. $\texttt{2 5 6 7 4 8 9 3 1 0}$

  4. $\texttt{4 3 2 1 0 5 6 7 8 9}$

  5. $\texttt{1 2 3 4 5 6 9 8 7 0}$

  6. $\texttt{0 4 6 5 3 8 1 7 2 9}$

  7. $\texttt{1 4 7 9 8 6 5 3 0 2}$

  8. $\texttt{2 1 4 3 6 5 8 7 9 0}$

3 Answers

1 1 vote

A stack follows LIFO order. Once a larger later item is pushed above smaller earlier items, the lower item cannot be popped before the items above it.

In option B, after producing part of the sequence, $1$ blocks $0$, so $0$ cannot come before $1$.

In option F, after some required pushes, an item below the stack is demanded before the item above it. This violates LIFO order.

In option G, the output asks for $0$ before $2$, even though $2$ is above $0$ on the stack at that stage.

Therefore, the impossible sequences are B, F and G.

0 0 votes

In B 0 is coming before 1 not possible 

In F 1 is coming before 2 not possible

In G 0 is coming before 2 not possible

So answer is B, F , G

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · Question from Keneth...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

7 7 votes
3 3 answers
314
314 views
GO Classes asked Jul 8
314 views
GO Classes DPP | GATE CS, DA | Data Structure | Stack Output
A stack client reads tokens from left to right. If the token is a word, it is pushed onto the stack. If the token is $\texttt{-}$, one item is popped and printed.Consider...
5 5 votes
2 2 answers
266
266 views
GO Classes asked Jul 9
266 views
GO Classes DPP | GATE CS, DA | Data Structure | Balanced Brackets
A stack is used to check whether parentheses, braces, and brackets are properly balanced.Consider the following two inputs:Input $1: \texttt{[()]\{\}\{[()()]()\}}$Input $...
7 7 votes
1 1 answer
361
361 views
GO Classes asked Jul 10
361 views
GO Classes DPP | GATE CS, DA | Data Structure | Stack Implementation & DFS
Assume there are $n$ elements in the data structure. Consider the following statements:$\text{S1}:$ A stack can be implemented using a linked list such that each individu...
4 4 votes
1 1 answer
224
224 views
GO Classes asked Jul 10
224 views
GO Classes DPP | GATE CS, DA | Data Structure | Queue Order
Suppose a client performs an intermixed sequence of $\texttt{enqueue}$ and $\texttt{dequeue}$ operations on a queue. The enqueue operations put the integers $0$ through $...