Close Menu
    What's Hot
    Explore the coolest frontend learning platform !
    Visit NamasteDev
    Wednesday, June 24

    Implement Stack Using One Queue

    Updated: Algorithms and Data Structures No Comments4 Mins Readdevangini123By

    Problem Statement:

    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, which means that only push to back, peek/pop from front, size and is empty operations are valid.
    • Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.

    Examples

    Example 1:

    Input:[“MyStack”, “push”, “push”, “top”, “pop”, “empty”] [[], [1], [2], [], [], []]

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

    Explanation MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // return 2 myStack.pop(); // return 2 myStack.empty(); // return False

    Constraints:

    • 1 <= x <= 9
    • At most 100 calls will be made to push, pop, top, and empty.
    • All the calls to pop and topare valid.

    Follow-up: Can you implement the stack using only one queue?

    Approach: Implement Stack Using One Queue

    • We simulate LIFO (stack) using only FIFO (queue) operations.
    • We maintain a single queue (q).
    • Remove the last pushed element (i.e., rear of q1).
      • Insert it at the back (q.push(x)).
      • Rotate the queue to bring the new element to the front by dequeuing and enqueuing all previous elements.

    Visualisation:

    stack

    Time Complexity:

  • push → O(n)

    pop → O(1)

    top → O(1)

    empty → O(1)

    • Space Complexity:

  • Space Complexity = O(n)

  • Where n is the total number of elements in the stack.

    • Dry Run

    Input:

    Operations:
push(1)
push(2)
push(3)
top()
pop()
top()
empty()

    State Transitions:

    After push(1):
  q = [1]

After push(2):
  q = [1, 2]

After push(3):
  q = [1, 2, 3]

top():
  Loop to rotate first n-1 = 2 elements:
    q.push(q.shift()) → q = [2, 3, 1]
    q.push(q.shift()) → q = [3, 1, 2]
  Peek front = 3
  Push front back → q = [1, 2, 3]
  → Returns: 3

pop():
  Loop to rotate first n-1 = 2 elements:
    q.push(q.shift()) → q = [2, 3, 1]
    q.push(q.shift()) → q = [3, 1, 2]
  Remove front = 3 → q = [1, 2]
  → Returns: 3

top():
  Loop to rotate first n-1 = 1 element:
    q.push(q.shift()) → q = [2, 1]
  Peek front = 2
  Push front back → q = [1, 2]
  → Returns: 2

empty():
  q = [1, 2] → Not empty
  → Returns: false

    Final State: q = [1, 2], Stack (top to bottom): [2, 1]

    
var MyStack = function() {
    this.q = []; 
};

MyStack.prototype.push = function(x) {
    this.q.push(x);
};

MyStack.prototype.pop = function() {
    let n = this.q.length;
    for (let i = 0; i < n - 1; i++) {
        this.q.push(this.q.shift());
    }
    return this.q.shift();
};

MyStack.prototype.top = function() {
    let n = this.q.length;
    for (let i = 0; i < n - 1; i++) {
        this.q.push(this.q.shift());
    }
    let front = this.q.shift();
    this.q.push(front);
    return front;
};

MyStack.prototype.empty = function() {
    return this.q.length === 0;
};

    
from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)

    def pop(self) -> int:
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
        return self.q.popleft()

    def top(self) -> int:
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
        front = self.q.popleft()
        self.q.append(front)
        return front

    def empty(self) -> bool:
        return len(self.q) == 0

    
    
import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    Queue q = new LinkedList<>();

    public void push(int x) {
        q.offer(x);
    }

    public int pop() {
        int n = q.size();
        for (int i = 0; i < n - 1; i++) {
            q.offer(q.poll());
        }
        return q.poll();
    }

    public int top() {
        int n = q.size();
        for (int i = 0; i < n - 1; i++) {
            q.offer(q.poll());
        }
        int front = q.poll();
        q.offer(front);
        return front;
    }

    public boolean empty() {
        return q.isEmpty();
    }
}
 
    
#include <queue>
class MyStack {
    std::queue q;
public:
    void push(int x) {
        q.push(x);
    }

    int pop() {
        int n = q.size();
        for (int i = 0; i < n - 1; ++i) {
            q.push(q.front());
            q.pop();
        }
        int top = q.front();
        q.pop();
        return top;
    }

    int top() {
        int n = q.size();
        for (int i = 0; i < n - 1; ++i) {
            q.push(q.front());
            q.pop();
        }
        int top = q.front();
        q.pop();
        q.push(top);
        return top;
    }

    bool empty() {
        return q.empty();
    }
};
    
    
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAX 1000

typedef struct {
    int data[MAX];
    int front;
    int rear;
    int size;
} Queue;

void initQueue(Queue* q) {
    q->front = 0;
    q->rear = 0;
    q->size = 0;
}

void enqueue(Queue* q, int val) {
    if (q->size == MAX) {
        printf("Queue overflow\n");
        return;
    }
    q->data[q->rear] = val;
    q->rear = (q->rear + 1) % MAX;
    q->size++;
}

int dequeue(Queue* q) {
    if (q->size == 0) {
        printf("Queue underflow\n");
        return -1;
    }
    int val = q->data[q->front];
    q->front = (q->front + 1) % MAX;
    q->size--;
    return val;
}

int queueSize(Queue* q) {
    return q->size;
}

bool isQueueEmpty(Queue* q) {
    return q->size == 0;
}

// MyStack implementation using one queue
typedef struct {
    Queue q;
} MyStack;

void myStackInit(MyStack* obj) {
    initQueue(&obj->q);
}

void myStackPush(MyStack* obj, int x) {
    enqueue(&obj->q, x);
}

int myStackPop(MyStack* obj) {
    int n = queueSize(&obj->q);
    for (int i = 0; i < n - 1; i++) {
        enqueue(&obj->q, dequeue(&obj->q));
    }
    return dequeue(&obj->q);
}

int myStackTop(MyStack* obj) {
    int n = queueSize(&obj->q);
    for (int i = 0; i < n - 1; i++) {
        enqueue(&obj->q, dequeue(&obj->q));
    }
    int top = dequeue(&obj->q);
    enqueue(&obj->q, top);
    return top;
}

bool myStackEmpty(MyStack* obj) {
    return isQueueEmpty(&obj->q);
}
// Example usage
int main() {
    MyStack s;
    myStackInit(&s);

    myStackPush(&s, 10);
    myStackPush(&s, 20);
    myStackPush(&s, 30);

    printf("Top: %d\n", myStackTop(&s)); // 30
    printf("Pop: %d\n", myStackPop(&s)); // 30
    printf("Top after pop: %d\n", myStackTop(&s)); // 20
    printf("Is empty? %s\n", myStackEmpty(&s) ? "Yes" : "No"); // No

    return 0;
}
    
    
using System.Collections.Generic;

public class MyStack {
    private Queue q = new Queue();

    public void Push(int x) {
        q.Enqueue(x);
    }

    public int Pop() {
        int n = q.Count;
        for (int i = 0; i < n - 1; i++) {
            q.Enqueue(q.Dequeue());
        }
        return q.Dequeue();
    }

    public int Top() {
        int n = q.Count;
        for (int i = 0; i < n - 1; i++) {
            q.Enqueue(q.Dequeue());
        }
        int front = q.Dequeue();
        q.Enqueue(front);
        return front;
    }

    public bool Empty() {
        return q.Count == 0;
    }
}

    Keep Reading

    Add A Comment
    Leave A Reply

    Demo

    Courses

    Community

    Contact Us