数据结构设计 --- 栈实现队列、队列实现栈

2021-06-21 本文已影响0人 _code_x

队列实现栈（leetcode225）

题目描述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

思路：

定义两个队列，一个主队列，一个辅助队列，模拟栈后进先出。
当入栈操作时，先将该数据入队辅助队列，然后主队列内容导入辅助队列（while循环），最后将将主队列和辅助队列进行交换。
其实，了解了上述思路（将当前加入元素加到已经按照栈排好的元素最前边），我们只需要一个队列即可。

复杂度分析

时间复杂度：入栈操作 O(n)，其余操作都是 O(1)。

入栈操作需要将queue 1中的 n个元素出队，并入队 n+1 个元素到queue 2 ，共有 2n+1 次操作，每次出队和入队操作的时间复杂度都是 O(1)，因此入栈操作的时间复杂度是 O(n)。

出栈操作和获取栈顶元素对应将 queue 1的前端元素出队，时间复杂度是 O(1)。

判断栈是否为空操作只需要判断queue 1是否为空，时间复杂度是 O(1)。
空间复杂度：O(n)，其中 n 是栈内的元素。需要使用两个队列存储栈内的元素。

代码实现：

class MyStack {

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

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    public void push(int x) {
        queue2.offer(x);
        // 特别注意，while循环
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
        return queue1.peek();
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
}

使用一个队列实现（将当前加入的元素放在已经是栈顺序序列的最前边，实现后进先出原则而）

class MyStack {

    private Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }
    
    public void push(int x) {
        queue.offer(x);
        int cnt = queue.size();
        while (cnt-- > 1) {
            queue.offer(queue.poll());
        }
    }
    
    public int pop() {
        return queue.poll();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

栈实现队列（leetcode232）

问题描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

要求：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

示例：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

思路：

定义两个栈用于数据的输入和输出。
当进行pop和poll操作时，如果输出栈为空，那么将输入栈数据全部移到输出栈。所以，当移到输出栈中然后进行输出的时候（出队列），就满足先进先出的结构。

复杂度分析：

时间复杂度：push 和empty 为 O(1)，pop 和 peek 为均摊 O(1)。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为 O(1)。
空间复杂度：O(n)O(n)。其中 n是操作总数。对于有 n 次 push 操作的情况，队列中会有 n 个元素，故空间复杂度为 O(n)。

代码实现：

class MyQueue {

    private Deque<Integer> inStack;
    private Deque<Integer> outStack;

    public MyQueue() {
        inStack = new LinkedList<>();
        outStack = new LinkedList<>();
    }
    
    public void push(int x) {
        inStack.push(x);
    }
    
    // 获取栈中的元素时，需要检查输出栈是否为空
    public int pop() {
        if (outStack.isEmpty()) {
            inToOut();
        }
        return outStack.pop();
    }
    
    public int peek() {
        if (outStack.isEmpty()) {
            inToOut();
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
    
    // 将输入栈中的元素移到输出栈
    private void inToOut() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

对于均摊复杂度的说明：参考@宫水三叶

我们先用另外一个例子来理解「均摊复杂度」，大家都知道「哈希表」底层是通过数组实现的。

正常情况下，计算元素在哈希桶的位置，然后放入哈希桶，即插入操作复杂度为 O(1)，假定是通过简单的“拉链法”搭配「头插法」方式来解决哈希冲突。
但当某次元素插入后，「哈希表」达到扩容阈值，则需要对底层所使用的数组进行扩容，这个复杂度是 O(n)
显然「扩容」操作不会发生在每一次的元素插入中，因此扩容的 O(n) 都会伴随着 n 次的 O(1)，也就是 O(n) 的复杂度会被均摊到每一次插入当中，因此哈希表插入仍然是 O(1)的。

同理，我们不是发生在每一次的「输出操作」中，而是集中发生在一次「输出栈为空」的时候，因此 pop 和 peek 都是均摊复杂度为 O(1)的操作。

补充：Queue接口分析：add和offer区别，remove和poll方法到底啥区别

这些方法的主要区别在于，如果执行失败，是抛出异常还是返回值。

queue的增加元素方法add和offer的区别在于，add方法在队列满的情况下将选择抛异常的方法来表示队列已经满了，而offer方法通过返回false表示队列已经满了；在有限队列的情况，使用offer方法优于add方法；
remove方法和poll方法都是删除队列的头元素，remove方法在队列为空的情况下将抛异常，而poll方法将返回null；
element和peek方法都是返回队列的头元素，但是不删除头元素，区别在与element方法在队列为空的情况下，将抛异常，而peek方法将返回null

总结：我们一般希望抛出返回值，优先使用offer，poll和peek方法。

数据结构设计 --- 栈实现队列、队列实现栈

队列实现栈（leetcode225）

栈实现队列（leetcode232）

猜你喜欢

热点阅读