Table of Contents

栈Stack

「栈 Stack」是一种遵循「先入后出 first in, last out」数据操作规则的线性数据结构。我们可以将栈类比为放在桌面上的一摞盘子，如果需要拿出底部的盘子，则需要先将上面的盘子依次取出。

我们将这一摞元素的顶部称为「栈顶」，将底部称为「栈底」，将把元素添加到栈顶的操作称为「入栈」，将删除栈顶元素的操作称为「出栈」。

栈常用操作

栈的常用操作见下表（方法命名以 Java 为例）

可以直接使用编程语言实现好的栈类。某些语言并未专门提供栈类，但我们可以直接把该语言的「数组」或「链表」看作栈来使用，并通过“脑补”来屏蔽无关操作

/* 初始化栈 */
// 在 Go 中，推荐将 Slice 当作栈来使用
var stack []int

/* 元素入栈 */
stack = append(stack, 1)
stack = append(stack, 3)
stack = append(stack, 2)
stack = append(stack, 5)
stack = append(stack, 4)

/* 访问栈顶元素 */
peek := stack[len(stack)-1]

/* 元素出栈 */
pop := stack[len(stack)-1]
stack = stack[:len(stack)-1]

/* 获取栈的长度 */
size := len(stack)

/* 判断是否为空 */
isEmpty := len(stack) == 0

栈的实现

栈规定元素是先入后出的，因此我们只能在栈顶添加或删除元素。然而，数组或链表都可以在任意位置添加删除元素，因此 栈可被看作是一种受约束的数组或链表。换言之，我们可以“屏蔽”数组或链表的部分无关操作，使之对外的表现逻辑符合栈的规定即可。

基于链表的实现

使用「链表」实现栈时，将链表的头结点看作栈顶，将尾结点看作栈底。

对于入栈操作，将元素插入到链表头部即可，这种结点添加方式被称为“头插法”。而对于出栈操作，则将头结点从链表中删除即可。

基于链表实现栈的示例代码：

/* 基于链表实现的栈 */
type linkedListStack struct {
    // 使用内置包 list 来实现栈
    data *list.List
}

/* 初始化栈 */
func newLinkedListStack() *linkedListStack {
    return &linkedListStack{
        data: list.New(),
    }
}

/* 入栈 */
func (s *linkedListStack) push(value int) {
    s.data.PushBack(value)
}

/* 出栈 */
func (s *linkedListStack) pop() any {
    if s.isEmpty() {
        return nil
    }
    e := s.data.Back()
    s.data.Remove(e)
    return e.Value
}

/* 访问栈顶元素 */
func (s *linkedListStack) peek() any {
    if s.isEmpty() {
        return nil
    }
    e := s.data.Back()
    return e.Value
}

/* 获取栈的长度 */
func (s *linkedListStack) size() int {
    return s.data.Len()
}

/* 判断栈是否为空 */
func (s *linkedListStack) isEmpty() bool {
    return s.data.Len() == 0
}

/* 获取 List 用于打印 */
func (s *linkedListStack) toList() *list.List {
    return s.data
}

基于数组的实现

使用「数组」实现栈时，考虑将数组的尾部当作栈顶。这样设计下，「入栈」与「出栈」操作就对应在数组尾部「添加元素」与「删除元素」，时间复杂度都为O(1)

由于入栈的元素可能是源源不断的，因此可以使用支持动态扩容的「列表」，这样就无需自行实现数组扩容了。以下是示例代码。

/* 基于数组实现的栈 */
type arrayStack struct {
    data []int // 数据
}

/* 初始化栈 */
func newArrayStack() *arrayStack {
    return &arrayStack{
        // 设置栈的长度为 0，容量为 16
        data: make([]int, 0, 16),
    }
}

/* 栈的长度 */
func (s *arrayStack) size() int {
    return len(s.data)
}

/* 栈是否为空 */
func (s *arrayStack) isEmpty() bool {
    return s.size() == 0
}

/* 入栈 */
func (s *arrayStack) push(v int) {
    // 切片会自动扩容
    s.data = append(s.data, v)
}

/* 出栈 */
func (s *arrayStack) pop() any {
    val := s.peek()
    s.data = s.data[:len(s.data)-1]
    return val
}

/* 获取栈顶元素 */
func (s *arrayStack) peek() any {
    if s.isEmpty() {
        return nil
    }
    val := s.data[len(s.data)-1]
    return val
}

/* 获取 Slice 用于打印 */
func (s *arrayStack) toSlice() []int {
    return s.data
}

栈典型应用

浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页，浏览器就将上一个网页执行入栈，这样我们就可以通过「后退」操作来回到上一页面，后退操作实际上是在执行出栈。如果要同时支持后退和前进，那么则需要两个栈来配合实现。
程序内存管理。每当调用函数时，系统就会在栈顶添加一个栈帧，用来记录函数的上下文信息。在递归函数中，向下递推会不断执行入栈，向上回溯阶段时出栈

队列

「队列 Queue」是一种遵循「先入先出 first in, first out」数据操作规则的线性数据结构。顾名思义，队列模拟的是排队现象，即外面的人不断加入队列尾部，而处于队列头部的人不断地离开。

我们将队列头部称为「队首」，队列尾部称为「队尾」，将把元素加入队尾的操作称为「入队」，删除队首元素的操作称为「出队」

队列常用操作

队列的常用操作见下表

/* 初始化队列 */
// 在 Go 中，将 list 作为队列来使用
queue := list.New()

/* 元素入队 */
queue.PushBack(1)
queue.PushBack(3)
queue.PushBack(2)
queue.PushBack(5)
queue.PushBack(4)

/* 访问队首元素 */
peek := queue.Front()

/* 元素出队 */
poll := queue.Front()
queue.Remove(poll)

/* 获取队列的长度 */
size := queue.Len()

/* 判断队列是否为空 */
isEmpty := queue.Len() == 0

队列实现

队列需要一种可以在一端添加，并在另一端删除的数据结构，也可以使用链表或数组来实现

基于链表的实现

我们将链表的「头结点」和「尾结点」分别看作是队首和队尾，并规定队尾只可添加结点，队首只可删除结点

/* 基于链表实现的队列 */
type linkedListQueue struct {
    // 使用内置包 list 来实现队列
    data *list.List
}

/* 初始化队列 */
func newLinkedListQueue() *linkedListQueue {
    return &linkedListQueue{
        data: list.New(),
    }
}

/* 入队 */
func (s *linkedListQueue) push(value any) {
    s.data.PushBack(value)
}

/* 出队 */
func (s *linkedListQueue) poll() any {
    if s.isEmpty() {
        return nil
    }
    e := s.data.Front()
    s.data.Remove(e)
    return e.Value
}

/* 访问队首元素 */
func (s *linkedListQueue) peek() any {
    if s.isEmpty() {
        return nil
    }
    e := s.data.Front()
    return e.Value
}

/* 获取队列的长度 */
func (s *linkedListQueue) size() int {
    return s.data.Len()
}

/* 判断队列是否为空 */
func (s *linkedListQueue) isEmpty() bool {
    return s.data.Len() == 0
}

/* 获取 List 用于打印 */
func (s *linkedListQueue) toList() *list.List {
    return s.data
}

基于数组的实现

数组的删除首元素的时间复杂度为 O(n),这会导致出队列操作效率低下。然而，我们可以采取下述的巧妙方法来避免这个问题。

借助一个变量 front 来指向队首元素的索引，并维护变量 queSize 来记录队列长度。我们定义 rear = front + queSize ，该公式计算出来的 rear 指向“队尾元素索引 +1 ”的位置

在该设计下，数组中包含元素的有效区间为 [front, rear - 1] ，进而

对于入队操作，将输入元素赋值给 rear 索引处，并将 queSize 自增 1 即可；
对于出队操作，仅需将 front 自增 1 ，并将 queSize 自减 1 即可

可以发现一个问题：在不断入队与出队的过程中，front 和 rear 都在向右移动，在到达数组尾部后就无法继续移动了。为解决此问题，我们考虑将数组看作是首尾相接的，这样的数组被称为「环形数组」。

对于环形数组，我们需要令 front 或 rear 在越过数组尾部后，直接绕回到数组头部接续遍历。这种周期性规律可以通过「取余操作」来实现，详情请见以下代码：

/* 基于环形数组实现的队列 */
type arrayQueue struct {
    nums        []int // 用于存储队列元素的数组
    front       int   // 队首指针，指向队首元素
    queSize     int   // 队列长度
    queCapacity int   // 队列容量（即最大容纳元素数量）
}

/* 初始化队列 */
func newArrayQueue(queCapacity int) *arrayQueue {
    return &arrayQueue{
        nums:        make([]int, queCapacity),
        queCapacity: queCapacity,
        front:       0,
        queSize:     0,
    }
}

/* 获取队列的长度 */
func (q *arrayQueue) size() int {
    return q.queSize
}

/* 判断队列是否为空 */
func (q *arrayQueue) isEmpty() bool {
    return q.queSize == 0
}

/* 入队 */
func (q *arrayQueue) push(num int) {
    // 当 rear == queCapacity 表示队列已满
    if q.queSize == q.queCapacity {
        return
    }
    // 计算尾指针，指向队尾索引 + 1
    // 通过取余操作，实现 rear 越过数组尾部后回到头部
    rear := (q.front + q.queSize) % q.queCapacity
    // 将 num 添加至队尾
    q.nums[rear] = num
    q.queSize++
}

/* 出队 */
func (q *arrayQueue) poll() any {
    num := q.peek()
    // 队首指针向后移动一位，若越过尾部则返回到数组头部
    q.front = (q.front + 1) % q.queCapacity
    q.queSize--
    return num
}

/* 访问队首元素 */
func (q *arrayQueue) peek() any {
    if q.isEmpty() {
        return nil
    }
    return q.nums[q.front]
}

/* 获取 Slice 用于打印 */
func (q *arrayQueue) toSlice() []int {
    rear := (q.front + q.queSize)
    if rear >= q.queCapacity {
        rear %= q.queCapacity
        return append(q.nums[q.front:], q.nums[:rear]...)
    }
    return q.nums[q.front:rear]
}

队列典型应用

淘宝订单。购物者下单后，订单就被加入到队列之中，随后系统再根据顺序依次处理队列中的订单。在双十一时，在短时间内会产生海量的订单，如何处理「高并发」则是工程师们需要重点思考的问题。
各种待办事项。任何需要实现“先来后到”的功能，例如打印机的任务队列、餐厅的出餐队列等等。

双向队列（Deque）

对于队列，我们只能在头部删除或在尾部添加元素，而「双向队列 Deque」更加灵活，在其头部和尾部都能执行元素添加或删除操作

双向队列常用操作

可以直接使用编程语言实现好的双向队列类。

/* 初始化双向队列 */
// 在 Go 中，将 list 作为双向队列使用
deque := list.New()

/* 元素入队 */
deque.PushBack(2)      // 添加至队尾
deque.PushBack(5)
deque.PushBack(4)
deque.PushFront(3)     // 添加至队首
deque.PushFront(1)

/* 访问元素 */
front := deque.Front() // 队首元素
rear := deque.Back()   // 队尾元素

/* 元素出队 */
deque.Remove(front)    // 队首元素出队
deque.Remove(rear)     // 队尾元素出队

/* 获取双向队列的长度 */
size := deque.Len()

/* 判断双向队列是否为空 */
isEmpty := deque.Len() == 0

双向队列实现

基于双向链表的实现

双向队列的头部和尾部都可以执行入队与出队操作，换言之，双向队列的操作是“首尾对称”的，也需要实现另一个对称方向的操作。因此，双向队列需要使用「双向链表」来实现。

我们将双向链表的头结点和尾结点分别看作双向队列的队首和队尾，并且实现在两端都能添加与删除结点。

哈希表（Hash Map）

哈希表通过建立「键 key」和「值 value」之间的映射，实现高效的元素查找。具体地，输入一个 key ，在哈希表中查询并获取 value ，时间复杂度为 O(1) 。

哈希表效率

除了哈希表之外，还可以使用以下数据结构来实现上述查询功能：

无序数组：每个元素为 [学号, 姓名] ；
有序数组：将数组按照学号从小到大排序；
链表：每个结点的值为 [学号, 姓名] ；
二叉搜索树：每个结点的值为 [学号, 姓名] ，根据学号大小来构建树；

哈希表常用操作

哈希表的基本操作包括 初始化、查询操作、添加与删除键值对

/* 初始化哈希表 */
mapp := make(map[int]string)

/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
mapp[12836] = "小哈"
mapp[15937] = "小啰"
mapp[16750] = "小算"
mapp[13276] = "小法"
mapp[10583] = "小鸭"

/* 查询操作 */
// 向哈希表输入键 key ，得到值 value
name := mapp[15937]

/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
delete(mapp, 10583)

遍历哈希表有三种方式，即 遍历键值对、遍历键、遍历值

/* 遍历哈希表 */
// 遍历键值对 key->value
for key, value := range mapp {
    fmt.Println(key, "->", value)
}
// 单独遍历键 key
for key := range mapp {
    fmt.Println(key)
}
// 单独遍历值 value
for _,value := range mapp {
    fmt.Println(value)
}

哈希函数

哈希表中存储元素的数据结构被称为「桶 Bucket」，底层实现可能是数组、链表、二叉树（红黑树），或是它们的组合。

最简单地，我们可以仅用一个「数组」来实现哈希表。首先，将所有 value 放入数组中，那么每个 value 在数组中都有唯一的「索引」。显然，访问 value 需要给定索引，而为了 建立 key 和索引之间的映射关系，我们需要使用「哈希函数 Hash Function」

设数组为 bucket ，哈希函数为 f(x) ，输入键为 key 。那么获取 value 的步骤为：

通过哈希函数计算出索引，即 index = f(key) ；
通过索引在数组中获取值，即 value = bucket[index] ；

以上述学生数据 key 学号 -> value 姓名 为例，我们可以将「哈希函数」设计为

/* 键值对 int->String */
type entry struct {
    key int
    val string
}

/* 基于数组简易实现的哈希表 */
type arrayHashMap struct {
    bucket []*entry
}

/* 初始化哈希表 */
func newArrayHashMap() *arrayHashMap {
    // 初始化一个长度为 100 的桶（数组）
    bucket := make([]*entry, 100)
    return &arrayHashMap{bucket: bucket}
}

/* 哈希函数 */
func (a *arrayHashMap) hashFunc(key int) int {
    index := key % 100
    return index
}

/* 查询操作 */
func (a *arrayHashMap) get(key int) string {
    index := a.hashFunc(key)
    pair := a.bucket[index]
    if pair == nil {
        return "Not Found"
    }
    return pair.val
}

/* 添加操作 */
func (a *arrayHashMap) put(key int, val string) {
    pair := &entry{key: key, val: val}
    index := a.hashFunc(key)
    a.bucket[index] = pair
}

/* 删除操作 */
func (a *arrayHashMap) remove(key int) {
    index := a.hashFunc(key)
    // 置为 nil ，代表删除
    a.bucket[index] = nil
}

/* 获取所有键对 */
func (a *arrayHashMap) entrySet() []*entry {
    var pairs []*entry
    for _, pair := range a.bucket {
        if pair != nil {
            pairs = append(pairs, pair)
        }
    }
    return pairs
}

/* 获取所有键 */
func (a *arrayHashMap) keySet() []int {
    var keys []int
    for _, pair := range a.bucket {
        if pair != nil {
            keys = append(keys, pair.key)
        }
    }
    return keys
}

/* 获取所有值 */
func (a *arrayHashMap) valueSet() []string {
    var values []string
    for _, pair := range a.bucket {
        if pair != nil {
            values = append(values, pair.val)
        }
    }
    return values
}

/* 打印哈希表 */
func (a *arrayHashMap) print() {
    for _, pair := range a.bucket {
        if pair != nil {
            fmt.Println(pair.key, "->", pair.val)
        }
    }
}

哈希冲突

哈希函数f(x)=x%100 会在某些情况下失效。具体地，当输入的 key 后两位相同时，哈希函数的计算结果也相同，指向同一个 value 。例如，分别查询两个学号 12836 和 20336 ，则有f(12836)=f(10336)=36

两个学号指向了同一个姓名，这明显是不对的，我们将这种现象称为「哈希冲突 Hash Collision」

综上所述，一个优秀的「哈希函数」应该具备以下特性：

尽量少地发生哈希冲突；
时间复杂度 O(1) ，计算尽可能高效；
空间使用率高，即“键值对占用空间 / 哈希表总占用空间”尽可能大；

数据结构(2)

2022/07/24