Implement Stack using Queues Editorial

Practice Problem Link: Implement Stack using Queues

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Implement a stack using one or more queues.

The Stack class should support the following methods:

• int size()
• boolean isEmpty()
• int top()
• void push(int element)
• void pop()

You can assume that you've access to a Queue class that provides the following methods:

• int size()
• boolean isEmpty()
• int front()
• int back()
• void push(int element)
• void pop()

Approach

All the operations of the stack can be implemented with a single queue. All the functions except the push() function can be implemented using the corresponding functions of the Queue class. For the push() function, whenever we push an element in the queue, take all the elements in the queue, except the current one, and push them into the queue again. Refer to the implementation for more details.

Analysis

• Time Complexity: O(n) for push(), O(1) for the rest.
• Space Complexity: O(n) for push(), O(1) for the rest.

Implementation

C++

/* Use this Queue class
class Queue {
	Queue (int capacity)
	int size()
	boolean isEmpty()
	int front()
	int back()
	void push(int element)
	void pop()
};
*/

// Implement the Stack class
class Stack {
public:
	int capacity;
	Queue *queue;
	Stack (int capacity) {
		this->capacity = capacity;
		queue = new Queue(capacity);
	}
	bool isEmpty() {
		return queue->isEmpty();
	}
	
	int size() {
		return queue->size();
	}
	
	int top() {
		return queue->front();
	}
	
	void push(int element) {
		queue->push(element);
		for(int i = 1; i < queue->size(); i++) {
			queue->push(queue->front());
			queue->pop();
		}
	}
	
	void pop() {
		queue->pop();
	}
};

Java

/* Use this Queue class
class Queue {
	Queue (int capacity)
	int size()
	boolean isEmpty()
	int front()
	int back()
	void push(int element)
	void pop()
};
*/

// Implement the Stack class
class Stack {
	Queue queue;
	int capacity;
	public Stack (int capacity) {
		this.capacity = capacity;
		queue = new Queue(capacity);
	}

	public boolean isEmpty() {
		return queue.isEmpty();
	}
	
	public int size() {
		return queue.size();
	}
	
	public int top() {
		return queue.front();
	}
	
	public void push(int element) {
		queue.push(element);
		for(int i = 1; i < queue.size(); i++) {
			queue.push(queue.front());
			queue.pop();
		}
	}
	
	public void pop() {
		queue.pop();
	}
}