Register

GO Classes DPP | GATE CS, DA | Data Structure | Queue Order

• edited by
211 views
4 4 votes

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 $9$ in order onto the queue. The dequeue operations print the returned values.

Which of the following output sequences could NOT occur?

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

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

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

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

1 Answer

1 1 vote

A queue follows FIFO order, which means first-in-first-out.

Since the values are enqueued in this order:

$\text{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$

the dequeue output must preserve this same relative order.

Option A can occur because it is exactly the enqueue order.

Options B, C and D cannot occur because they output later inserted elements before earlier inserted elements.

Therefore, the impossible sequences are B, C and D.

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

Related questions

6 6 votes
3 3 answers
344
344 views
GO Classes asked Jul 8
344 views
GO Classes DPP | GATE CS, DA | Data Structure | Stack Permutation
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...
7 7 votes
1 1 answer
341
341 views
GO Classes asked Jul 10
341 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...
5 5 votes
2 2 answers
256
256 views
GO Classes asked Jul 9
256 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
3 3 answers
302
302 views
GO Classes asked Jul 8
302 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...