UGC NET CSE | August 2016 | Part 2 | Question: 24

Question

Consider the following statements :

$S_{1}$ : A queue can be implemented using two stacks.

$S_{2}$ : A stack can be implemented using two queues.

Which of the following is correct ?

• A. $S_{1}$ is correct and $S_{2}$ is not correct.
• B. $S_{1}$ is not correct and $S_{2}$ is correct.
• C. Both $S_{1}$ and $S_{2}$ are correct.
• D. Both $S_{1}$ and $S_{2}$ are not correct.

Answer 1

Both of the statements are true.Lets understand one by one.In both the cases , we are making enqueue simpler and dequeue operation costlier.

Explanation of statement 1:

Let us have 2 stacks S₁ and S₂ for  our purpose.For enqueue operation , we simply push in S₁.For dequeue operation , we have 2 cases :

a) S₂ is not empty : In that case ,we simply pop from this stack.

b) S₂ is empty : In that case , first we pop all elements from S₁ and push into S₂.After pushing all the elements from S₁ to S₂ we pop the topmost element from S₂.

Explanation of statement 2:

For this we take 2 queues , say Q₁ and Q₂. Now ,

For push operation of stack , we simply enqueue into that queue which is not empty.

For pop operation , in any case , we do the following :

a) Dequeue all elements from the queue which is non empty and enqueue into the empty queue.

b) Then dequeue the front element from the queue where enqueue has been performed recently.

Hence, both statements S₁ and S₂ are true.Hence C is the correct option.

Comments

@habibkhan, Please check these lines again -

For push operation of stack , we simply enqueue into that queue which is not empty.

For pop operation , in any case , we do the following :

a) Dequeue all elements from the queue which is non empty and enqueue into the empty queue.

b) Then dequeue the front element from the queue where enqueue has been performed recently.

Let us do enqueue - 1, 2, 3, 4, 5

Now in the first line you said that we simply enqueue into that queue which is not empty, in the begning we will aways have an empty quueue .. right ??

---

Now, In cae of pop, you said that Dequeue all elements from the queue which is non empty and enqueue into the empty queue.

Lets say, q1 contains - 1, 2, 3, 4 and q2 is empty.

After doing the first operation for pop, q2 = 1, 2, 3, 4   and q1 will become empty ... right  ??

---

Now, In the 2nd operation for pop you said that, Then dequeue the front element from the queue where enqueue has been performed recently, and I think it will return 1 right ?? but it should return 4, because it was the last element which was inserted into the queue in the last push operation ... right ??

---

If you have further query then you may look at the following links:

http://stackoverflow.com/questions/688276/implement-stack-using-two-queues

http://www.geeksforgeeks.org/implement-stack-using-queue/

---

okay, Thanks @habibkhan :)