Implement Queue using Stacks

Try it on GfG Practice

Implement a queue using stacks. We are allowed to use only stack data structure.

The queue should support the following operations:

• enqueue(x): Insert element x at the end of the queue.
• dequeue(): Remove the element from the front of the queue. If the queue is empty, do nothing.
• front(): Return the element at the front of the queue. If the queue is empty, return -1.
• size(): Return the number of elements in the queue.

[Approach 1] Making Enqueue Operation Costly - Enqueue in O(n) and Dequeue() in O(1)

A queue can be implemented using two stacks. Let the queue be represented as q, and the stacks used for its implementation be s1 and s2.

In this approach, the enqueue operation is made costly by transferring elements from s1 to s2 before adding the new element. This ensures that the elements in s2 are in the correct order for dequeuing. The dequeue operation remains efficient, as it simply involves popping elements from s2.

Enqueue(x):

• While s1 is not empty, move all elements from s1 to s2.
• Push x into s1.
• Move everything back from s2 to s1.
• This guarantees that the front of the queue is always on top of s1.

Dequeue():

• If s1 is empty → queue is empty (underflow).
• Otherwise, pop from s1.

Front():

• If s1 is empty → return -1.
• Otherwise, return the top element of s1 (since it always represents the front of the queue).

Size():

• Return the current size of s1 (both stacks together always hold exactly n elements).

#include <iostream> #include <stack> using namespace std; class myQueue {  stack<int> s1, s2; public:  // Enqueue operation (costly)  void enqueue(int x) {    // Move all elements from s1 to s2  while (!s1.empty()) {  s2.push(s1.top());  s1.pop();  }  // Push the new item into s1  s1.push(x);  // Push everything back to s1  while (!s2.empty()) {  s1.push(s2.top());  s2.pop();  }  }  // Dequeue operation  void dequeue() {  if (s1.empty()) {    // Queue underflow  return;   }    s1.pop();  }  // Front operation  int front() {  if (s1.empty()) {    // Queue empty  return -1;   }  return s1.top();  }  // Size operation  int size() {  return s1.size();  } }; // Driver code int main() {  myQueue q;  q.enqueue(1);  q.enqueue(2);  q.enqueue(3);  cout << "Front: " << q.front() << '\n';   cout << "Size: " << q.size() << '\n';   q.dequeue();   cout << "Front: " << q.front() << '\n';   cout << "Size: " << q.size() << '\n';   return 0; } 

import java.util.Stack; class GfG {  static class myQueue {  Stack<Integer> s1 = new Stack<>();  Stack<Integer> s2 = new Stack<>();  // Enqueue operation (costly)  void enqueue(int x) {    // Move all elements from s1 to s2  while (!s1.isEmpty()) {  s2.push(s1.pop());  }  // Push the new item into s1  s1.push(x);  // Push everything back to s1  while (!s2.isEmpty()) {  s1.push(s2.pop());  }  }  // Dequeue operation  void dequeue() {  if (s1.isEmpty()) {    // Queue underflow  return;   }  s1.pop();  }  // Front operation  int front() {  if (s1.isEmpty()) {    // Queue empty  return -1;   }  return s1.peek();  }  // Size operation  int size() {  return s1.size();  }  }  public static void main(String[] args) {  myQueue q = new myQueue();  q.enqueue(1);  q.enqueue(2);  q.enqueue(3);  System.out.println("Front: " + q.front());   System.out.println("Size: " + q.size());     q.dequeue();    System.out.println("Front: " + q.front());  System.out.println("Size: " + q.size());   } } 

class myQueue: def __init__(self): self.s1 = [] self.s2 = [] # Enqueue operation (costly) def enqueue(self, x): # Move all elements from s1 to s2 while self.s1: self.s2.append(self.s1.pop()) # Push the new item into s1 self.s1.append(x) # Move everything back to s1 while self.s2: self.s1.append(self.s2.pop()) # Dequeue operation def dequeue(self): if not self.s1: # Queue underflow return self.s1.pop() # Front operation def front(self): if not self.s1: return -1 return self.s1[-1] # Size operation def size(self): return len(self.s1) if __name__ == "__main__": q = myQueue() q.enqueue(1) q.enqueue(2) q.enqueue(3) print("Front:", q.front()) print("Size:", q.size()) q.dequeue() print("Front:", q.front()) print("Size:", q.size()) 

using System; using System.Collections.Generic; class GfG {  class myQueue {  Stack<int> s1 = new Stack<int>();  Stack<int> s2 = new Stack<int>();  // Enqueue operation (costly)  public void enqueue(int x) {  // Move all elements from s1 to s2  while (s1.Count > 0) {  s2.Push(s1.Pop());  }  // Push item into s1  s1.Push(x);  // Push everything back to s1  while (s2.Count > 0) {  s1.Push(s2.Pop());  }  }  // Dequeue operation  public void dequeue() {  if (s1.Count == 0) {    // Queue underflow  return;   }  s1.Pop();  }  // Front operation  public int front() {  if (s1.Count == 0) {  return -1;   }  return s1.Peek();  }  // Size operation  public int size() {  return s1.Count;  }  }  public static void Main(string[] args) {  myQueue q = new myQueue();  q.enqueue(1);  q.enqueue(2);  q.enqueue(3);  Console.WriteLine("Front: " + q.front());   Console.WriteLine("Size: " + q.size());   q.dequeue();   Console.WriteLine("Front: " + q.front());   Console.WriteLine("Size: " + q.size());     } } 

class myQueue {  constructor() {  this.s1 = [];  this.s2 = [];  }  // Enqueue operation (costly)  enqueue(x) {    // Move all elements from s1 to s2  while (this.s1.length > 0) {  this.s2.push(this.s1.pop());  }  // Push the new item into s1  this.s1.push(x);  // Move everything back to s1  while (this.s2.length > 0) {  this.s1.push(this.s2.pop());  }  }  // Dequeue operation  dequeue() {  if (this.s1.length === 0) {  return;   }  this.s1.pop();  }  // Front operation  front() {  if (this.s1.length === 0) {  return -1;  }  return this.s1[this.s1.length - 1];  }  // Size operation  size() {  return this.s1.length;  } } // Driver code const q = new myQueue(); q.enqueue(1); q.enqueue(2); q.enqueue(3); console.log("Front:", q.front());  console.log("Size:", q.size());  q.dequeue();  console.log("Front:", q.front());  console.log("Size:", q.size());  

Front: 1 Size: 3 Front: 2 Size: 2 

Time Complexity:

• enqueue(x) : O(n) - Move all elements from s1 to s2, push the new element, then move back. Linear in the number of elements n.
• dequeue() : O(1) - Just pop the top element from s1.
• front() : O(1) - Return the top element of s1 without removing it.
• size() : O(1) - Return the number of elements in s1.in the number of elements n.

Space Complexity: O(n) - All elements are stored in the two stacks s1 and s2. No extra space beyond that is needed.

[Approach 2] Making Dequeue Operation Costly - Enqueue in O(1) and Dequeue() in O(n)

In this approach, the new element is pushed onto the top of s1 during the enqueue operation. For the dequeue operation, if s2 is not empty then top of s2 needs to be returned. Otherwise all elements are transferred from s1 to s2, and the element at the top of s2 is returned.

enqueue(q, x)

• Push x onto s1.

dequeue(q)

• If both s1 and s2 are empty → queue underflow.
• If s2 is empty while s1 is not empty, pop elements from s1 and push them to s2.
• Pop the element from s2 and return it.

front()

• If s2 is not empty → top of s2 is the front.
• Else, if s1 is not empty → bottom of s1 is the front (can be accessed indirectly via transfer).
• If both empty → queue is empty.

size()

• Total size = s1.size() + s2.size()

#include <iostream> #include <stack> using namespace std; class myQueue {  stack<int> s1, s2;   public:  // Enqueue operation (O(1))  void enqueue(int x) {  s1.push(x);  }  // Dequeue operation   void dequeue() {    // If both stacks are empty → queue underflow  if (s1.empty() && s2.empty()) return;  // If s2 is empty, move all elements from s1  if (s2.empty()) {  while (!s1.empty()) {  s2.push(s1.top());  s1.pop();  }  }  s2.pop();  }  // Return the front element without removing it  int front() {  if (!s2.empty()) return s2.top();  if (!s1.empty()) {    // Move all elements to s2 to access front  while (!s1.empty()) {  s2.push(s1.top());  s1.pop();  }  int x = s2.top();  return x;  }    // Queue empty  return -1;   }  // Return the current size of the queue  int size() {  return s1.size() + s2.size();  } }; int main() {  myQueue q;  q.enqueue(1);  q.enqueue(2);  q.enqueue(3);  cout << "Front: " << q.front() << "\n";   cout << "Size: " << q.size() << "\n";   q.dequeue();   cout << "Front: " << q.front() << "\n";   cout << "Size: " << q.size() << "\n";     return 0; } 

import java.util.Stack; class GfG {  static class myQueue {  Stack<Integer> s1 = new Stack<>();  Stack<Integer> s2 = new Stack<>();  // Enqueue an item to the queue  void enqueue(int x) {  s1.push(x);  }  // Dequeue an item from the queue  void dequeue() {  if (s1.isEmpty() && s2.isEmpty()) {    // Queue underflow  return;  }  if (s2.isEmpty()) {  while (!s1.isEmpty()) {  s2.push(s1.pop());  }  }  s2.pop();  }  // Return the front element without removing it  int front() {  if (!s2.isEmpty()) {  return s2.peek();  }  if (!s1.isEmpty()) {    // Move elements to s2 to access front  while (!s1.isEmpty()) {  s2.push(s1.pop());  }  return s2.peek();  }    // Queue empty  return -1;   }  // Return the size of the queue  int size() {  return s1.size() + s2.size();  }  }  public static void main(String[] args) {  myQueue q = new myQueue();  q.enqueue(1);  q.enqueue(2);  q.enqueue(3);  System.out.println("Front: " + q.front());   System.out.println("Size: " + q.size());   q.dequeue();   System.out.println("Front: " + q.front());   System.out.println("Size: " + q.size());     } } 

class myQueue: def __init__(self): self.s1 = [] self.s2 = [] # Enqueue an item to the queue def enqueue(self, x): self.s1.append(x) # Dequeue an item from the queue  def dequeue(self): if not self.s1 and not self.s2: # Queue underflow return if not self.s2: while self.s1: self.s2.append(self.s1.pop()) self.s2.pop() # Return the front element without removing it def front(self): if self.s2: return self.s2[-1] if self.s1: # Move all elements to s2 to access front while self.s1: self.s2.append(self.s1.pop()) return self.s2[-1] # Queue empty return -1 # Return the size of the queue def size(self): return len(self.s1) + len(self.s2) if __name__ == "__main__": q = myQueue() q.enqueue(1) q.enqueue(2) q.enqueue(3) print("Front:", q.front()) print("Size:", q.size()) q.dequeue() print("Front:", q.front()) print("Size:", q.size()) 

using System; using System.Collections.Generic; class GfG {  class myQueue {  private Stack<int> s1 = new Stack<int>();  private Stack<int> s2 = new Stack<int>();  // Enqueue an item to the queue   public void enqueue(int x) {  s1.Push(x);  }  // Dequeue an item from the queue   public void dequeue() {  if (s1.Count == 0 && s2.Count == 0) {  return;   }  if (s2.Count == 0) {  while (s1.Count > 0) {  s2.Push(s1.Pop());  }  }  s2.Pop();  }  // Return the front element without removing it  public int front() {  if (s2.Count > 0) return s2.Peek();  if (s1.Count > 0) {  while (s1.Count > 0) {  s2.Push(s1.Pop());  }  return s2.Peek();  }  return -1;   }  // Return the size of the queue  public int size() {  return s1.Count + s2.Count;  }  }  public static void Main(string[] args) {  myQueue q = new myQueue();  q.enqueue(1);  q.enqueue(2);  q.enqueue(3);  Console.WriteLine("Front: " + q.front());   Console.WriteLine("Size: " + q.size());   q.dequeue();   Console.WriteLine("Front: " + q.front());   Console.WriteLine("Size: " + q.size());   } } 

class myQueue {  constructor() {  this.s1 = [];  this.s2 = [];  }  // Enqueue an item to the queue  enqueue(x) {  this.s1.push(x);  }  // Dequeue an item from the queue   dequeue() {  if (this.s1.length === 0 && this.s2.length === 0) {    // Queue underflow  return;   }  if (this.s2.length === 0) {  while (this.s1.length > 0) {  this.s2.push(this.s1.pop());  }  }  this.s2.pop();  }  // Return the front element without removing it  front() {  if (this.s2.length > 0) return this.s2[this.s2.length - 1];  if (this.s1.length > 0) {  while (this.s1.length > 0) {  this.s2.push(this.s1.pop());  }  return this.s2[this.s2.length - 1];  }    // Queue empty  return -1;   }  // Return the size of the queue  size() {  return this.s1.length + this.s2.length;  } } //Driven Code  const q = new myQueue(); q.enqueue(1); q.enqueue(2); q.enqueue(3); console.log("Front:", q.front());  console.log("Size:", q.size());  q.dequeue();  console.log("Front:", q.front());  console.log("Size:", q.size());  

Front: 1 Size: 3 Front: 2 Size: 2 

Time Complexity:

• enqueue(x) : O(1) - Simply push onto s1.
• dequeue() : Amortized O(1), Worst-case O(n)
  => Worst-case: All elements from s1 are moved to s2 O(n).
  => Amortized: Each element is moved at most once from s1 to s2 O(1) per operation.
• front() : Amortized O(1), Worst-case O(n)
  => Similar to dequeue: may need to move elements from s1 to s2.
• size() : O(1) Just return the sum of lengths of s1 and s2.

Space Complexity: O(n)- s1 and s2 together hold at most n elements, where n is the number of elements in the queue.

[Approach 3] Queue Implementation Using One Stack and Recursion

A queue can be implemented using one stack and recursion. The recursion uses the call stack to temporarily hold elements while accessing the bottom element of the stack, which represents the front of the queue.

enqueue(x) :

• Push new elements on top of the stack.
• The stack top represents the rear of the queue.

dequeue() :

• Recursively reach the bottom element (which is the front of the queue).
• Remove it and return it.
• Push back all other elements in the same order.

Front() :

• Recursively reach the bottom element but do not remove it.
• Push back all elements.

Size():

• Returns the current size.

#include <iostream> #include <stack> using namespace std; class myQueue { private:  // single stack for queue elements  stack<int> s;  public:  // Enqueue an item to the queue  void enqueue(int x) {  s.push(x);  }  // Dequeue an item from the queue   void dequeue() {  if (s.empty()) {  cout << "Queue Underflow\n";  return;  }  int x = s.top();  s.pop();  // If this is the last element (bottom), return it  if (s.empty())  return;  // Recursive call to pop remaining elements  dequeue();  // Push current element back  s.push(x);  return;  }  // Return the front element without removing it   int front() {  if (s.empty()) {  cout << "Queue is empty\n";  return -1;  }  int x = s.top();  s.pop();  if (s.empty()) {  s.push(x);   return x;  }  int item = front();   s.push(x);  return item;  }  // Return the current size of the queue   int size() {  return s.size();  } }; int main() {  myQueue q;  q.enqueue(1);  q.enqueue(2);  q.enqueue(3);  cout << "Front: " << q.front() << endl;   cout << "Size: " << q.size() << endl;   q.dequeue();   cout << "Front: " << q.front() << endl;   cout << "Size: " << q.size() << endl;   return 0; } 

import java.util.Stack; class GFG {  static class myQueue {  private Stack<Integer> s = new Stack<>();  // Enqueue an item to the queue   void enqueue(int x) {  s.push(x);  }  // Dequeue an item from the queue   void dequeue() {  if (s.isEmpty()) {  System.out.println("Queue Underflow");  return;  }  int x = s.pop();  // If stack becomes empty after popping,  // this was the bottom (front of queue)  if (s.isEmpty()) {  return;  }  // Recursive call to remove the bottom element  dequeue();  // Restore the current element  s.push(x);  }  // Return the front element without removing it   int front() {  if (s.isEmpty()) {  System.out.println("Queue is empty");  return -1;  }  int x = s.pop();  // If this is the bottom element  if (s.isEmpty()) {  s.push(x);  return x;  }  int item = front();  // Restore stack  s.push(x);  return item;  }  // Return the current size of the queue   int size() {  return s.size();  }  }  public static void main(String[] args) {  myQueue q = new myQueue();  q.enqueue(1);  q.enqueue(2);  q.enqueue(3);  System.out.println("Front: " + q.front());   System.out.println("Size: " + q.size());   q.dequeue();   System.out.println("Front: " + q.front());   System.out.println("Size: " + q.size());   } } 

class myQueue: def __init__(self): self.s = [] # Enqueue an item to the queue  def enqueue(self, x): self.s.append(x) # Dequeue an item from the queue def dequeue(self): if not self.s: print("Queue Underflow") return x = self.s.pop() if not self.s: return # Recursive call self.dequeue() # Push current element back self.s.append(x) return # Return the front element without removing it  def front(self): if not self.s: print("Queue is empty") return -1 x = self.s.pop() if not self.s: self.s.append(x) return x # recursive call item = self.front() self.s.append(x) return item # Return the current size of the queue  def size(self): return len(self.s) if __name__ == "__main__": q = myQueue() q.enqueue(1) q.enqueue(2) q.enqueue(3) print("Front:", q.front()) print("Size:", q.size()) q.dequeue() print("Front:", q.front()) print("Size:", q.size()) 

using System; using System.Collections.Generic; public class myQueue {  private Stack<int> s = new Stack<int>();  // Enqueue an item to the queue   public void enqueue(int x) {  s.Push(x);  }  // Dequeue an item from the queue   public void dequeue() {  if (s.Count == 0) {  Console.WriteLine("Queue Underflow");  return;  }  int x = s.Pop();    if (s.Count == 0)  return;  // Recursive call  dequeue();  // Push current element back  s.Push(x);  return;  }  // Return the front element without removing it   public int front() {  if (s.Count == 0) {  Console.WriteLine("Queue is empty");  return -1;  }  int x = s.Pop();  if (s.Count == 0) {  s.Push(x);  return x;  }  // recursive call  int item = front();  s.Push(x);  return item;  }  // Return the current size of the queue   public int size() {  return s.Count;  } } class GFG {  static void Main(string[] args) {  myQueue q = new myQueue();  q.enqueue(1);  q.enqueue(2);  q.enqueue(3);  Console.WriteLine("Front: " + q.front());   Console.WriteLine("Size: " + q.size());   q.dequeue();   Console.WriteLine("Front: " + q.front());   Console.WriteLine("Size: " + q.size());   } } 

class myQueue {  constructor() {  this.s = [];  }  // Enqueue an item to the queue   enqueue(x) {  this.s.push(x);  }  // Dequeue an item from the queue   dequeue() {  if (this.s.length === 0) {  console.log("Queue Underflow");  return;  }  let x = this.s.pop();  if (this.s.length === 0) {  return;  }  // Recursive call  this.dequeue();  // Push current element back  this.s.push(x);  return;  }  // Return the front element without removing it  front() {  if (this.s.length === 0) {  console.log("Queue is empty");  return -1;  }  let x = this.s.pop();  if (this.s.length === 0) {  this.s.push(x);  return x;  }  // recursive call  let item = this.front();  this.s.push(x);  return item;  }  // Return the current size of the queue   size() {  return this.s.length;  } } // Driven Code const q = new myQueue(); q.enqueue(1); q.enqueue(2); q.enqueue(3); console.log("Front:", q.front());  console.log("Size:", q.size());  q.dequeue();  console.log("Front:", q.front());  console.log("Size:", q.size());  

Front: 1 Size: 3 Front: 2 Size: 2 

Time Complexity

• enqueue(x): O(1) - Just a single s.push(x).
• dequeue(): O(n) - In the worst case, it pops all n elements recursively until it reaches the bottom, then pushes them back while unwinding recursion.
• front(): O(n) - Similar to dequeue(), it traverses all elements recursively to reach the bottom and then restores them.
• size(): O(1) - Direct call to s.size().

Auxiliary Space: O(n) due to the recursion call stack holding up to n elements temporarily.