Implement Queue using Stacks Editorial

Practice Problem Link: Implement Queue using Stacks

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

Problem Statement

Implement a queue using one or more stacks.

The Queue class should support the following methods:

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

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

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

Approach

The push(), isEmpty(), size() functions stay the same as a normal stack. We will use two stacks for the front() operation. If the output stack is not empty, we return its top. Else we empty the input stack into the output stack and return its top. For the back function also use two stacks. We will empty one stack into another then return its top. For the pop() function, empty the input stack into the output stack and pop from it. Accordingly, adjust the back stacks. Refer to the implementation for more details.

Analysis

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

Implementation

C++

/* Use this Stack class
class Stack {
	Stack (int capacity)
	int size()
	boolean isEmpty()
	int top()
	void push(int element)
	void pop()
};
*/

// Implement the Queue class
class Queue {
public:
	Stack *stack1;
	Stack *stack2;
	int capacity = 0;
	Queue (int capacity) {
		this->capacity = capacity;
		stack1 = new Stack(capacity);
		stack2 = new Stack(capacity);
	}

	bool isEmpty() {
		return stack1->isEmpty();
	}
	
	int size() {
		return stack1->size();
	}
	
	int front() {
		if(isEmpty()) {
			return -1;
		}
		while(!isEmpty()) {
			stack2->push(stack1->top());
			stack1->pop();
		}
		int x = stack2->top();
		while(!stack2->isEmpty()) {
			stack1->push(stack2->top());
			stack2->pop();
		}
		return x;
	}
	int back() {
		if(isEmpty()) {
			return -1;
		}
		return stack1->top();
	}
	void push(int element) {
		if(stack1->size() == capacity) {
			return;
		} 
		stack1->push(element);
	}
	void pop() {
		if(isEmpty()) {
			return;
		}
		while(!isEmpty()) {
			stack2->push(stack1->top());
			stack1->pop();
		}
		stack2->pop();
		while(!stack2->isEmpty()) {
			stack1->push(stack2->top());
			stack2->pop();
		}
	}
};

Java

/* Use this Stack class
class Stack {
	Stack (int capacity)
	int size()
	boolean isEmpty()
	int top()
	void push(int element)
	void pop()
}
*/

// Implement the Queue class
class Queue {
	Stack stack1 = new Stack();
	Stack stack2 = new Stack();
	int capacity = 0;
	Queue (int capacity) {
		this.capacity = capacity;
	}

	boolean isEmpty() {
		return stack1.isEmpty();
	}
	
	int size() {
		return stack1.size();
	}
	
	int front() {
		if(isEmpty()) {
			return -1;
		}
		while(!isEmpty()) {
			stack2.push(stack1.top());
			stack1.pop();
		}
		int x = stack2.top();
		while(!stack2.isEmpty()) {
			stack1.push(stack2.top());
			stack2.pop();
		}
		return x;
	}
	int back() {
		if(isEmpty()) {
			return -1;
		}
		return stack1.top();
	}
	void push(int element) {
		if(stack1.size() == capacity) {
			return;
		} 
		stack1.push(element);
	}
	void pop() {
		if(isEmpty()) {
			return;
		}
		while(!isEmpty()) {
			stack2.push(stack1.top());
			stack1.pop();
		}
		stack2.pop();
		while(!stack2.isEmpty()) {
			stack1.push(stack2.top());
			stack2.pop();
		}
	}
}