Implementation of Queue using one Stack in C++

November 14, 2025

Implementation of Queue using One Stack

In Data Structures and Algorithms (DSA), various techniques are used to solve problems efficiently by combining and transforming different data structures. Understanding how one structure can be implemented using another strengthens problem-solving skills and deepens conceptual clarity.

In this article, we explore a unique approach implementing a queue using just one stack. While queues follow the FIFO (First-In-First-Out) principle and stacks work on LIFO (Last-In-First-Out), clever algorithmic logic allows us to bridge the gap between the two. This concept not only enhances your DSA understanding but also prepares you for interview-oriented coding challenges.

Stack vs Queue?

Stack is a data structure where you get Last in First out implementation, and queue is with first in first out implementation.

So, it seems impossible to turn a stack into a queue. Though by basic using of two stacks we can implement a queue very easily : Queue By 2 stacks.

Algorithm: 

Here we are making a class named Queue, and the objects of the class can be used as real queue type data structure. Now as we need to turn a stack into a queue, the builtin stack class from C++ Standard Template Library is used (Stack in C++ STL).

Here is how to get it done.

  • Firstly, we are going to take one stack. Now stack can push value in the top and pop from there.
  • So the top of the stack is going to be treated as the rear or back of the queue. So pushing value in the queue is easy, pushing value in the stack.
  • For Pop, If the stack is empty, the queue can not pop anything.
  • Now, the pop function or dequeue function is a trick with recursion. 
  • We know recursion uses stack memory to store recursively called functions. Now suppose in the Pop Function, we pop out one element in the stack, and keep base condition after that.
  • The base condition is here as: if the stack is empty, we know the last popped value is the last value in the stack. And the last value in the stack is the front of the queue. So only then we return the value without pushing it back to the stack,
  • Otherwise, we recursively call pop function again, store the value of it in another variable, and after that push the popped out value for that calling in the stack. By this, when the recursion will totally end, the values will be pushed in the order they were popped out, just deleting the last value in the stack.
  • The same way can be used to check the front value too,  using a recursive function.
  • There may be a function called empty, saying if the size is 0 or not.
  • Otherwise we can track how many nodes are there in the queue, using the size variable in the class.
Implementation of queue using stack in C

Types of Queues in Data Structure

Application of Queue Data Structure

Insertion in Queues Program (Enqueuing)

Queues using Linked Lists

Implement Queue using two Stacks

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

Implementation of Queue using Linked List in C++:

The implementation of a Queue using a Linked List in C++ provides an efficient way to manage data in FIFO order with dynamic memory usage. It allows enqueue and dequeue operations to run smoothly without worrying about fixed-size limitations.

  • Uses nodes to store data and pointers, making the queue flexible in size.
  • Enqueue operation inserts elements at the rear of the linked list.
  • Dequeue operation removes elements from the front, ensuring FIFO behavior.
  • No overflow issues since memory is allocated dynamically.
  • Ideal for scenarios where the number of elements isn’t known in advance.

Run

#include<bits/stdc++.h>
using namespace std;

class Queue
{
public:
  stack < int >s;
  int size;
    Queue ()
  {
    size = 0;
  }
  void Push (int i)
  {
    cout << "Pushing the element : " << i << endl;
    s.push (i);
    size++;
  }
  int pop ()
  {
    if (size == 0)
      {
	cout << "The Queue is empty" << endl;
	return 0;
      }
    int a = s.top ();
    s.pop ();
    if (!s.empty ())
      {
	int b = pop ();
	s.push (a);
	return b;
      }
    else
      {
	cout << "Popping " << a << endl;
	size--;
      }
    return a;

  }
  void display ()
  {
    if (size == 0)
      {
	cout << "The Queue is empty" << endl;
	return;
      }
    int a = s.top ();
    s.pop ();
    if (!s.empty ())
      display ();
    cout << a << " ";
    s.push (a);
  }
  int front ()
  {
    if (size == 0)
      {
	cout << "The Queue is empty" << endl;
      }
    int b, a = s.top ();
    s.pop ();
    if (!s.empty ())
      {
	int b = front ();
	s.push (a);
	return b;
      }
    else
      b = a;
    s.push (a);
    return a;
  }
  bool empty ()
  {
    return size == 0;
  }
};

int main ()
{
  Queue q;
  q.Push (1);
  q.Push (5);
  q.Push (2);
  q.Push (11);
  q.display ();
  cout << endl;
  cout << "The front most value right now is : " << q.front () << endl;
  q.pop ();
  q.pop ();
  q.Push (12);
  q.Push (8);
  cout << "The front most value right now is : " << q.front () << endl;
  q.display ();
  cout << endl;
}

 

Output

 

Pushing the element : 1
Pushing the element : 5
Pushing the element : 2
Pushing the element : 11
1 5 2 11
The front most value right now is : 1
Popping 1
Popping 5
Pushing the element : 12
Pushing the element : 8
The front most value right now is : 2
2 11 12 8

Explanation:

  • The queue is implemented using a single stack, and recursion is used to access the bottom-most element, which represents the front of the queue.
  • The Push() function simply inserts elements on top of the stack, maintaining the LIFO nature while counting size.
  • The pop() function recursively pops elements until it reaches the bottom element, removes it as the actual queue pop, and then pushes all other elements back in order.
  • The front() function uses the same recursive approach as pop() but does not remove the element; it just retrieves the bottom-most value and restores the stack.
  • The display() function prints elements from bottom to top using recursion, ensuring the original order of elements is preserved after printing.

Time & Space Complexity:

Operation Time Complexity Space Complexity
Push() O(1) O(1)
Pop() O(n) — due to recursive bottom search O(n) — recursion stack
Front() O(n) — recursive traversal O(n) — recursion stack
Display() O(n) — prints all elements O(n) — recursion depth
Empty() O(1) O(1)

To wrap it up:

The article presents a clear and practical way to implement a queue using just one stack and recursion, efficiently mimicking FIFO behavior even though a single stack inherently offers LIFO operations. The key takeaway is that by using recursion to reach the bottom of the stack when popping or retrieving the front element, the code effectively treats the stack’s base as the queue’s front.

While this method cleverly uses built in stack operations and recursion, it is important to keep in mind that it may not be the most optimal for large datasets due to extra recursive calls. Overall, the tutorial offers a good tool in your DSA toolkit when you want to implement a queue using stack constraints.

FAQs

Recursion helps reach the bottom-most element of the stack, which represents the front of the queue. This allows the structure to behave like a queue even though only one stack is used.

During dequeue, elements are popped one by one using recursion until the last element is reached, which is returned as the queue’s front. All other elements are then pushed back to restore the stack.

The enqueue operation is O(1), while the dequeue operation takes O(n) time due to recursive popping and restoring of stacked elements.

This approach is clever but not the most efficient for large inputs because dequeue operations take linear time. It is mainly useful for learning or solving constrained problems.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout

Stacks

  • Introduction to Stack in Data Structure
    Click Here
  • Operations on a Stack
    Click Here
  • Stack: Infix, Prefix and Postfix conversions
    Click Here
  • Stack Representation in –
    C | C++ | Java
  • Representation of a Stack as an Array. –
    C | C++ | Java
  • Representation of a Stack as a Linked List. –
    C | C++ | Java
  • Infix to Postfix Conversion –
    C | C++ | Java
  • Infix to prefix conversion in –
    C | C++ | Java
  • Postfix to Prefix Conversion in –
    C | C++ | Java

Queues

  • Queues in Data Structures (Introduction)
    Click Here
  • Queues Program in C and implementation
    Click Here
  • Implementation of Queues using Arrays | C Program
    Click Here
  • Types of Queues in Data Structure
    Click Here
  • Application of Queue Data Structure
    Click Here
  • Insertion in Queues Program (Enqueuing) –
    C | C++ | Java
  • Deletion (Removal) in Queues Program(Dequeuing) –
    C | C++ | Java
  • Reverse a Queue –
    C | C++ | Java
  • Queues using Linked Lists –
    C | C++ | Java
  • Implement Queue using Stack –
    C | C++ | Java
  • Implement Queue using two Stacks –
    C | C++ | Java

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction –
    C | C++ | Java
  • Priority Queue Implementation using Array –
    C | C++ | Java
  • Priority Queue using Linked List –
    C | C++ | Java
  • Priority Queue Insertion and Deletion-
    C | C++ | Java

Stacks

Queues

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction – C | C++ | Java
  • Priority Queue Implementation using Array – C | C++ | Java
  • Priority Queue using Linked List – C | C++ | Java
  • Priority Queue Insertion and Deletion- C | C++ | Java