算法练习: 队列和双端队列(Queue & Deque)

理论知识

队列
- 09 | 队列：队列在线程池等有限资源池中的应用
双端队列
- 使用Deque - 廖雪峰的官方网站
- swift-algorithm-club/Deque

题目列表

总结

队列和栈有两个最大的不同点: 1) 栈是“先进后出”、队列是“先进先出”；2）队列是两端可以操作，而栈只有一端可以操作。这两点在题目 225. Implement Stack using Queues 和 232. Implement Queue using Stacks 中就体现出来了。
队列既可以用数组来实现，又可以用链表来实现。具体的实现过程见题目分别用数组和链表实现一个队列和实现一个循环队列。
Swift 的标准库中没有提供 Stack 和 Queue，不过我们可以用 Array 来模拟 Stack 和 Queue 的操作。
均摊复杂度分析：通过题目 232. Implement Queue using Stacks 的练习，正好顺便复习了一下均摊时间复杂度的分析以及什么时候需要用到均摊时间复杂度。

分别用数组和链表实现一个队列

2021.01.21

1. 基于数组实现的有界队列（队列大小有限制）

enqueue 的时间复杂度是 dequeue 的时间复杂度是 O(1)

struct ArrayQueue<T> {
    private let capacity: Int
    private var storage: [T?]
    private var head = 0
    private var tail = 0

    init() {
        self.capacity = 100
        storage = [T?](repeating: nil, count: capacity)
    }

    init(capacity: Int) {
        self.capacity = capacity
        storage = [T?](repeating: nil, count: capacity)
    }

    @discardableResult
    mutating func enqueue(_ item: T) -> Bool {
        // 两端是否还有剩余空间
        guard tail < capacity || head > 0 else {
            return false
        }

        // 尾端已经没有空间了，需要整体搬移
        if tail == capacity {
            for i in head..<tail {
                storage[i-head] = storage[i]
            }
            tail -= head
            head = 0
        }

        storage[tail] = item
        tail += 1
        return true
    }

    mutating func dequeue() -> T? {
        guard head < tail else {
            return nil
        }
        let item = storage[head]
        head += 1
        return item
    }
}

extension ArrayQueue: CustomStringConvertible {

    var description: String {
        return storage[head..<tail].description
    }

}

2. 基于链表实现的无界队列（支持无限排队）

enqueue 的时间复杂度是 O(1) dequeue 的时间复杂度是 O(1)


/// 链表
class ListNode<T> {
    let value: T
    var next: ListNode<T>?

    init(value: T) {
        self.value = value
        self.next = nil
    }

    init(value: T, next: ListNode<T>?) {
        self.value = value
        self.next = next
    }
}

extension ListNode: CustomStringConvertible {
    var description: String {
        var str = "\(value)"
        var node: ListNode = self
        while node.next != nil {
            str += " -> "
            str += "\(node.next!.value)"
            node = node.next!
        }
        return str
    }
}

/// 队列(支持无限排队)
struct LinkedListQueue<T> {
    private var head: ListNode<T>?
    private var tail: ListNode<T>?
    private var count = 0

    @discardableResult
    mutating func enqueue(_ item: T) -> Bool {
        if head == nil || tail == nil {
            head = ListNode(value: item)
            tail = head
        } else {
            tail?.next = ListNode(value: item)
            tail = tail?.next
        }
        count += 1
        return true
    }

    mutating func dequeue() -> T? {
        guard count > 0 else {
            return nil
        }

        let item = head
        head = item?.next
        count -= 1
        return item?.value
    }
}

extension LinkedListQueue: CustomStringConvertible {

    var description: String {
        return head?.description ?? ""
    }

}

核心思路：当 tail 指针已经指向数组中最后一个元素时，如果再有新的元素入队列，则将 tail 指针指向第 0 个元素(前提是当前 head 在第 0 个元素之后)，以此类推，如下图所示。难点：实现的关键是如何判断队列是满的，tail 和 head 之间要相差一个元素。 易错点：如何判断队列是满的；当 head 或者 tail 到达数组最后一个元素时，再出列或者入列时会不会数组越界。

时间复杂度：enqueue 和 dequeue 都是 O(1) 空间复杂度：O(N)，一个用来存储数据的数组，N 为要存储的元素个数

代码实现：

/// 循环队列
struct CircularQueue<T> {
    let capacity: Int
    private var storage: [T?]
    private var head = 0
    private var tail = 0

    init() {
        self.capacity = 100
        self.storage = [T?](repeating: nil, count: capacity)
    }

    init(capacity: Int) {
        self.capacity = capacity
        self.storage = [T?](repeating: nil, count: capacity)
    }

    @discardableResult
    mutating func enqueue(_ item: T) -> Bool {
        guard (tail + 1) % capacity != head else {
            return false
        }

        storage[tail] = item
        tail = (tail + 1) % capacity
        return true
    }

    @discardableResult
    mutating func dequeue() -> T? {
        guard head != tail else {
            return nil
        }

        let item = storage[head]
        storage[head] = nil
        head = (head + 1) % capacity
        return item
    }
}

extension CircularQueue: CustomStringConvertible {
    var description: String {
        return storage.description
    }
}

测试 case：

var queue = CircularQueue<Int>(capacity: 4)
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue)          // 输出 [1, 2, 3, nil]
queue.dequeue()
print(queue)          // 输出 [nil, 2, 3, nil]
queue.enqueue(4)
queue.enqueue(5)
print(queue)          // 输出 [nil, 2, 3, 4]
queue.dequeue()
print(queue)         // 输出 [nil, nil, 3, 4]
queue.enqueue(5)
print(queue)         // 输出 [5, nil, 3, 4]
queue.dequeue()
print(queue)
queue.dequeue()
print(queue)
queue.dequeue()
print(queue)         // 输出 [nil, nil, nil, nil]

225. Implement Stack using Queues

2021.01.24

建议：画图，画图，还是画图！

解法一：两个队列( push - `O(N)`, pop `O(1)`)

每次 push 新的元素时，我们将它 enqueue 到队列 A 中，然后再把队列 B 中的元素出列并重新 enqueue 到队列 A 中。最后再将队列 A 和队列 B 的变量互换。

思路：因为栈的特点是”后进先出“，而队列的特点是”先进先出“，所以我们可以想办法让队列中”最晚进“的元素变成”最早进“的元素。核心思想就是在每次 push 新的元素时，我们将它 enqueue 到队列 A 中，然后再把队列 B 中的元素出列并重新 enqueue 到队列 A 中，这样就达到了新 push 的元素变成了队列中最早入队的元素，此时队列 B 就为空了，我们再将指向队列 A 和队列 B 的变量互换一下，最终队列 A 就为空了，队列 B 就是刚好符合”后进先出“的”栈“了（具体的动效见题解）。

时间复杂度：push 的操作是 O(N)，其他操作为 O(1)，N 为栈中元素的个数 空间复杂度：O(N)，N 为栈中元素的个数

class MyStack {
    var queue1 = [Int]() // 用来存储栈中数据的队列
    var queue2 = [Int]() // 用来转移数据的队列

    func push(_ x: Int) {
        queue2.append(x)
        while !queue1.isEmpty {
            let item = queue1.removeFirst()
            queue2.append(item)
        }

        let tmpQueue1 = queue1
        queue1 = queue2
        queue2 = tmpQueue1
    }

    func pop() -> Int {
        return queue1.removeFirst()
    }

    func top() -> Int {
        return queue1.first!
    }

    func empty() -> Bool {
        return queue1.isEmpty
    }
}

解法二：两个队列( push - `O(1)`, pop `O(N)`)

在 pop 的时候将队列 A 中的前 N-1 个元素都先转移到队列 B 中，最后队列 A 中就只剩下要 pop 的元素了；另外 top 的值可以在 push 和 pop 的时候用一个变量记录下来。

思路：因为队列的特点是”先进先出“，所以我们可以在 push 时正常入队列 A，在 pop 的时候将队列 A 中的前 N-1 个元素都先转移到队列 B 中，最后队列 A 中就只剩下要 pop 的元素了；另外 top 的值可以在 push 和 pop 的时候用一个变量记录下来（具体的图解见题解 Approach #1）。

时间复杂度：pop 的操作是 O(N)，其他操作为 O(1)，N 为栈中元素的个数 空间复杂度：O(N)，N 为栈中元素的个数

class MyStack {
    var queue1 = [Int]()
    var queue2 = [Int]()
    var topItem: Int?

    func push(_ x: Int) {
        queue1.append(x)
        topItem = x
    }

    func pop() -> Int {
        while queue1.count > 1 {
            topItem = queue1.removeFirst()
            queue2.append(topItem!)
        }
        let popped = queue1.removeFirst()

        let temp = queue1
        queue1 = queue2
        queue2 = temp

        return popped
    }

    func top() -> Int {
        return topItem!
    }

    func empty() -> Bool {
        return queue1.isEmpty
    }
}

解法三：一个队列

在 push 新元素后，让前面已经入队的各个元素出队再重新入队。

思路：跟解法一中的要点分析类似，因为栈的特点是”后进先出“，而队列的特点是”先进先出“，所以我们可以想办法让队列中”最晚进“的元素变成”最早进“的元素。用一个队列也可以做到这个效果，那就是在 push 新元素后，让前面已经入队的各个元素再重新排队，这样就可以实现“晚到的先走”了（具体的动效见题解）。

时间复杂度：push 的操作是 O(N)，其他操作为 O(1)，N 为栈中元素的个数 空间复杂度：O(N)，N 为栈中元素的个数

class MyStack {
    var queue = [Int]()

    func push(_ x: Int) {
        queue.append(x)
        // 前面的 n-1 个元素出列再重新入列
        for _ in 0..<queue.count-1 {
            let item = queue.removeFirst()
            queue.append(item)
        }
    }

    func pop() -> Int {
        return queue.removeFirst()
    }

    func top() -> Int {
        return queue.first!
    }

    func empty() -> Bool {
        return queue.isEmpty
    }
}

232. Implement Queue using Stacks

2021.01.24

建议：画图，画图，还是画图！

解法一：两个栈（Push - `O(N)`, Pop - `O(1)`）

stack1 用来存储数据，stack2 用来临时转移数据。enqueue 时，把 stack1 中的元素转移到 stack2 中，然后 pop 栈顶元素，最后再转移回 stack1。

思路：因为队列的特点是”先进先出“，而栈的特点是”后进先出“，所以我们可以想办法让栈中的元素顺序颠倒过来。那么怎么“颠倒”栈中的元素顺序呢？我们要做的是在每次新元素入队列的时候，通过两次转移把栈中的元素按照入栈顺序颠倒过来。具体做法是，每次在新元素入队列时，先将上一次逆序过的栈 s1 中的元素依次出栈，转移到栈 s2 中，然后再将新元素入栈 s2，最后再将栈 s2 中的元素依次出栈，转移到栈 s1 中。 时间复杂度：push 的操作是 O(N)，其他操作为 O(1)，N 为队列中元素的个数 空间复杂度：O(N)，N 为队列中元素的个数

图解(push 的过程)：

    s1           s2            s1

                  |
                  v
 |     |  -->  |  1  |  -->  |  1  |
 +-----+       +-----+       +-----+

                  |
                  v
 |     |       |  2  |       |  1  |
 +-----+  -->  +-----+  -->  +-----+
 |  1  |       |  1  |       |  2  |
 +-----+       +-----+       +-----+

                  |
                  v
 |     |       |  3  |       |  1  |
 +-----+       +-----+       +-----+
 |  1  |  -->  |  2  |  -->  |  2  |
 +-----+       +-----+       +-----+
 |  2  |       |  1  |       |  3  |
 +-----+       +-----+       +-----+

代码实现：

class MyQueue {
    var stack1 = [Int]() // 用来按顺序存储队列中的元素
    var stack2 = [Int]() // 用来转移数据的栈

    func push(_ x: Int) {
        // 先将逆序的 stack1 中的元素转移到 stack2 中，比如 stack1 [3, 2, 1] -> stack2 [1, 2, 3]
        while !stack1.isEmpty {
            stack2.append(stack1.popLast()!)
        }
        // stack2 入栈新元素，stack2 [1, 2, 3] -> stack2 [1, 2, 3, 4]
        stack2.append(x)

        // 然后再将顺序的 stack2 中的元素转移到 stack1 中，比如 stack2 [1, 2, 3, 4] -> stack1 [4, 3, 2, 1]
        while !stack2.isEmpty {
            stack1.append(stack2.popLast()!)
        }
    }

    func pop() -> Int {
        return stack1.popLast()!
    }

    func peek() -> Int {
        return stack1.last!
    }

    func empty() -> Bool {
        return stack1.isEmpty
    }
}

解法二：两个栈（Push - `O(1)`, Pop - 均摊复杂度 `O(1)`）

stack1 用来入队，stack2 用来出队。dequeue 时，如果 stack2 中没有了，就把 stack1 中的元素移到 stack2 中，否则直接从 stack2 中 pop。

思路：第二种解法也是让栈中的元素顺序颠倒过来，但不是在 push 的时候一次性反转过来，而是在 pop 的时候“按需反转”。具体做法是，每次在新元素入队列时，直接入栈 s1，在 pop 的时候再看 s2 中是否有倒序的元素，如果没有则从 s1 转移到 s2 中，这样 s2 的栈顶就是最底下的元素了，也就是最早入栈的元素，然后再 pop 出 s2 中的栈顶元素；如果 s2 中已经有了倒序的元素，则直接 pop 出 s2 中的栈顶元素。在处理 peek 和 isEmpty 时，也需要同时考虑 s1 和 s2 两部分，s2 中是已经逆序过的元素，s1 中是待处理的元素。

时间复杂度：pop 的操作是 O(N)，其他操作为 O(1)，N 为队列中元素的个数 空间复杂度：O(N)，N 为队列中元素的个数

关于 pop 操作的时间复杂度分析： 摊还复杂度 O(1)，最坏情况下的时间复杂度 O(N)。在最坏情况下，s2 为空，算法需要从 s1 中弹出 n 个元素，然后再把这 n 个元素压入 s2，在这里 n 代表队列的大小。这个过程产生了 2n 步操作，时间复杂度为 O(n)。但当 s2 非空时，算法就只有 O(1) 的时间复杂度。关于摊还复杂度分析的详细介绍见题解。

图解(pop 的过程)：

            s1            s2          s2

          |  2  |       |     |
push 1,2  +-----+       |     |
          |  1  |       |     |
          +-----+       +-----+

          |     |       |  1  |       |     |
 pop      |     |  -->  +-----+  -->  |     |
          |     |       |  2  |       |  2  |
          +-----+       +-----+       +-----+

          |  4  |       |     |
push 3,4  +-----+       |     |
          |  3  |       |  2  |
          +-----+       +-----+

          |  4  |       |     |
 pop      +-----+       |     |
          |  3  |       |     |
          +-----+       +-----+

          |     |       |  3  |       |     |
 pop      |     |  -->  +-----+  -->  |     |
          |     |       |  4  |       |  4  |
          +-----+       +-----+       +-----+

          |     |       |     |       |     |
 pop      |     |       |     |  -->  |     |
          |     |       |  4  |       |     |
          +-----+       +-----+       +-----+

代码实现：

class MyQueue {
    var stack1 = [Int]() // 用来 push 的栈
    var stack2 = [Int]() // 用来 pop 的栈
    var firstOfStack1: Int?

    func push(_ x: Int) {
        if stack1.isEmpty {
            firstOfStack1 = x
        }

        stack1.append(x)
    }

    func pop() -> Int {
        if stack2.isEmpty {
            while !stack1.isEmpty {
                stack2.append(stack1.popLast()!)
            }
        }
        return stack2.popLast()!
    }

    func peek() -> Int {
        return !stack2.isEmpty ? stack2.last! : firstOfStack1!
    }

    func empty() -> Bool {
        return stack1.isEmpty && stack2.isEmpty
    }
}

ShannonChenCHN / algorithm-and-data-structure