Implement Stack Using Queue

Table of Contents
1. Introduction
2. Implement Stack using Queues by making push() costly
3. Implement Stack using Queues by making pop() costly
4. Implement Stack using a single queue
5. Comparison and practical notes
6. When to use which implementation
7. Summary
View more

Introduction

Given a Queue data structure that supports standard operations such as enqueue() and dequeue(), the task is to implement a Stack data structure using only queues and the permitted queue operations. A stack is a Last-In-First-Out (LIFO) structure supporting push, pop, top (or peek) and size operations. A queue is a First-In-First-Out (FIFO) structure with enqueue and dequeue.

Implement Stack using Queues by making push() costly

Idea

Keep the most recently pushed element at the front of one queue (q1) so that a pop() simply dequeues from q1. Use a second queue (q2) to reorder elements when pushing a new element.

Steps

1. push(s, x):
   1. Enqueue x into q2.
   2. Dequeue every element from q1 and enqueue it into q2.
   3. Swap the names (contents) of q1 and q2.
2. pop(s):
   1. Dequeue an item from q1 and return it (if q1 is empty, do nothing or signal underflow).
3. top():
   1. Return the front element of q1 (or a sentinel if empty).
4. size():
   1. Return the size of q1.

Implementation (C++)

#include <bits/stdc++.h> using namespace std; class Stack { // Two inbuilt queues queue<int> q1, q2; public: void push(int x) { // Push x first in empty q2 q2.push(x); // Push all the remaining elements in q1 to q2. while (!q1.empty()) { q2.push(q1.front()); q1.pop(); } // swap the names of two queues queue<int> q = q1; q1 = q2; q2 = q; } void pop() { // if no elements are there in q1 if (q1.empty()) return; q1.pop(); } int top() { if (q1.empty()) return -1; return q1.front(); } int size() { return q1.size(); } }; // Driver code int main() { Stack s; s.push(1); s.push(2); s.push(3); cout << "current size: " << s.size() << endl; cout << s.top() << endl; s.pop(); cout << s.top() << endl; s.pop(); cout << s.top() << endl; cout << "current size: " << s.size() << endl; return 0; }

Sample output

current size: 3 3 2 1 current size: 1

Complexity

• Push: O(N) - every push moves all existing elements from q1 to q2.
• Pop: O(1) - pop is a single dequeue from q1.
• Auxiliary space: O(N) - two queues are used whose total storage is proportional to the number of elements.

Implement Stack using Queues by making pop() costly

Idea

Enqueue new elements into q1. To pop, move all elements except the last from q1 into q2, dequeue the last element (which is the top of the stack), then swap the queues so that q1 again contains all remaining elements in correct order.

Steps

1. push(s, x):
   1. Enqueue x into q1.
2. pop(s):
   1. If q1 is empty, do nothing (or signal underflow).
   2. Dequeue and enqueue into q2 all elements from q1 except the last element.
   3. Dequeue the last element from q1 - this is the popped (returned) value.
   4. Swap the names (contents) of q1 and q2.
3. top():
   1. Similar to pop(), but capture the last element and then ensure it is placed back into q2 before swapping so that the stack is unchanged.
4. size():
   1. Return size of q1.

Implementation (C++)

// Program to implement a stack // using two queue #include <bits/stdc++.h> using namespace std; class Stack { queue<int> q1, q2; public: void pop() { if (q1.empty()) return; // Leave one element in q1 and push others in q2. while (q1.size() != 1) { q2.push(q1.front()); q1.pop(); } // Pop the only left element from q1 q1.pop(); // swap the names of two queues queue<int> q = q1; q1 = q2; q2 = q; } void push(int x) { q1.push(x); } int top() { if (q1.empty()) return -1; while (q1.size() != 1) { q2.push(q1.front()); q1.pop(); } // last pushed element int temp = q1.front(); // to empty the auxiliary queue after last operation q1.pop(); // push last element to q2 q2.push(temp); // swap the two queues names queue<int> q = q1; q1 = q2; q2 = q; return temp; } int size() { return q1.size(); } }; // Driver code int main() { Stack s; s.push(1); s.push(2); s.push(3); cout << "current size: " << s.size() << endl; cout << s.top() << endl; s.pop(); cout << s.top() << endl; s.pop(); cout << s.top() << endl; cout << "current size: " << s.size() << endl; return 0; }

Sample output

current size: 3 3 2 1 current size: 1

Complexity

• Push: O(1) - enqueue to q1 is constant time.
• Pop: O(N) - pop requires moving N-1 elements between queues.
• Auxiliary space: O(N) - two queues are used.

Implement Stack using a single queue

Idea

Use one queue and rotate its elements after every push so that the newly pushed element becomes the front of the queue. This makes push O(N) and pop O(1).

Steps

1. push(s, x):
   1. Record the size s of the queue before inserting the new element.
   2. Enqueue the new element.
   3. Dequeue and re-enqueue the previous s elements one by one so that the newly added element comes to the front.
2. pop(s):
   1. Dequeue from the queue (front is the top of the simulated stack).
3. top():
   1. Return the front element of the queue.
4. size():
   1. Return the queue size.

Implementation (C++)

#include <bits/stdc++.h> using namespace std; // Stack Class that acts as a queue class Stack { queue<int> q; public: void push(int data); void pop(); int top(); int size(); bool empty(); }; // Push operation void Stack::push(int data) { // Get previous size of queue int s = q.size(); // Push the current element q.push(data); // Pop all the previous elements and put them after current element for (int i = 0; i < s; i++) { // Add the front element again q.push(q.front()); // Delete front element q.pop(); } } // Removes the top element void Stack::pop() { if (q.empty()) cout << "No elements
"; 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()); } int Stack::size() { return q.size(); } int main() { Stack st; st.push(1); st.push(2); st.push(3); cout << "current size: " << st.size() << "
"; cout << st.top() << "
"; st.pop(); cout << st.top() << "
"; st.pop(); cout << st.top() << "
"; cout << "current size: " << st.size(); return 0; }

Sample output

current size: 3 3 2 1 current size: 1

Complexity

• Push: O(N) - rotating existing elements after each push.
• Pop: O(1) - dequeue from the front.
• Auxiliary space: O(N) - a single queue holds all elements.

Comparison and practical notes

• All three methods simulate a stack using queues; the trade-off is between which operation is costly (push or pop).
• If the application performs many more push operations than pop, prefer the approach where push is O(1) and pop is O(N) (pop-costly two-queue method).
• If the application needs fast pop and top, prefer the push-costly two-queue method or the single-queue rotation approach (both make pop O(1)).
• The single-queue method uses slightly less bookkeeping (only one container) and is often simpler to implement, but still incurs O(N) push time.
• All methods require O(N) space to store N elements; extra auxiliary queues only hold elements transiently or duplicate references.

When to use which implementation

• Use the two-queue, push-costly method when pop and top must be very fast.
• Use the two-queue, pop-costly method when push is frequent and must be fast.
• Use the single-queue rotation when you want a compact implementation with O(1) pop and O(N) push and prefer a single container.

Summary

It is possible to implement a stack using one or more queues by reordering elements so that the most recently inserted element is accessible at the queue's front. Three standard approaches are: two-queue with push costly, two-queue with pop costly, and a single-queue rotation approach. Choose the approach based on which operation (push or pop) must be optimised in your use case. The provided C++ implementations and complexity analyses give ready patterns for implementation and exam-style understanding.