In this Leetcode Implement Stack using Queues problem solution 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:

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

Leetcode Implement Stack using Queues problem solution


Problem solution in Python.

class Stack:
    def __init__(self):
        self.q1=[]
        self.q2=[]

    def push(self, x):
        self.q1.append(x)

    def pop(self):
        while self.q1:
            tmp=self.q1.pop(0)
            if self.q1:
                self.q2.append(tmp)
        self.q1=self.q2
        self.q2=[]

    def top(self):
        while self.q1:
            tmp=self.q1.pop(0)
            self.q2.append(tmp)
        self.q1=self.q2
        self.q2=[]
        return tmp

    def empty(self):
        if self.q1:
            return False
        return True



Problem solution in Java.

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

    public void push(int x) {
        q.add(x);
        for (int i = 0; i < q.size() - 1; i++) {
            q.add(q.remove());    
        }
    }

    public void pop() {
        q.remove();
    }

    public int top() {
        return q.peek();
    }

    public boolean empty() {
        return q.isEmpty();
    }
}


Problem solution in C++.

class MyStack {
public:
    queue<int> q1;

    MyStack() {
        
    }

    void push(int x) {
        queue<int> q2;
        int n = q1.size();
        for (int i=0; i<n; ++i) {
            q2.push(q1.front());
            q1.pop();
        }
        q1.push(x);
        for (int i=0; i<n; ++i) {
            q1.push(q2.front());
            q2.pop();
        }
    }

    int pop() {
        auto temp = q1.front();
        q1.pop();
        return temp;
    }

    int top() {
        return q1.front();
    }

    bool empty() {
        return q1.size()==0;
    }
};


Problem solution in C.

typedef struct {
    int *array;
    int top;
} MyStack;


MyStack* myStackCreate() {
    MyStack* s = (MyStack*)malloc(sizeof(MyStack));
    s->array = (int*)malloc(100000*sizeof(int));
    s->top = -1;
    return s;
}

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

int myStackPop(MyStack* obj) {
  return obj->array[obj->top--];
}

int myStackTop(MyStack* obj) {
  return obj->array[obj->top];
}

bool myStackEmpty(MyStack* obj) {
  return (obj->top == -1) ? true : false;
}

void myStackFree(MyStack* obj) {
    if(obj)
        free(obj->array);
    free(obj);
}