Implement a stack using single queue

Last Updated : 31 Jul, 2022

We are given queue data structure, the task is to implement stack using only given queue data structure.
We have discussed a solution that uses two queues. In this article, a new solution is discussed that uses only one queue. This solution assumes that we can find size of queue at any point. The idea is to keep newly inserted element always at front of queue, keeping order of previous elements same.

Below are complete steps.

// x is the element to be pushed and s is stack
push(s, x) 
  1) Let size of q be s. 
  1) Enqueue x to q
  2) One by one Dequeue s items from queue and enqueue them.
  
// Removes an item from stack
pop(s)
  1) Dequeue an item from q

Below is implementation of the idea.

C++

// C++ program to implement a stack using
// single queue
#include<bits/stdc++.h>
using namespace std;
 
// User defined stack that uses a queue
class Stack
{
    queue<int>q;
public:
    void push(int val);
    void pop();
    int top();
    bool empty();
};
 
// Push operation
void Stack::push(int val)
{
    //  Get previous size of queue
    int s = q.size();
 
    // Push current element
    q.push(val);
 
    // Pop (or Dequeue) all previous
    // elements and put them after current
    // element
    for (int i=0; i<s; i++)
    {
        // this will add front element into
        // rear of queue
        q.push(q.front());
 
        // this will delete front element
        q.pop();
    }
}
 
// Removes the top element
void Stack::pop()
{
    if (q.empty())
        cout << "No elements\n";
    else
        q.pop();
}
 
// Returns top of stack
int  Stack::top()
{
    return (q.empty())? -1 : q.front();
}
 
// Returns true if Stack is empty else false
bool Stack::empty()
{
    return (q.empty());
}
 
// Driver code
int main()
{
    Stack s;
    s.push(10);
    s.push(20);
    cout << s.top() << endl;
    s.pop();
    s.push(30);
    s.pop();
    cout << s.top() << endl;
    return 0;
}

Java

// Java program to implement stack using a 
// single queue
 
import java.util.LinkedList;
import java.util.Queue;
 
public class stack 
{
    Queue<Integer> q = new LinkedList<Integer>();
     
    // Push operation
    void push(int val) 
    {
        // get previous size of queue
        int size = q.size();
         
        // Add current element
        q.add(val);
         
        // Pop (or Dequeue) all previous
        // elements and put them after current
        // element
        for (int i = 0; i < size; i++) 
        {
            // this will add front element into
            // rear of queue
            int x = q.remove();
            q.add(x);
        }
    }
     
    // Removes the top element
    int pop() 
    {
        if (q.isEmpty()) 
        {
            System.out.println("No elements");
            return -1;
        }
        int x = q.remove();
        return x;
    }
     
    // Returns top of stack
    int top() 
    {
        if (q.isEmpty())
            return -1;
        return q.peek();
    }
     
    // Returns true if Stack is empty else false
    boolean isEmpty() 
    {
        return q.isEmpty();
    }
 
    // Driver program to test above methods
    public static void main(String[] args) 
    {
        stack s = new stack();
        s.push(10);
        s.push(20);
        System.out.println("Top element :" + s.top());
        s.pop();
        s.push(30);
        s.pop();
        System.out.println("Top element :" + s.top());
    }
}
 
// This code is contributed by Rishabh Mahrsee

Python3

# Python3 program to implement stack using a 
# single queue 
  
q = []
 
# append operation 
def append(val):
 
    # get previous size of queue 
    size = len(q)
 
    # Add current element 
    q.append(val); 
 
    # Pop (or Dequeue) all previous 
    # elements and put them after current
    # element
    for i in range(size):
 
        # this will add front element into 
        # rear of queue 
        x = q.pop(0); 
        q.append(x); 
            
# Removes the top element 
def pop():
 
    if (len(q) == 0):
 
        print("No elements"); 
        return -1; 
     
    x = q.pop(0); 
    return x; 
 
# Returns top of stack 
def top():
 
    if(len(q) == 0):
        return -1; 
    return q[-1]
 
# Returns true if Stack is empty else false 
def isEmpty():
 
    return len(q)==0; 
 
# Driver program to test above methods 
if __name__=='__main__':
 
    s = []
 
    s.append(10); 
    s.append(20); 
    print("Top element :" + str(s[-1])); 
    s.pop(); 
    s.append(30); 
    s.pop(); 
    print("Top element :" + str(s[-1]));
     
    # This code is contributed by rutvik_56.

C#

// C# program to implement stack using a 
// single queue
using System;
using System.Collections.Generic;
 
public class stack 
{
    Queue<int> q = new Queue<int>();
     
    // Push operation
    void push(int val) 
    {
        // get previous size of queue
        int size = q.Count;
         
        // Add current element
        q.Enqueue(val);
         
        // Pop (or Dequeue) all previous
        // elements and put them after current
        // element
        for (int i = 0; i < size; i++) 
        {
            // this will add front element into
            // rear of queue
            int x = q.Dequeue();
            q.Enqueue(x);
        }
    }
     
    // Removes the top element
    int pop() 
    {
        if (q.Count == 0) 
        {
            Console.WriteLine("No elements");
            return -1;
        }
        int x = q.Dequeue();
        return x;
    }
     
    // Returns top of stack
    int top() 
    {
        if (q.Count == 0)
            return -1;
        return q.Peek();
    }
     
    // Returns true if Stack is empty else false
    bool isEmpty() 
    {
        if(q.Count == 0)
            return true;
        return false;
    }
 
    // Driver program to test above methods
    public static void Main(String[] args) 
    {
        stack s = new stack();
        s.push(10);
        s.push(20);
        Console.WriteLine("Top element :" + s.top());
        s.pop();
        s.push(30);
        s.pop();
        Console.WriteLine("Top element :" + s.top());
    }
}
 
// This code has been contributed by Rajput-Ji 

Javascript

<script>
    // Javascript program to implement stack using a single queue
    let q = [];
      
    // Push operation
    function Push(val)
    {
        // get previous size of queue
        let Size = q.length;
          
        // Add current element
        q.push(val);
          
        // Pop (or Dequeue) all previous
        // elements and put them after current
        // element
        for (let i = 0; i < Size; i++)
        {
            // this will add front element into
            // rear of queue
            let x = q[0];
            q.shift();
            q.push(x);
        }
    }
  
    // Removes the top element
    function Pop()
    {
        if (isEmpty())
        {
            document.write("No elements" + "</br>");
            return -1;
        }
        let x = q[0];
        q.shift();
        return x;
    }
      
    // Returns top of stack
    function Top()
    {
        if (isEmpty())
            return -1;
        return q[0];
    }
     
    // Returns true if Stack is empty else false
    function isEmpty()
    {
        if(q.length == 0)
            return true;
        return false;
    }
     
    Push(10);
    Push(20);
    document.write(Top() + "</br>");
    Pop();
    Push(30);
    Pop();
    document.write(Top() + "</br>");
 
// This code is contributed by decode2207.
</script>

Output

20
10

Time complexity: O(N) where N is size of stack

Auxiliary Space: O(N)

M

Manu Agrawal

Improve

Previous Article

Design a stack that supports getMin() in O(1) time and O(1) extra space

How to implement stack using priority queue or heap?

Similar Reads

Should we declare as Queue or Priority Queue while using Priority Queue in Java?

Queue: Queue is an Interface that extends the collection Interface in Java and this interface belongs to java.util package. A queue is a type of data structure that follows the FIFO (first-in-first-out ) order. The queue contains ordered elements where insertion and deletion of elements are done at different ends. Priority Queue and Linked List are

Stack and Queue in Python using queue Module

A simple python List can act as queue and stack as well. Queue mechanism is used widely and for many purposes in daily life. A queue follows FIFO rule(First In First Out) and is used in programming for sorting and for many more things. Python provides Class queue as a module which has to be generally created in languages such as C/C++ and Java. 1.

Check if a queue can be sorted into another queue using a stack

Given a Queue consisting of first n natural numbers (in random order). The task is to check whether the given Queue elements can be arranged in increasing order in another Queue using a stack. The operation allowed are: Push and pop elements from the stack Pop (Or Dequeue) from the given Queue. Push (Or Enqueue) in the another Queue. Examples : Inp

Can we use Simple Queue instead of Priority queue to implement Dijkstra's Algorithm?

What is Dijkstra's Algorithm? Dijkstra's Algorithm is used for finding the shortest path between any two vertices of a graph. It uses a priority queue for finding the shortest path. For more detail, about Dijkstra's Algorithm, you can refer to this article. Why Dijkstra's Algorithm uses a Priority Queue? We use min heap in Dijkstra's Algorithm beca

How to implement Stack and Queue using ArrayDeque in Java

ArrayDeque in Java The ArrayDeque in Java provides a way to apply resizable-array in addition to the implementation of the Deque interface. It is also known as Array Double Ended Queue or Array Deck. This is a special kind of array that grows and allows users to add or remove an element from both sides of the queue. ArrayDeque class implements Queu

Implement Stack and Queue using Deque

Deque also known as double ended queue, as name suggests is a special kind of queue in which insertions and deletions can be done at the last as well as at the beginning. A link-list representation of deque is such that each node points to the next node as well as the previous node. So that insertion and deletions take constant time at both the beg

How to implement stack using priority queue or heap?

How to Implement stack using a priority queue(using min heap)? Asked In: Microsoft, Adobe. Solution: In the priority queue, we assign priority to the elements that are being pushed. A stack requires elements to be processed in the Last in First Out manner. The idea is to associate a count that determines when it was pushed. This count works as a k

Most efficient way to implement Stack and Queue together

Introduction to Stack:A stack is a linear data structure in computer science that follows the Last-In-First-Out (LIFO) principle. It is a data structure in which the insertion and removal of elements can only be performed at one end, which is called the top of the stack.In a stack, elements are pushed onto the top of the stack, and elements are pop

Reversing a Queue using another Queue

Given a queue. The task is to reverse the queue using another empty queue. Examples: Input: queue[] = {1, 2, 3, 4, 5} Output: 5 4 3 2 1 Input: queue[] = {10, 20, 30, 40} Output: 40 30 20 10 Approach: Given a queue and an empty queue.The last element of the queue should be the first element of the new queue.To get the last element there is a need to

How to Implement Queue in Java using Array and Generics?

The queue is a linear data structure that follows the FIFO rule (first in first out). We can implement Queue for not only Integers but also Strings, Float, or Characters. There are 5 primary operations in Queue: enqueue() adds element x to the front of the queuedequeue() removes the last element of the queuefront() returns the front elementrear() r

Article Tags :

Practice Tags :