Algorithm
Mark Chen |
10 May 2021
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
你使用哪种语言？我们会根据你选择的语言显示对应的代码示例
Python
Java
前置条件
在学习这个知识点前，你应该先学习……
队列
队列 (Queue) 是一种用于收集数据的线性数据结构，主要有两个操作：
- 放入 (Push): 将元素放入队列中
- 取出 (Pop) : 将最先放入的元素从队列中取出
因为在这个数据结构中，最先放入的元素会被最先取出来，和日常生活中的排队情境一样，所以这个数据结构被称作队列。
编程实现
0 - 一个基于 list 的朴素实现
在 Python 与 Java 中，语言的 list 都提供了删除特定元素和在列表末尾添加元素的方法。 所以一种最朴素的实现可以直接使用语言的 list 来完成。
class Queue: def __init__(self): self.data = list() def push(self, element): self.data.append(element) def pop(self): if len(self.data) > 0: return self.data.pop(0) else: raise Exception("Cannot pop from an Empty Queue")import java.util.*; class Queue{ private ArrayList<Integer> arr = new ArrayList<>(); public void push(int element){ this.arr.add(element); } public int pop(){ if (this.arr.size() > 0){ int result = this.arr.get(0); this.arr.remove(0); return result; } else{ return -1; } } }
这种实现方法虽然可以 work，但是当你考虑时间复杂度的时候，你会发现这个实现实际上是非常低效的 - 每次从队列中取出一个元素的时候，你都要从队列中拿出第 0 项，同时将 1 ~ n 的所有元素依次向前挪动一格。 这说明每次从队列中取出元素的时间复杂度是 $O(n)$。
那么有没有可能换一种实现数据结构的方法，从而达到放取都是 $O(1)$ 的时间复杂度的效果呢？
下面我们来看看如何使用刚刚学习的 链表 数据结构来提高 Queue 的效率
1 - 更加高效的队列（链表）
虽然访问链表中间的第 $n$ 个元素需要 $O(n)$ 的时间复杂度，我们可以非常方便的在链表的首尾做对元素进行增删的操作。每次在链表末尾增添一个元素只需要 $O(1)$ 的时间复杂度；同时，删除链表头部的元素也只需要 $O(1)$ 的时间复杂度。通过这两个特性，我们可以让队列做到进出都只需要 $O(1)$ 的时间复杂度。
class LinkedListNode: def __init__(self, val: int) -> None: self.next = None self.val = val class Queue: def __init__(self) -> None: self.head = None self.tail = None self.size = 0 def push(self, val: int) -> None: self.size += 1 new_node = LinkedListNode(val) if self.head == None: self.head = new_node self.tail = new_node else: self.tail.next = new_node self.tail = self.tail.next def pop(self) -> int: self.size -= 1 val = self.head.val self.head = self.head.next return val def size(self) -> int: return self.size def peek(self) -> int: return self.head.val def __str__(self) -> str: ptr = self.head string = "HEAD -> " while ptr.next != None: string += str(ptr.val) + " -> " ptr = ptr.next string += str(ptr.val) + " -> " string += "TAIL" return stringNot Implemented yet, see Python Version
2 - 更加高效的队列（循环数组）
除了链表以外，我们还可以用循环数组来实现队列。
class Queue: def __init__(self, max_capacity: int) -> None: self.arr = [0] * max_capacity self.max_len = max_capacity self.start = 0 self.end = 0 def size(self) -> int: return self.end - self.start def push(self, item: int) -> None: self.end += 1 actual_index = (self.end - 1) % self.max_len self.arr[actual_index] = item def pop(self) -> None: actual_index = self.start % self.max_len self.start += 1 return self.arr[actual_index] def peek(self) -> int: return self.arr[self.start % self.max_len] def __str__(self) -> str: string = "[ " for index, num in enumerate(self.arr): string += str(num) if index == self.start % self.max_len: string += "(START)" if index == self.end % self.max_len: string += "(END)" string += " | " string += " ]" return stringNot Implemented Yet, see Python Version
练习
