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
Hiring now
Software engineer roles are open right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY
Next question