Leetcode-225-Implement Stack using Queues

Implement Stack using Queues

leetcode: https://leetcode.com/problems/implement-stack-using-queues/

Description:

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Idea:

**solution **

Step1: create the queue, when do the push operation, reverse the order of the elements in the queue so that it is in the same order as the stack.

Step2: do other operations directly, because the order has changed when adding elements.

Code:

class MyStack {
    Queue<Integer> queue; 
    public MyStack() {
        queue = new LinkedList<>();
    }
    
    public void push(int x) {
        int size= queue.size()-1;
        queue.offer(x);
        //make the last in element, first out
        //add all elements except the last add node, and push them to the back of the queue and remove them in the original poisition
        while(size-->=0){
            queue.offer(queue.poll());
        }
    }
    //because the order of all elements have been changed when add, so do following operation directly.
    public int pop() {
        return queue.poll();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
         return queue.isEmpty();
    }
}

/**
 * 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();
 */