介绍
栈和队列也是我们日常编码中经常使用的数据结构了，它们也都是线性表数据结构，但是在访问元素时具有不同的限制条件。
队列（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 函数的时间复杂度主要由以下两个因素决定：
- 分配内存的时间复杂度：当切片容量不足以存储新元素时，
append函数会重新分配一个更大的底层数组，并将原有元素复制到新的数组中，该操作的时间复杂度为 O(n)。 - 添加新元素的时间复杂度：当切片容量足够存储新元素时，
append函数会直接在底层数组的末尾添加新元素。该操作的时间复杂度为 O(1)。
因此，如果要添加的元素数量比切片当前容量小，则 append 函数的时间复杂度为 O(1)；否则，其时间复杂度为 O(n)。
栈的一些用途：
- 函数调用：函数的调用过程中，可以利用栈保存函数调用时的上下文信息。
- 表达式求值：在进行中缀表达式转换为后缀表达式的过程中，需要用到栈。
- 括号匹配检查：比如，{[] ()[{}]}或[{()}([])]，当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号依次匹配，不匹配和最后栈不为空则括号有问题。
- 浏览器历史管理：浏览器中的导航历史和操作历史通常都是基于一个栈来实现的。
- 编辑器撤销操作：撤销操作可以使用栈来实现，将每一次编辑操作的状态信息保存到栈中，撤销时从栈中弹出最近的状态。