代码随想录算法训练营第十天-栈和队列.md

LeetCode 232.用栈实现队列

class MyQueue {

    // use two stacks to simulate a queue
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    
    // stackIn's topside is the end of the queue
    public void push(int x) {
        stackIn.push(x);
    }
    
    // stackOut's topside is the head of the queue
    public int pop() {

        // if there is no element in the stackOut
        // fetch them from the stackIn 
        if (stackOut.empty()) {
            while (!stackIn.empty()) {
                stackOut.push(stackIn.pop());
            }
        } 
        return stackOut.pop();
    }
    
    // the easiest way to get the head element is pop it 
    // then push it back to the head of the queue
    public int peek() {
        int ans = this.pop();
        stackOut.push(ans);
        return ans;
    }
    
    public boolean empty() {
        return stackIn.empty() && stackOut.empty();
    }
}

学习了如何使用栈这种数据结构去模仿队列，想法很巧妙。

LeetCode 225. 用队列实现栈

可以使用两个队列也可以使用一个队列，两个队列的话，一个用于存储，一个用于挪移，使用一个队列的话，需要弹出栈顶元素时，将前面的所有元素poll出然后加到最后一个元素后面即可。

class MyStack {

    Deque storage_queue = new LinkedList<Integer>();
    Deque subDeque = new LinkedList<Integer>();

    public MyStack() {
        
    }
    
    public void push(int x) {

        // let's cache the added element in our sub queue
        subDeque.offer(x);

        // then move all the currently stored element into our sub queue
        while ( !storage_queue.isEmpty() ) {
            subDeque.offer(storage_queue.pollFirst());
        }

        // now the sub queue has a correct sequence as a stack
        // let's swap the two references
        Deque temp = subDeque;
        subDeque = storage_queue;
        storage_queue = temp;
    }
    
    public int pop() {
        return (Integer)storage_queue.pollFirst();
    }
    
    public int top() {
        return (Integer)storage_queue.peekFirst();
    }
    
    public boolean empty() {
        return storage_queue.isEmpty();
    }
}