Then queue π 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 π or π.
Which of the following options is/are possible valid assignment(s) of the elements?
Note: In the options, the notation π₯π denotes that element π₯ was assigned to π and yπ denotes that element π¦ was assigned to π.
Correct : a,b
The output is 4 3 1 2 5. Stack S is emptied first by popping (LIFO), then Queue Q is emptied by dequeueing (FIFO). So whatever comes out of S appears at the front of the output, and whatever comes out of Q follows at the end.
Option A β 1S, 2Q, 3S, 4S, 5Q
S gets 1, 3, 4 in that order. Popping gives 4, 3, 1. Q gets 2, 5. Dequeueing gives 2, 5. Full output: 4 3 1 2 5 β
Option B β 1Q, 2Q, 3S, 4S, 5Q
S gets 3, 4. Popping gives 4, 3. Q gets 1, 2, 5. Dequeueing gives 1, 2, 5. Full output: 4 3 1 2 5 β
Option C β 1Q, 2Q, 3Q, 4S, 5S
S gets 4, 5. Popping gives 5, 4. But output starts with 4 3, not 5 4. β
Option D β 1S, 2S, 3S, 4Q, 5Q
S gets 1, 2, 3. Popping gives 3, 2, 1. But output starts with 4 3, not 3 2. β
Correct answer: A and B β
Similar Questions
Total Unique Visitors