Question:
Consider a stack \(S\) and a queue \(Q\). Both of them are initially empty and have the capacity to store ten elements each. The elements \(1, 2, 3, 4\), and \(5\) arrive one by one, in that order. When an element arrives, it is assigned either to \(S\) (pushed on \(S\)) or to \(Q\) (enqueued to \(Q\)). Once all the five elements are stored, the output is generated in two steps. First, stack \(S\) is emptied by popping all elements. Then queue \(Q\) is emptied by dequeueing all elements. The output obtained by following this process is \(4\ 3\ 1\ 2\ 5\).
Given the output, the objective is to predict whether an element was assigned to \(S\) or \(Q\).
Which of the following options is/are possible valid assignment(s) of the elements?
Note: In the options, the notation \(xS\) denotes that element \(x\) was assigned to \(S\) and \(yQ\) denotes that element \(y\) was assigned to \(Q\).
Consider a stack \(S\) and a queue \(Q\). Both of them are initially empty and have the capacity to store ten elements each. The elements \(1, 2, 3, 4\), and \(5\) arrive one by one, in that order. When an element arrives, it is assigned either to \(S\) (pushed on \(S\)) or to \(Q\) (enqueued to \(Q\)). Once all the five elements are stored, the output is generated in two steps. First, stack \(S\) is emptied by popping all elements. Then queue \(Q\) is emptied by dequeueing all elements. The output obtained by following this process is \(4\ 3\ 1\ 2\ 5\).
Given the output, the objective is to predict whether an element was assigned to \(S\) or \(Q\).
Which of the following options is/are possible valid assignment(s) of the elements?
Note: In the options, the notation \(xS\) denotes that element \(x\) was assigned to \(S\) and \(yQ\) denotes that element \(y\) was assigned to \(Q\).
Given the output, the objective is to predict whether an element was assigned to \(S\) or \(Q\).
Which of the following options is/are possible valid assignment(s) of the elements?
Note: In the options, the notation \(xS\) denotes that element \(x\) was assigned to \(S\) and \(yQ\) denotes that element \(y\) was assigned to \(Q\).
Show Hint
Reverse only the elements sent to the stack, keep the elements sent to the queue in their original arrival order, and check which split matches 4 3 1 2 5.
Updated On: Jul 22, 2026
- \(1S, 2Q, 3S, 4S, 5Q\)
- \(1Q, 2Q, 3S, 4S, 5Q\)
- \(1Q, 2Q, 3Q, 4S, 5S\)
- \(1S, 2S, 3S, 4Q, 5Q\)
Show Solution
Verified By Collegedunia
The Correct Option is A, B
Solution and Explanation
Step 1: Set up how the output is built.
Every element sent to \(S\) is pushed in arrival order, and popping a stack reverses that order. Every element sent to \(Q\) is enqueued in arrival order, and dequeuing a queue preserves that order. So if \(S_{list}\) is the elements sent to \(S\), listed in the order they arrived, and \(Q_{list}\) is the elements sent to \(Q\), listed in the order they arrived, then the final printed output is
\[ \text{output} = \text{reverse}(S_{list})\ \text{followed by}\ Q_{list} \]
We are told this output must equal \(4\ 3\ 1\ 2\ 5\). We check each option by building \(S_{list}\) and \(Q_{list}\) and testing this rule.
Step 2: Test option (A), \(1S, 2Q, 3S, 4S, 5Q\).
Elements sent to \(S\) in arrival order: \(1, 3, 4\), so \(S_{list}=(1,3,4)\), and reversing gives \((4,3,1)\). Elements sent to \(Q\) in arrival order: \(2, 5\), so \(Q_{list}=(2,5)\). Putting them together:
\[ (4,3,1)+(2,5) = 4\ 3\ 1\ 2\ 5 \]
This matches the required output, so option (A) is valid.
Step 3: Test option (B), \(1Q, 2Q, 3S, 4S, 5Q\).
Elements sent to \(S\): \(3, 4\), so \(S_{list}=(3,4)\), reversed gives \((4,3)\). Elements sent to \(Q\): \(1, 2, 5\), so \(Q_{list}=(1,2,5)\). Together:
\[ (4,3)+(1,2,5) = 4\ 3\ 1\ 2\ 5 \]
This also matches, so option (B) is valid.
Step 4: Test option (C), \(1Q, 2Q, 3Q, 4S, 5S\).
Elements sent to \(S\): \(4, 5\), reversed gives \((5,4)\). Elements sent to \(Q\): \(1, 2, 3\). Together:
\[ (5,4)+(1,2,3) = 5\ 4\ 1\ 2\ 3 \]
This does not equal \(4\ 3\ 1\ 2\ 5\), so option (C) is not valid.
Step 5: Test option (D), \(1S, 2S, 3S, 4Q, 5Q\).
Elements sent to \(S\): \(1, 2, 3\), reversed gives \((3,2,1)\). Elements sent to \(Q\): \(4, 5\). Together:
\[ (3,2,1)+(4,5) = 3\ 2\ 1\ 4\ 5 \]
This does not equal \(4\ 3\ 1\ 2\ 5\), so option (D) is not valid.
Step 6: Final answer.
Only options (A) and (B) reproduce the required output.
\[ \boxed{\text{(A) and (B)}} \]
Every element sent to \(S\) is pushed in arrival order, and popping a stack reverses that order. Every element sent to \(Q\) is enqueued in arrival order, and dequeuing a queue preserves that order. So if \(S_{list}\) is the elements sent to \(S\), listed in the order they arrived, and \(Q_{list}\) is the elements sent to \(Q\), listed in the order they arrived, then the final printed output is
\[ \text{output} = \text{reverse}(S_{list})\ \text{followed by}\ Q_{list} \]
We are told this output must equal \(4\ 3\ 1\ 2\ 5\). We check each option by building \(S_{list}\) and \(Q_{list}\) and testing this rule.
Step 2: Test option (A), \(1S, 2Q, 3S, 4S, 5Q\).
Elements sent to \(S\) in arrival order: \(1, 3, 4\), so \(S_{list}=(1,3,4)\), and reversing gives \((4,3,1)\). Elements sent to \(Q\) in arrival order: \(2, 5\), so \(Q_{list}=(2,5)\). Putting them together:
\[ (4,3,1)+(2,5) = 4\ 3\ 1\ 2\ 5 \]
This matches the required output, so option (A) is valid.
Step 3: Test option (B), \(1Q, 2Q, 3S, 4S, 5Q\).
Elements sent to \(S\): \(3, 4\), so \(S_{list}=(3,4)\), reversed gives \((4,3)\). Elements sent to \(Q\): \(1, 2, 5\), so \(Q_{list}=(1,2,5)\). Together:
\[ (4,3)+(1,2,5) = 4\ 3\ 1\ 2\ 5 \]
This also matches, so option (B) is valid.
Step 4: Test option (C), \(1Q, 2Q, 3Q, 4S, 5S\).
Elements sent to \(S\): \(4, 5\), reversed gives \((5,4)\). Elements sent to \(Q\): \(1, 2, 3\). Together:
\[ (5,4)+(1,2,3) = 5\ 4\ 1\ 2\ 3 \]
This does not equal \(4\ 3\ 1\ 2\ 5\), so option (C) is not valid.
Step 5: Test option (D), \(1S, 2S, 3S, 4Q, 5Q\).
Elements sent to \(S\): \(1, 2, 3\), reversed gives \((3,2,1)\). Elements sent to \(Q\): \(4, 5\). Together:
\[ (3,2,1)+(4,5) = 3\ 2\ 1\ 4\ 5 \]
This does not equal \(4\ 3\ 1\ 2\ 5\), so option (D) is not valid.
Step 6: Final answer.
Only options (A) and (B) reproduce the required output.
\[ \boxed{\text{(A) and (B)}} \]
Was this answer helpful?
0
0
Top GATE CS Programming and Data Structures Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- Given N distinct elements in an array, determine the number of comparisons required to find the element which is not the largest:
Consider the following code:
main() { int x = 126, y = 105; { if (x > y) x = x - y; else y = y - x; } while (x != y) printf("%d", x); }- In a binary search tree with the following elements: \( 10, -4, 15, 13, 20, 5, 16, 19 \), the number of edges from node 19 to the root is?
Consider the following code:
int a; int arr[] = {30, 50, 10}; int *ptr = arr[10] + 1; a = *ptr; (*ptr)++; ptr = ptr + 1; printf("%d", a + arr[1] + *ptr);
View More Questions
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?
View More Questions