【225】【232】栈和队列相互实现

题目【225】（难度：简单）：用队列实现栈

解题思想：队列的特点是先进先出，用两个队列相互数据转移，实现栈的先进后出。以pop为例，队列1先进栈，如果要实现出栈，则将队列1中的元素除了最后一个元素转移到队列2中，再将队列1中元素移除，实现出栈，下一步继续入栈，再从队列2转移到队列1.

代码实现：

Queue<Integer> queue1;
    Queue<Integer> queue2;

    public Solution225() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue1.offer(x);
    }

    public int pop() {
        if (queue1.isEmpty()) throw new RuntimeException("队列为空");
        int len = queue1.size();
        if (len == 1) return queue1.poll();
        while (!queue1.isEmpty() && (len--) > 1) {
            queue2.offer(queue1.poll());
        }
        int res = queue1.poll();
        swap();
        return res;
    }

    public int top() {
        if (queue1.isEmpty()) throw new RuntimeException("队列为空");
        int len = queue1.size();
        if (len == 1) return queue1.peek();
        while (!queue1.isEmpty() && (len--) > 1) {
            queue2.offer(queue1.poll());
        }
        int res = queue1.peek();
        queue2.offer(queue1.poll());
        swap();
        return res;
    }

    public boolean empty() {
        if (queue1.isEmpty() && queue2.isEmpty()) {
            return true;
        }
        return false;
    }

    public void swap() {
        Queue<Integer> tmp;
        tmp = queue1;
        queue1 = queue2;
        queue2 = tmp;
    }
           

测试用例：

算法分析：

时间复杂度：O（n），空间复杂度O(2*n) （两个队列）

题目【232】（难度：简单）：用栈实现队列

解题思想：队列的特点是先进先出，使用两个栈，使得栈1最后入栈的元素转移到栈2后先出栈，前提是进行出队操作时，要保证栈1为空（即需要全部转移到栈2中）。

代码实现：

Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    public Solution232() {
    }

    public void push(int x) {
        stack1.add(x);
    }

    public int pop() {
        int res;
        if (!stack2.empty()) {
            res = stack2.pop();
        } else {
            while (!stack1.empty()) {
                stack2.add(stack1.pop());
            }
            res = stack2.pop();
        }
        return res;
    }

    public int peek() {
        int res;
        if (!stack2.empty()) {
            res = stack2.peek();
        } else {
            while (!stack1.empty()) {
                stack2.add(stack1.pop());
            }
            res = stack2.peek();
        }

        return res;
    }

    public boolean empty() {
        if (stack1.empty() && stack2.empty()) {
            return true;
        }
        return false;
    }
           

测试用例：

算法分析：

时间复杂度O(n)，空间复杂度O(2*n)