Skip to content
GATETECH
Official PYQ · 2023Q49Arrays, Stacks and QueuesNAT2 marks

GATE CS 2023 Q49 — Arrays, Stacks and Queues

Explain with AI

Consider a sequence aa of elements a0=1,a1=5,a2=7,a3=8,a4=9a_{0}=1, a_{1}=5, a_{2}=7, a_{3}=8, a_{4}=9, and a5=2a_{5}=2. The following operations are performed on a stack SS and a queue Q,Q, both of which are initially empty.

  1. push\textsf{push} the elements of aa from a0a_{0} to a5a_{5} in that order into SS.
  2. enqueue\textsf{enqueue} the elements of aa from a0a_{0} to a5a_{5} in that order into QQ.
  3. pop\textsf{pop} an element from SS.
  4. dequeue\textsf{dequeue} an element from QQ.
  5. pop\textsf{pop} an element from SS.
  6. dequeue\textsf{dequeue} an element from QQ.
  7. dequeue\textsf{dequeue} an element from QQ and push the same element into SS.
  8. Repeat operation VII\text{VII} three times.
  9. pop\textsf{pop} an element from SS.
  10. pop\textsf{pop} an element from SS.

The top element of SS after executing the above operations is ______________.

View worked solution

Answer: 8

Let us trace the operations on the stack SS and queue QQ step-by-step. The initial sequence is a=[1,5,7,8,9,2]a = [1, 5, 7, 8, 9, 2].

  1. Operations I & II: Push and enqueue all elements of aa.
    • S=[1,5,7,8,9,2]S = [1, 5, 7, 8, 9, 2]   (top is 22)
    • Q=[1,5,7,8,9,2]Q = [1, 5, 7, 8, 9, 2]   (front is 11)
  2. Operations III & IV: Pop from SS and dequeue from QQ.
    • S=[1,5,7,8,9]S = [1, 5, 7, 8, 9]   (pops 22)
    • Q=[5,7,8,9,2]Q = [5, 7, 8, 9, 2]   (dequeues 11)
  3. Operations V & VI: Pop from SS and dequeue from QQ.
    • S=[1,5,7,8]S = [1, 5, 7, 8]   (pops 99)
    • Q=[7,8,9,2]Q = [7, 8, 9, 2]   (dequeues 55)
  4. Operation VII: Dequeue from QQ (77) and push to SS.
    • Q=[8,9,2]Q = [8, 9, 2]
    • S=[1,5,7,8,7]S = [1, 5, 7, 8, 7]
  5. Operation VIII: Repeat operation VII three times.
    • First repeat: Dequeue 88 and push to SS.
      Q=[9,2]Q = [9, 2],   S=[1,5,7,8,7,8]S = [1, 5, 7, 8, 7, 8]
    • Second repeat: Dequeue 99 and push to SS.
      Q=[2]Q = [2],   S=[1,5,7,8,7,8,9]S = [1, 5, 7, 8, 7, 8, 9]
    • Third repeat: Dequeue 22 and push to SS.
      Q=[]Q = [],   S=[1,5,7,8,7,8,9,2]S = [1, 5, 7, 8, 7, 8, 9, 2]
  6. Operations IX & X: Pop twice from SS.
    • Pop 1: S=[1,5,7,8,7,8,9]S = [1, 5, 7, 8, 7, 8, 9]   (pops 22)
    • Pop 2: S=[1,5,7,8,7,8]S = [1, 5, 7, 8, 7, 8]   (pops 99)

After all operations, the stack is S=[1,5,7,8,7,8]S = [1, 5, 7, 8, 7, 8]. The top element of SS is 8.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Arrays, Stacks and Queues questions