Question

Are you able to implement a stack using just one queue? If yes, please provide the pop(only) algorithm to simulate the stack operations with just one queue. If yes, please provide the pop(only) algorithm to simulate the stack operations with just one queue. If no, explain.

Answer 1

Stack can be implemented using one queue. The main idea is the size of queue can be found at any time. Also keep the newly inserted element always at rear of queue and do not change the order of previous elements.

Approach:

a is the element to be pushed and s is stack.

push(s, a):

1. Let the size of q be s.

2. Enqueue a to q. (Enqueue means to add elements)

3. One after the other Dequeue s items from queue to enqueue them. (Dequeue means to remove elements)

Removes item from stack.

pop(s):

1. Dequeue an item from q.

There is only one operation in pop that is to take out elements one by one.

Algorithm:

void(pop){

if (queue.isEmpty()){

System.out.println("Queue is empty");

}

else {

   System.out.println(queue.poll());

}

}

Code for push and pop operation: (Java)

import java.util.LinkedList;
import java.util.Queue;

public class StackUsingQueue
{
   Queue<Integer> q = new LinkedList<Integer>();
  
   // Push operation of Stack
   void push(int a)
   {
       // get previous size of queue
       int size = q.size();
      
       // Add current element
       q.add(a);
      
       // Pop all previous elements and put them after current  element
       for (int i = 0; i < size; i++)
       {
           // this will add front element into rear (back) of queue
           int x = q.remove();
           q.add(x);
       }
   }
  
   // Removes the top element (Pop operation)
   int pop()
   {
       if (q.isEmpty())
       {
           System.out.println("No element is in the queue");
           return -1;
       }
       int x = q.remove();
       return x;
   }
  
   // Returns the top of stack
   int top()
   {
       if (q.isEmpty())
           return -1;
       return q.peek();
   }
  
   // Returns true if Stack is empty else it will return false
   boolean isEmpty()
   {
       return q.isEmpty();
   }

   // This is the driver program to test the methods implemented above
   public static void main(String[] args)
   {
       stack s = new stack();
       s.push(500);
       s.push(800);
       System.out.println("Top element of stack:" + s.top());
       s.pop(); //pop the element
       s.push(150); //push the element
       s.pop();
       System.out.println("Top element of stack :" + s.top());
   }
}

Note: Without push operation it is difficult to understand pop and so I have coded both for your ease.

I hope this helps you. Thankyou.