算法 1.4.3 用队列实现栈【leetcode 225】

题目描述

使用队列实现栈的下列操作：

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

数据结构

• 队列（链表）

算法思维

• 队列操作

解题要点

• 队列的 FIFO 特性
• 栈的 LIFO 特性

---

解题思路

一. Comprehend 理解题意

• 需要自实现一个栈
• 只能使用队列作为数据结构
• 只能使用队列操作实现栈的功能

二. Choose 选择数据结构与算法

解法一：双队列改变元素顺序

• 数据结构：队列（链表）
• 算法思维：队列操作

三. Code 编码实现基本解法

class MyStack {

    //1.声明两个用来实现栈的队列
    Queue<Integer> q1;
    Queue<Integer> q2;

    /** Initialize your data structure here. */
    public MyStack() {
        q1 = new LinkedList<>(); //用于存放栈中数据的队列
        q2 = new LinkedList<>(); //用于改变数据顺序的队列
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        //2.在入栈之前，先将q1中的元素暂存在q2中
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        //3.新元素入栈
        q1.offer(x);
        //4.将暂存在q2中的元素放回q1中
        while (!q2.isEmpty()) {
            q1.offer(q2.poll());
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        //5.出栈 == q1出队
        return q1.poll();
    }
    
    /** Get the top element. */
    public int top() {
        //6.查看栈顶 == 查看q1队首
        return q1.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        //7.空栈 == q1为空队列
        return q1.isEmpty();
    }

}

执行耗时：0 ms，击败了 100.00% 的Java用户
内存消耗：36.3 MB，击败了 52.92% 的Java用户
时间复杂度：O(n²) -- 每次插入数据都要遍历队列 O(n²)
空间复杂度：O(n) -- 队列的内存空间 O(n)

四. Consider 思考更优解

优化代码结构
改变算法思维
借鉴其他算法

思路：

方法：

解法二：XXX

• 数据结构：
• 算法思维：

五. Code 编码实现最优解

执行耗时：
内存消耗：
时间复杂度：O() --
空间复杂度：O() --

六. Change 变形与延伸

=== 待续 ===