Stack using Queues

Uncategorized

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Stack using Queues”.

1. Making the push operation costly, select the code snippet which implements the same.(let q1 and q2 be two queues)
A)

public void push(int x)
{
        if(empty())
        {
            q1.offer(x);
        }
        else{
                if(q1.size()>0)
                {
                    q2.offer(x);
                    int size = q1.size();
                    while(size>0)
                    {
                        q2.offer(q1.poll());
                        size--;
                    }
                }
            else if(q2.size()>0)
            {
                q1.offer(x);
                int size = q2.size();
                while(size>0)
                {
                    q1.offer(q2.poll());
                    size--;
                }
            }
        }
    }

B)

public void push(int x)
{
        if(empty())
        {
            q1.offer(x);
        }
        else
        {
            if(q1.size()>0)
            {
                q1.offer(x);
                int size = q1.size();
                while(size>0)
                {
                    q2.offer(q1.poll());
                    size--;
                }
            }
            else if(q2.size()>0)
            {
                q2.offer(x);
                int size = q2.size();
                while(size>0)
                {
                    q1.offer(q2.poll());
                    size--;
                }
            }
        }
}

C)

public void push(int x)
{
        if(empty())
        {
            q1.offer(x);
        }
        else
        {
            if(q1.size()>0)
            {
                q2.offer(x);
                int size = q1.size();
                while(size>0)
                {
                    q1.offer(q2.poll());
                    size--;
                }
            }
            else if(q2.size()>0)
            {
                q1.offer(x);
                int size = q2.size();
                while(size>0)
                {
                    q2.offer(q1.poll());
                    size--;
                }
            }
        }
}

D)

public void push(int x)
{
        if(empty())
        {
            q1.offer(x);
        }
        else
        {
            if(q1.size()>0)
            {
                q2.offer(x);
                int size = q1.size();
                while(size>0)
                {
                    q2.offer(q2.poll());
                    size--;
                }
            }
            else if(q2.size()>0)
            {
                q1.offer(x);
                int size = q2.size();
                while(size>0)
                {
                    q2.offer(q1.poll());
                    size--;
                }
            }
        }
}

Answer: A
Explanation: The stack follows the LIFO principle, so a new item added must be the first to exit; however, the queue follows the FIFO principle, so a new item added would be at the back end of the queue. If the queue is initially empty, simply add the new element; otherwise, add the new element to the second queue and dequeue all of the elements from the second queue before enqueuing it to the first, ensuring that the new element is still at the front of the queue. This push process is known to be more expensive because it necessitates the use of two queues.

2. To implement a stack using queue(with only enqueue and dequeue operations), how many queues will you need?
A) 1
B) 2
C) 3
D) 4
Answer: B
Explanation: Either the push or the pop must be an expensive operation, and the more expensive operation necessitates the use of two queues.

3. Select the code snippet which returns the top of the stack.
A)
public int top() {        if(q1.size()>0)        {             return q1.poll();        }        else if(q2.size()>0)        {             return q2.poll();        }        return 0; }
B)
public int top() {        if(q1.size()==0)        {             return q1.peek();        }        else if(q2.size()==0)        {             return q2.peek();        }         return 0;     }
C)
public int top() {        if(q1.size()>0)        {             return q1.peek();        }        else if(q2.size()>0)        {             return q2.peek();        }        return 0; }
D)
public int top() {        if(q1.size()>0)        {             return q2.peek();        }        else if(q2.size()>0)        {             return q1.peek();        }        return 0; }

Answer: C
Explanation: Assuming a push-cost implementation, the top of the stack will be in the queue's front end; note that peek() merely returns the front element, while poll() removes the front element.


 4. Making the push operation costly, select the code snippet which implements the pop operation.
A)
advertisement

public void pop() {         if(q1.size()>0)         {             q2.poll();         }         else if(q2.size()>0)         {             q1.poll();         } }
B)
public void pop() {         if(q1.size()>0)         {             q1.poll();         }         else if(q2.size()>0)         {             q2.poll();         } }
C)
public void pop() {         q1.poll(); q2.poll(); }
D)
public void pop() {         if(q2.size()>0)         {             q1.poll();         }         else         {             q2.poll();         } }

Answer: B
Explanation: Since the push operation is expensive, it is obvious that the necessary item is at the front of the queue; simply dequeue the product.

5. What is the functionality of the following piece of code?
public void fun(int x) { q1.offer(x); }
A) Perform push() with push as the costlier operation
B) Perform push() with pop as the costlier operation
C) Perform pop() with push as the costlier operation
D) Perform pop() with pop as the costlier operation
Answer: B
Explanation: While offer() implies that it is a push operation, we can see that it is only performed with one queue, so the pop operation is more expensive.

6. Making the pop operation costly, select the code snippet which implements the same.
A)
public int pop() { int res=-999,count=0; if(q1.size()>0)         { count = q1.size(); while(count>0) q2.offer(q1.poll()); res = q1.poll(); } if(q2.size()>0)         { count = q2.size(); while(count>0) q1.offer(q2.poll()); res = q2.poll(); } return res; }
B)
public int pop() { int res=-999,count=0; if(q1.size()>0)         { count = q1.size(); while(count>1) q2.offer(q1.poll()); res = q2.poll(); } if(q2.size()>0)         { count = q2.size(); while(count>1) q1.offer(q2.poll()); res = q1.poll(); } return res; }
C)
public int pop() { int res=-999,count=0; if(q1.size()>0)         { count = q1.size(); while(count>1) q2.offer(q1.poll()); res = q1.poll(); } if(q2.size()>0)         { count = q2.size(); while(count>1) q1.offer(q2.poll()); res = q2.poll(); } return res; }
D)
public int pop() { int res=-999,count=0; if(q1.size()>0)         { count = q2.size(); while(count>1) q2.offer(q1.poll()); res = q1.poll(); } if(q2.size()>0)         { count = q1.size(); while(count>1) q1.offer(q2.poll()); res = q2.poll(); } return res; }

Answer: C
Explanation: Since the pop operation is expensive in this case, we'll use two queues. Apart from the first element, all the items from one queue are dequeued and enqueued to the second queue, leaving just one element in the first queue, which is the item we want, so dequeue it and return the result.

7. Select the code snippet which return true if the stack is empty, false otherwise.
A)
public boolean empty() {      return q2.isEmpty(); }
B)
public boolean empty()  {      return q1.isEmpty() || q2.isEmpty(); }
C)
public boolean empty()  {      return q1.isEmpty(); }
D)
public boolean empty()  {      return q1.isEmpty() & q2.isEmpty(); }

Answer: B
Explanation: If both queues are empty, the stack would be empty as well.

The task is to implement a queue using instances of the stack data structure and operations on them, given a stack data structure with push and pop operations. Two stacks can be used to build a queue. Let's name the queue to be implemented q, and the stacks that will be used to implement it stack1 and stack2. Stacks of them. Queues are inevitable. The LIFO principle governs stacks, which means that the element inserted last is the first to emerge from the list. Queues work on the first-in, first-out (FIFO) principle, which means that the element added first is the first to be removed from the queue.

Leave a Reply

Your email address will not be published. Required fields are marked *