Home / LeetCode / 225. Implement Stack using Queues | LeetCode Solutions |Master Problem Solving

225. Implement Stack using Queues | LeetCode Solutions |Master Problem Solving

Implement the following operations of a stack using queues.

  • push(x) — Push element x onto stack.
  • pop() — Removes the element on top of the stack.
  • top() — Get the top element.
  • empty() — Return whether the stack is empty.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

You must use only standard operations of a queue — which means only Push to back , peek/pop from front size, and is empty operations are valid.

Notes:

Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.

You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Solution

The Idea here is to use Two Queue Data Structures through making The Push or Pop operations is Expensive which means it takes more running time.So in a simple way we need to make the queue works for us like stack because in Stack we need LIFO (Last Input First Output) But Queue works as FIFO(First Input Last Output)

class MyStack {
    Queue<Integer> q = new LinkedList<Integer>();
    // Push element x onto stack.
    public void push(int x) {
        Queue<Integer> newq = new LinkedList<Integer>();
        newq.add(x);
        while (q.size() > 0) {
            newq.add(q.poll());
        }
        q = newq;
    }
 
    // Removes the element on top of the stack.
    public int pop() {
      return  q.poll();
    }
 
    // Get the top element.
    public int top() {
        return q.peek();
    }
 
    // Return whether the stack is empty.
    public boolean empty() {
        return q.size() == 0;
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

Leave a Reply

Your email address will not be published. Required fields are marked *