Implement Queue using Stack
InfoEdge India LtdPCPop ClubThe problem
Implement a First-In-First-Out (FIFO) queue using two stacks. The implemented queue should support the following operations: push, pop, peek, and isEmpty.
Implement the StackQueue class:
void push(int x): Adds element x to the end of the queue. int pop(): Removes and returns the front element of the queue. int peek(): Returns the front element of the queue without removing it. boolean isEmpty(): Returns true if the queue is empty, false otherwise.
Input: ["StackQueue", "push", "push", "pop", "peek", "isEmpty"] [[], [4], [8], [], [], []] Output:[null, null, null, 4, 8, false] Explanation: StackQueue queue = new StackQueue(); queue.push(4); queue.push(8); queue.pop(); // returns 4 queue.peek(); // returns 8 queue.isEmpty(); // returns false
Input: ["StackQueue", "isEmpty"] [[]] Output: [null, true] Explanation: StackQueue queue = new StackQueue(); queue.isEmpty(); // returns true
Input: ["StackQueue", "push", "pop", "isEmpty"] [[], [6], [], []]
- 1 <= numbers of calls made <= 100
- 1 <= x <= 100
cpp
class StackQueue {
public:
StackQueue() {
}
void push(int x) {
}
int pop() {
}
int peek() {
}
bool isEmpty() {
}
};java
class StackQueue {
public StackQueue() {
}
public void push(int x) {
}
public int pop() {
}
public int peek() {
}
public boolean isEmpty() {
}
}python
class StackQueue:
def __init__(self):
def push(self, x):
def pop(self):
def peek(self):
def isEmpty(self):javascript
class StackQueue {
push(x) {
}
pop() {
}
peek() {
}
isEmpty() {
}
}csharp
class StackQueue
{
public StackQueue()
{
}
public void Push(int x)
{
}
public int Pop()
{
}
public int Peek()
{
}
public bool IsEmpty()
{
}
}go
type StackQueue struct {
}
func NewStackQueue() *StackQueue{
}
func (s *StackQueue) push(x int) {
}
func (s *StackQueue) pop() int {
}
func (s *StackQueue) peek() int {
}
func (s *StackQueue) isEmpty() bool {
}Stuck? Show a way to structure it+
- 01Push new values onto an input stack.
- 02Before pop or peek, move input to output only if output is empty.
- 03Serve the front from the top of output.
- 04Check both stacks for emptiness.
Reference answer
Then expect these follow-ups
How would you implement a stack using queues?
Tests: dual data structure
Explain the amortized O(1) proof.
Tests: amortized analysis
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question