[刷题记录Day10]Leetcode

番茄随想 / 2023-08-26 / 原文

No.1

题目

用栈实现队列

思路

模拟
一个入栈一个出栈

代码

class MyQueue {  
    private Stack<Integer> stackIn;  
    private Stack<Integer> stackOut;  
  
    public MyQueue() {  
        stackIn = new Stack<>();  
        stackOut = new Stack<>();  
    }  
  
    public void push(int x) {  
        stackIn.push(x);  
    }  
  
    public int pop() {  
        if (stackOut.empty()) {  
            while (!stackIn.empty())  
                stackOut.push(stackIn.pop());  
        }  
        // pop时要保证stackIn的元素全部转移完毕  
        return stackOut.pop();  
    }  
  
    public int peek() {  
        if (stackOut.empty()) {  
            while (!stackIn.empty())  
                stackOut.push(stackIn.pop());  
        }  
        // peek时要保证stackIn的元素全部转移完毕  
        return stackOut.peek();  
    }  
  
    public boolean empty() {  
        return stackIn.empty() && stackOut.empty();  
    }  
}

No.2

题目

用队列实现栈

思路

用两个队列que1和que2实现栈的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1

代码

class MyStack {  
    private Queue<Integer> queue1;  
    private Queue<Integer> queue2;  
  
    public MyStack() {  
        queue1 = new LinkedList<>();  
        queue2 = new LinkedList<>();  
    }  
  
    public void push(int x) {  
        queue1.add(x);  
        // 保证queue1仅包含最后一个元素  
        while (queue1.size() > 1)  
            queue2.add(queue1.poll());  
    }  
  
    public int pop() {  
        int res = queue1.poll();  
        // 保证queue2仅包含最后一个元素  
        while (queue2.size() > 1)  
            queue1.add(queue2.poll());  
        // 交换queue1和queue2  
        Queue<Integer> tempQ = queue1;  
        queue1 = queue2;  
        queue2 = tempQ;  
  
        return res;  
    }  
  
    public int top() {  
        return queue1.peek();  
    }  
  
    public boolean empty() {  
        return queue1.isEmpty() && queue2.isEmpty();  
    }  
}