Register

GO Classes DPP | PYTHON & DSA |STACK

• edited by
190 views
0 0 votes

Let $S$ be a stack of size $n$ and $Q$ be a queue of size $n$. An algorithm performs the following sequence of operations:

  1. Push elements $1,2, \ldots, n$ into stack $S$ in that order.
     
  2. Pop all elements from $S$ one by one and Enqueue them into $Q$.
     
  3. Dequeue all elements from $Q$ one by one and Push them back into $S$.
     
  4. Pop all elements from $S$.

In what order are the elements popped in Step $\mathbf{4}$?

  1. $1,2,3, \ldots, n$
     
  2. $n, n-1, n-2, \ldots, 1$
     
  3. $1, n, 2, n-1, \ldots$
     
  4. $n, 1, n-1,2, \ldots$

1 Answer

1 1 vote
Step $1:$ Stack $S=[1,2, \ldots, n]$ $($top is $n)$.

Step $2:$ Pop $S \rightarrow$ Enqueue $Q . Q$ becomes $[n, n-1, \ldots, 1]$ $($Front is $n)$.

Step $3:$ Dequeue $Q \rightarrow$ Push $S . S$ becomes $[n, n-1, \ldots, 1]$ $($top is $1)$.

Step $4:$ Popping $S$ yields $1,2, \ldots, n$.
• edited by
Voting & Accepting an answer helps improve the community
Answer:
← Previous · Asymptotic growthNext → · GO Classes DPP | PYT...
← Previous in category · GO Classes DPP | PYT...Next in category → · GO Classes DPP | PYT...
Position:
Show:

Related questions

1 1 vote
1 1 answer
170
170 views
GO Classes asked Feb 20
170 views
GO Classes DPP | PYTHON & DSA |MERGESORT
Consider the Merge Sort algorithm applied to an array $A$ of $n$ distinct integers. During the Merge step, we maintain two pointers for the sorted subarrays $L$ and $R$. ...
1 1 vote
1 1 answer
154
154 views
GO Classes asked Feb 20
154 views
GO Classes DPP | PYTHON & DSA |GRAPH
Consider a directed weighted graph $G$ with $V$ vertices and $E$ edges. The weights are all positive integers. If we increase the weight of every edge by a constant value...
3 3 votes
1 1 answer
131
131 views
GO Classes asked Feb 20
131 views
GO Classes DPP | PYTHON & DSA |QUICKSORT
Consider the Quicksort algorithm applied to an array of $n$ distinct elements. The pivot is always chosen as the median of the first, middle, and last elements of the cur...
1 1 vote
1 1 answer
134
134 views
GO Classes asked Feb 20
134 views
GO Classes DPP | PYTHON & DSA |BST
The preorder traversal of a Binary Search Tree (BST) is given as$: 15, 10, 12, 11, 20, 18, 16, 22.$ Which of the following statements is/are CORRECT?The postorder travers...