Implement Stack using Queues - Practice Coding Problems

Implement Stack using Queues - Problem

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) - Pushes element x to the top of the stack
int pop() - Removes the element on the top of the stack and returns it
int top() - Returns the element on the top of the stack
boolean empty() - Returns true if the stack is empty, false otherwise

Notes:

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

Input & Output

Example 1 — Basic Stack Operations

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

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

💡 Note: Create stack, push 1, push 2, top returns 2 (last pushed), pop returns 2, stack not empty (contains 1)

Example 2 — Single Element

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

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

💡 Note: Create stack, push 5, pop returns 5, stack is now empty

Example 3 — Multiple Operations

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

› Output: [null, null, null, null, 3, 3, 2]

💡 Note: Push 1,2,3; top shows 3 (most recent); pop removes 3; top now shows 2

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Series of stack operations to perform

Process

Use two queues to maintain LIFO order

Output

Results of each operation in order

Key Takeaway

🎯 Key Insight: Use two queues to reverse the natural FIFO order and achieve LIFO stack behavior

Asked in

B Bloomberg 15 M Microsoft 12 a Amazon 10 🍎 Apple 8

The key insight is using two queues to simulate LIFO behavior by either maintaining reverse order (push-heavy) or transferring elements during access (pop-heavy). Best approach depends on usage pattern: push-heavy for frequent pop/top, pop-heavy for frequent push. Time: O(n) per operation, Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Two Queue Approach (Pop Heavy)	O(n)	O(n)	Use two queues and make pop/top operations expensive while keeping push simple
Two Queue Approach (Push Heavy)	O(n)	O(n)	Use two queues and make push operation expensive by maintaining stack order

Two Queue Approach (Pop Heavy) — Algorithm Steps

Push: Simply add element to back of main queue
Pop: Move all but last element to helper queue, pop last element, swap queues
Top: Similar to pop but don't remove the element

Visualization

Tap to expand

Step-by-Step Walkthrough

Push Phase

Elements added in natural order to main queue

Pop Preparation

Transfer all but last element to helper queue

Pop Result

Get last element and swap queues

Code -

solution.c — C

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

typedef struct {
    int* q1;
    int* q2;
    int q1_size;
    int q2_size;
    int capacity;
} MyStack;

MyStack* myStackCreate() {
    MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
    stack->capacity = 1000;
    stack->q1 = (int*)malloc(stack->capacity * sizeof(int));
    stack->q2 = (int*)malloc(stack->capacity * sizeof(int));
    stack->q1_size = 0;
    stack->q2_size = 0;
    return stack;
}

void myStackPush(MyStack* obj, int x) {
    obj->q1[obj->q1_size++] = x;
}

int myStackPop(MyStack* obj) {
    while (obj->q1_size > 1) {
        obj->q2[obj->q2_size++] = obj->q1[0];
        for (int i = 0; i < obj->q1_size - 1; i++) {
            obj->q1[i] = obj->q1[i + 1];
        }
        obj->q1_size--;
    }
    int val = obj->q1[0];
    obj->q1_size--;
    int* temp = obj->q1;
    obj->q1 = obj->q2;
    obj->q2 = temp;
    int temp_size = obj->q1_size;
    obj->q1_size = obj->q2_size;
    obj->q2_size = temp_size;
    return val;
}

int myStackTop(MyStack* obj) {
    while (obj->q1_size > 1) {
        obj->q2[obj->q2_size++] = obj->q1[0];
        for (int i = 0; i < obj->q1_size - 1; i++) {
            obj->q1[i] = obj->q1[i + 1];
        }
        obj->q1_size--;
    }
    int val = obj->q1[0];
    obj->q2[obj->q2_size++] = obj->q1[0];
    obj->q1_size--;
    int* temp = obj->q1;
    obj->q1 = obj->q2;
    obj->q2 = temp;
    int temp_size = obj->q1_size;
    obj->q1_size = obj->q2_size;
    obj->q2_size = temp_size;
    return val;
}

bool myStackEmpty(MyStack* obj) {
    return obj->q1_size == 0;
}

void myStackFree(MyStack* obj) {
    free(obj->q1);
    free(obj->q2);
    free(obj);
}

char* solution(char** operations, int op_size, int* values, int val_size) {
    MyStack* stack = myStackCreate();
    char* result = (char*)malloc(10000);
    strcpy(result, "[");
    
    for (int i = 0; i < op_size; i++) {
        if (i > 0) strcat(result, ",");
        
        if (strcmp(operations[i], "MyStack") == 0) {
            strcat(result, "null");
        } else if (strcmp(operations[i], "push") == 0) {
            myStackPush(stack, values[i]);
            strcat(result, "null");
        } else if (strcmp(operations[i], "pop") == 0) {
            char temp[20];
            sprintf(temp, "%d", myStackPop(stack));
            strcat(result, temp);
        } else if (strcmp(operations[i], "top") == 0) {
            char temp[20];
            sprintf(temp, "%d", myStackTop(stack));
            strcat(result, temp);
        } else if (strcmp(operations[i], "empty") == 0) {
            strcat(result, myStackEmpty(stack) ? "true" : "false");
        }
    }
    
    strcat(result, "]");
    myStackFree(stack);
    return result;
}

int main() {
    printf("[null,null,null,2,1,false]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Pop and top require moving n-1 elements between queues, push is O(1)

✓ Linear Growth

Space Complexity

O(n)

Two queues store n elements total

⚡ Linearithmic Space

89.5K Views

Medium Frequency

~15 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

Two Queue Approach (Pop Heavy) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler