【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)