Implement Queue using Stacks - Practice Coding Problems

Implement Queue using Stacks - Problem

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue.

Implement the MyQueue class:

void push(int x) Pushes element x to the back of the queue
int pop() Removes the element from the front of the queue and returns it
int peek() Returns the element at the front of the queue
boolean empty() Returns true if the queue is empty, false otherwise

Notes:

You must use only standard operations of a stack (push to top, peek/pop from top, size, and is empty)
Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque as long as you use only a stack's standard operations

Input & Output

Example 1 — Basic Queue Operations

$ Input: operations = ["MyQueue", "push", "push", "peek", "pop", "empty"], values = [null, 1, 2, null, null, null]

› Output: [null, null, null, 1, 1, false]

💡 Note: Create queue, push 1 and 2, peek returns 1 (front), pop returns 1, queue not empty (still has 2)

Example 2 — Multiple Operations

$ Input: operations = ["MyQueue", "push", "push", "push", "pop", "pop", "empty"], values = [null, 1, 2, 3, null, null, null]

› Output: [null, null, null, null, 1, 2, false]

💡 Note: Push 1,2,3 then pop twice: first pop gets 1, second pop gets 2, queue still has 3 so not empty

Example 3 — Empty Queue Check

$ Input: operations = ["MyQueue", "push", "pop", "empty"], values = [null, 5, null, null]

› Output: [null, null, 5, true]

💡 Note: Push 5, pop 5, now queue is empty so empty() returns true

Constraints

1 ≤ x ≤ 9
At most 100 calls will be made to push, pop, peek, and empty
All the calls to pop and peek are valid

Visualization

Tap to expand

Understanding the Visualization

Input

Operations and values for queue implementation

Two Stack System

Input stack for push, output stack for pop/peek

FIFO Result

Queue operations return correct FIFO order

Key Takeaway

🎯 Key Insight: Use input stack for push, output stack for pop/peek with lazy transfer

Asked in

a Amazon 45 M Microsoft 32 🍎 Apple 28 G Google 25

The key insight is to use two stacks with lazy transfer: one for input, one for output. Only transfer elements when the output stack is empty. Best approach is the optimized lazy transfer with amortized O(1) time per operation and O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Transfer Every Time	O(n)	O(n)	Transfer all elements between stacks for every pop/peek operation
Optimized - Lazy Transfer	O(1)	O(n)	Transfer elements only when output stack is empty, amortized O(1)

Brute Force - Transfer Every Time — Algorithm Steps

Push: Add to input stack
Pop/Peek: Transfer all to output stack, operate, transfer back

Visualization

Tap to expand

Step-by-Step Walkthrough

Push Elements

Add elements to input stack

Transfer All

Move all elements to output stack for peek/pop

Transfer Back

Move everything back to input stack

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_SIZE 1000

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

typedef struct {
    Stack inputStack;
    Stack outputStack;
} MyQueue;

void stackInit(Stack* s) {
    s->top = -1;
}

void stackPush(Stack* s, int x) {
    s->data[++s->top] = x;
}

int stackPop(Stack* s) {
    return s->data[s->top--];
}

int stackTop(Stack* s) {
    return s->data[s->top];
}

bool stackEmpty(Stack* s) {
    return s->top == -1;
}

MyQueue* myQueueCreate() {
    MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
    stackInit(&queue->inputStack);
    stackInit(&queue->outputStack);
    return queue;
}

void myQueuePush(MyQueue* obj, int x) {
    stackPush(&obj->inputStack, x);
}

int myQueuePop(MyQueue* obj) {
    // Transfer all to output
    while (!stackEmpty(&obj->inputStack)) {
        stackPush(&obj->outputStack, stackPop(&obj->inputStack));
    }
    
    int result = stackPop(&obj->outputStack);
    
    // Transfer back
    while (!stackEmpty(&obj->outputStack)) {
        stackPush(&obj->inputStack, stackPop(&obj->outputStack));
    }
    
    return result;
}

int myQueuePeek(MyQueue* obj) {
    // Transfer all to output
    while (!stackEmpty(&obj->inputStack)) {
        stackPush(&obj->outputStack, stackPop(&obj->inputStack));
    }
    
    int result = stackTop(&obj->outputStack);
    
    // Transfer back
    while (!stackEmpty(&obj->outputStack)) {
        stackPush(&obj->inputStack, stackPop(&obj->outputStack));
    }
    
    return result;
}

bool myQueueEmpty(MyQueue* obj) {
    return stackEmpty(&obj->inputStack);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse operations (simplified for demo)
    char operations[100][20];
    int values[100];
    int opCount = 0;
    
    // Simplified parsing - in real implementation, parse JSON properly
    strcpy(operations[0], "MyQueue"); values[0] = 0; opCount++;
    strcpy(operations[1], "push"); values[1] = 1; opCount++;
    strcpy(operations[2], "push"); values[2] = 2; opCount++;
    strcpy(operations[3], "peek"); values[3] = 0; opCount++;
    strcpy(operations[4], "pop"); values[4] = 0; opCount++;
    strcpy(operations[5], "empty"); values[5] = 0; opCount++;
    
    MyQueue* queue = myQueueCreate();
    printf("[");
    
    for (int i = 0; i < opCount; i++) {
        if (i > 0) printf(",");
        
        if (strcmp(operations[i], "MyQueue") == 0) {
            printf("null");
        } else if (strcmp(operations[i], "push") == 0) {
            myQueuePush(queue, values[i]);
            printf("null");
        } else if (strcmp(operations[i], "pop") == 0) {
            printf("%d", myQueuePop(queue));
        } else if (strcmp(operations[i], "peek") == 0) {
            printf("%d", myQueuePeek(queue));
        } else if (strcmp(operations[i], "empty") == 0) {
            printf(myQueueEmpty(queue) ? "true" : "false");
        }
    }
    
    printf("]\n");
    free(queue);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each pop/peek transfers all n elements twice

✓ Linear Growth

Space Complexity

O(n)

Two stacks store up to n elements total

⚡ Linearithmic Space

185.0K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Transfer Every Time — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler