- Article -

数据结构栈和队列(三)

分类于 数据结构与算法 标签 数据结构 算法 队列 发表于2023-03-03 20:00

介绍

栈和队列也是我们日常编码中经常使用的数据结构了,它们也都是线性表数据结构,但是在访问元素时具有不同的限制条件。

队列(Queue)是一种先进先出(FIFO)的数据结构,新元素只能在队尾入队(enqueue),旧元素只能在队首出队(dequeue)。队列用于存储需要按照特定顺序处理的数据,例如任务队列、消息队列等等。队列的实现通常采用数组或链表,时间复杂度为O(1)。

栈(Stack)是一种后进先出(LIFO)的数据结构,新元素只能从栈顶入栈(push),元素只能从栈顶出栈(pop)。栈通常用于实现函数调用、表达式求值、括号匹配等等。栈的实现也通常采用数组或链表,时间复杂度为O(1)。


队列

实现一个队列可以基于数组或者链表,例如我们基于数组的话,入队的时候可以将数据直接push进数组,出队的时候取出第一个元素并删除它即可,但是前面学习数组的时候我们知道,这样每次出队都会迁移数据,但队列很长时还是比较耗性能的。一般可以设置一个head,tail指针,用来指向队首和队尾,比如申请了一个数组为5的队列,往里面入队3个元素的时候,tail就等于3,head就等于0,出队的时候移动head指针就行了,当数据满的时候,我们再来做数据迁移,并重置head指针到0,这样的话就会性能好一些。

示例

package main

import "fmt"
// 定义一个结构体 Queue,表示队列
type Queue struct {
  elements []int // 用一个 slice 存储队列中的元素
  size int    // 表示队列的长度
}
// 定义一个 Enqueue() 方法向队列中添加元素
func (q *Queue) Enqueue(e int) {
  q.elements = append(q.elements, e) // 将元素添加到队列末尾
  q.size++ // 队列长度加 1
}
// 定义一个 Dequeue() 方法从队列中取出元素
func (q *Queue) Dequeue() int {
  if q.size == 0 { // 如果队列为空,返回 -1
		return -1
  }
  e := q.elements[0] // 取出队列头部的元素
  q.elements = q.elements[1:] // 将元素从队列中删除
  q.size-- // 队列长度减 1
  return e
}
// main 函数入口
func main() {
  // 以下是示例代码
  // 初始化一个队列,并向队列中依次添加 1、2、3 三个元素
  q := Queue{}
  q.Enqueue(1)
  q.Enqueue(2)
  q.Enqueue(3)
  // 从队列中依次取出元素,并打印输出
  fmt.Println(q.Dequeue())
  fmt.Println(q.Dequeue())
  fmt.Println(q.Dequeue())
}

这里我们使用golang的slice来实现队列,可能像前面说的,这样会不会每一次都要实现数据迁移啊?抱着这样的疑问,我们问下导师:

我: 在golang中操作slice时,例如slice[:4],他的实际原理是怎样的?时间复杂度是多少

chatGPT: 在 golang 中,slice 表示一个动态数组,可以通过类似 slice[low:high] 的切片操作子切片,例如 slice[:4] 表示从 slice 的开头到第 4 个元素(不包含第 4 个元素)的子切片。slice[low:high] 的实际原理是,底层数组中从索引 low 到 high-1 的连续一段,称为子数组,slice 通过自己的索引和长度描述子数组的一部分。因此,切片是原始数组的一个视图(view),对切片的修改会反映到原始数组中。slice[low:high] 的时间复杂度为 O(high - low),即子数组的长度,因为它的实现只需计算子数组的起始指针和长度,而不需要复制数组元素。由此可见,切片操作非常高效,是 Go 语言常用的特色之一。


在队列中还有两个经常使用的东西,阻塞队列和并发队列。阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说,就是在队列为空的时候,从队头取数据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。

协程池的创建记录篇章我记录了在golang利用通道实现阻塞队列,同时线程安全的队列我们叫作并发队列,因此golang的缓冲通道可以很好的作为阻塞队列或者并发队列。


后进者先出,先进者后出,这就是典型的“栈”结构,

package main

import "fmt"
// 定义一个结构体 Stack,表示栈
type Stack struct {
  elements []int // 用一个 slice 存储栈中的元素
  size int    // 表示栈的长度
}
// 定义一个 Push() 方法向栈中添加元素
func (s *Stack) Push(e int) {
  s.elements = append(s.elements, e) // 将元素添加到栈顶
  s.size++ // 栈长度加 1
}
// 定义一个 Pop() 方法从栈中取出元素
func (s *Stack) Pop() int {
  if s.size == 0 { // 如果栈为空,返回 -1
		return -1
  }
  e := s.elements[s.size-1] // 取出栈顶元素
  s.elements = s.elements[:s.size-1] // 将元素从栈中删除
  s.size-- // 栈长度减 1
  return e

}

// main 函数入口
func main() {
  // 初始化一个栈,并向栈中依次添加 1、2、3 三个元素
  s := Stack{}
  s.Push(1)
  s.Push(2)
  s.Push(3)
  // 从栈中依次取出元素,并打印输出
  fmt.Println(s.Pop())
  fmt.Println(s.Pop())
  fmt.Println(s.Pop())
}

可以分析发现,在出栈时,Pop 里直接通过下标拿到元素,并且删除元素也只是对底层数组元素的视图映射,因此他的时间和空间复杂度都是常数(O(1)),这里注意一下,在分析空间复杂度的时候,数据结构本身所占的内存不应该计算进来,而是算法在计算过程中所产生的额外空间。所以我们说空间复杂度的时候,是指除了原本的数据存储空间外,算法运行还需要额外的存储空间。

在入栈时,主要使用了append函数,append 函数的时间复杂度主要由以下两个因素决定:

  1. 分配内存的时间复杂度:当切片容量不足以存储新元素时,append 函数会重新分配一个更大的底层数组,并将原有元素复制到新的数组中,该操作的时间复杂度为 O(n)。
  2. 添加新元素的时间复杂度:当切片容量足够存储新元素时,append 函数会直接在底层数组的末尾添加新元素。该操作的时间复杂度为 O(1)。

因此,如果要添加的元素数量比切片当前容量小,则 append 函数的时间复杂度为 O(1);否则,其时间复杂度为 O(n)。

栈的一些用途: