How to implement a queue using stacks in C++

The task at hand is to implement a queue using a stack data structure, with the push (adding an element) and pop (removing an element) operations as the low-level data structure.

A queue is a FIFO (First In First Out), while a stack is a LIFO (Last In First Out) data structure.

A stack pushes a new element to the top of the stack and also pops the element at the top. A queue, however, dequeues (removes) an element from the top of the queue, but it enqueues (inserts) an element at the bottom.

Implementation

There are two methods used to implement a queue using the stack data structure. One method uses two stacks while the other uses one.

Using two stacks

This method ensures that the oldest inserted element is always at the top of stack1 so that the deQueue operation just pops from stack1. To put the element at the top of stack1, stack2 is used.

enqueue(x):

While stack1 is not empty, push everything from stack1 to stack2.
Push x to stack1.
Push everything back to stack1.

dequeue(x):

If stack1 is empty, display an error message.
Pop an item from stack1 and return it.

Code

The code snippet below puts the above algorithm into code:

#include <bits/stdc++.h> 
using namespace std; 
struct Queue { 
	stack<int> stack1, stack2; 
	void enqueue(int x) 
	{ 
		// Move all elements from s1 to s2 
		while (!stack1.empty()) { 
			stack2.push(stack1.top()); 
			stack1.pop(); 
		} 
		// Push item into s1 
		stack1.push(x); 
		// Push everything back to s1 
		while (!stack2.empty()) { 
			stack1.push(stack2.top()); 
			stack2.pop(); 
		} 
	} 
	// Dequeue an item from the queue 
	int dequeue() 
	{ 
		// if first stack is empty 
		if (stack1.empty()) { 
			cout << "queue is Empty"; 
			exit(0); 
		} 
		// Return the top of stack1 
		int x = stack1.top(); 
		stack1.pop(); 
		return x; 
	} 
}; 
int main() 
{ 
	Queue q; 
	q.enqueue(3); 
	q.enqueue(4); 
	q.enqueue(5); 
	cout << q.dequeue() << endl; 
	cout << q.dequeue() << endl; 
	cout << q.dequeue() << endl; 
	return 0; 
}

Using one stack

A queue can also be implemented using only one user stack; this method uses recursion.

enqueue(x):

Push x to stack_.

dequeue(x):

If stack_ is empty, then display an error message.
If stack_ has only one element, then return it.
Recursively pop everything from the stack_, store the popped item in a variable ret, push the ret back to stack_, and return ret.

Step 3 of dequeue() makes sure that the last popped item is always returned. Recursion stops when there is only one item in thestack_, so the last element of stack_ in dequeue() is returned, while all other items are pushed back in stack_.

Code

The code snippet below puts the above algorithm into code:

#include <bits/stdc++.h> 
using namespace std; 
struct Queue { 
	stack<int> stack_; 
	// Enqueue an item to the queue 
	void enqueue(int x) 
	{ 
		stack_.push(x); 
	} 
	// Dequeue an item from the queue 
	int dequeue() 
	{ 
		if (stack_.empty()) { 
			cout << "Queue is empty" << endl;; 
			exit(0); 
		} 
		// pop an item from the stack 
		int x = stack_.top(); 
		stack_.pop(); 
		// if stack becomes empty, return 
		// the popped item 
		if (stack_.empty()) 
			return x; 
		// recursive call 
		int ret = dequeue(); 
		// push popped item back to the stack 
		stack_.push(x); 
		// return the result of deQueue() call 
		return ret; 
	} 
}; 
int main() 
{ 
	Queue q; 
	q.enqueue(3); 
	q.enqueue(4); 
	q.enqueue(5); 
	cout << q.dequeue() << endl; 
	cout << q.dequeue() << endl; 
	cout << q.dequeue() << endl; 
	return 0; 
}

Free Resources