Go：数据结构与算法入门，数组、链表、栈、队列在代码里怎么实现和使用

发表于 2018-08-15 分类于 Go 本文字数： 6k 阅读时长 ≈ 22 分钟

Go 里的数据结构入门，重点不是背定义，而是把数组、链表、栈、队列和真实代码连起来。这篇文章围绕一个最小任务执行器，讲清这四种结构在 Go 里怎么实现、时间复杂度是什么、哪里适合用、哪里不适合硬套，以及写错后通常会出现什么问题。

学 Go 进入工程阶段后，数据结构这条线迟早会撞上来。

表面上看，业务代码好像一直在写 struct、slice、map、interface、context、http。
真正把代码往下拆一层，会发现下面这些结构一直在反复出现：

固定长度的数据槽位
按顺序进入、按顺序处理的任务集合
后进先出的回滚动作
需要频繁在头尾移动节点的链式结构

如果这条线没补上，代码容易出现几类典型问题：

该用固定长度结构时，写成了会不断扩容的切片
该用 FIFO 队列时，直接用 append 和 items[0]
该用 LIFO 栈时，写成一堆散落的临时变量
看到链表就当成“高级数据结构”，结果把简单问题写复杂

这一篇不按刷题口径展开，而是按 Go 工程代码的视角来讲：

数组、链表、栈、队列分别解决什么问题
它们在 Go 里怎么实现
时间复杂度和内存特征分别是什么
在真实项目里通常会在哪些位置出现
代码写错后，怎么测、怎么查、怎么改

贯穿全文的小场景是：做一个最小任务执行器。

这个执行器要做几件事：

用队列缓存待执行任务
用栈记录已经执行的动作，失败时按逆序回滚
用数组记录固定数量的 worker 槽位状态
用链表维护一条重试链，保存需要下一轮再处理的任务

这个场景不大，但足够把四种结构的角色一次讲清。

一、先把四种结构的角色讲清楚

先不急着写代码，先把“它们分别在解决什么问题”说透。

1. 数组

数组解决的是：长度固定、内存连续、按下标访问。

典型特征：

长度写进类型里，例如 [4]int
元素连续存放
读写下标是 O(1)
复制数组时，会复制整块数据

在 Go 里，数组不像切片那样常直接暴露在业务代码表层，但它没有消失。
固定大小的状态槽位、协议头、哈希桶底层、编译期常量表，这些位置都能看到数组思路。

2. 链表

链表解决的是：节点分散存放，通过指针串起来，插入删除时不需要整体搬移。

典型特征：

节点不要求连续内存
已知节点位置时，插入删除成本低
按位置随机访问很慢，要从头走
每个节点额外带指针开销

链表在 Go 业务代码里不是默认首选，但在这些位置仍然有价值：

频繁做头尾插入删除
需要稳定节点引用
LRU、就绪链、空闲链、重试链这类结构

3. 栈

栈解决的是：后进先出，最后放进去的元素最先拿出来。

典型场景：

表达式解析
DFS
回滚动作
函数调用栈类思路

4. 队列

队列解决的是：先进先出，先来的元素先处理。

典型场景：

任务调度
worker pool
消息缓冲
BFS
批处理流水线

把这四个角色先分清，后面代码才不会一上来就乱用。

二、先给一个最小示例，看它们长什么样

先看极小版本，不掺太多工程包装。

package main

import "fmt"

func main() {
	arr := [3]int{10, 20, 30}

	stack := []int{}
	stack = append(stack, 1)
	stack = append(stack, 2)
	top := stack[len(stack)-1]
	stack = stack[:len(stack)-1]

	queue := []int{1, 2, 3}
	first := queue[0]
	queue = queue[1:]

	fmt.Println(arr[1], top, first)
}

输出：

20 2 1

这个例子只是让结构先露个脸：

[3]int 是数组
用切片尾部 append/pop 可以先实现一个简单栈
用切片头部取值可以先实现一个简单队列

链表没有直接出现，是因为 Go 没有内建语法糖，需要自己定义节点。

三、数组在 Go 里怎么理解

数组在 Go 里的第一个关键点是：长度属于类型的一部分。

package main

import "fmt"

func main() {
	a := [3]int{1, 2, 3}
	b := [3]int{1, 2, 3}

	fmt.Println(a == b)
}

输出：

true

这里有两个很重要的含义：

[3]int 和 [4]int 不是同一种类型
数组是值类型，赋值和传参默认是整体复制

1. 数组的最小工程示例

假设一个进程只开 4 个 worker 槽位，这个数量在启动时就固定：

package scheduler

type WorkerSlot struct {
	ID     int
	Busy   bool
	TaskID string
}

type WorkerTable struct {
	Slots [4]WorkerSlot
}

func (t *WorkerTable) Assign(taskID string) bool {
	for i := range t.Slots {
		if !t.Slots[i].Busy {
			t.Slots[i].Busy = true
			t.Slots[i].TaskID = taskID
			return true
		}
	}
	return false
}

func (t *WorkerTable) Release(taskID string) {
	for i := range t.Slots {
		if t.Slots[i].TaskID == taskID {
			t.Slots[i] = WorkerSlot{ID: t.Slots[i].ID}
			return
		}
	}
}

这种场景用数组是自然的，因为：

槽位数固定
下标访问直接
不需要动态扩缩容
数据布局简单

2. 为什么数组在 Go 里不常直接当作“动态集合”

因为真实业务里，“长度固定”并不常见。
大多数集合都需要：

动态增长
可切分
可传递
能和标准库函数直接配合

这也是为什么日常更常见的是 slice，不是 [N]T。

但这里不要走到另一个极端，以为数组没用。
数组仍然适合：

固定槽位
固定长度窗口
协议字段
固定大小缓冲区
对拷贝和布局有明确预期的代码

3. 数组最容易写错的地方：传参复制

package main

import "fmt"

func fill(arr [3]int) {
	arr[0] = 99
}

func main() {
	arr := [3]int{1, 2, 3}
	fill(arr)
	fmt.Println(arr)
}

输出：

[1 2 3]

原因不是函数没执行，而是 fill 收到的是数组副本。

如果你确实要修改原数组，可以传指针：

1
2
3

func fill(arr *[3]int) {
	arr[0] = 99
}

4. 数组与切片的关系

Go 学到这里时，最容易混淆的点是：数组和切片关系很近，但不是同一个东西。

数组：值类型，长度固定，类型里带长度
切片：对底层数组的一层描述，包含指针、长度、容量

如果文章主题是“动态集合”，主角通常是切片。
如果主题是“固定布局”，数组更直接。

四、链表在 Go 里怎么自己实现

链表没有内建字面量写法，先从最小单链表开始。

package list

type Task struct {
	ID       string
	Retry    int
	Priority int
}

type Node struct {
	Value Task
	Next  *Node
}

type LinkedList struct {
	head *Node
	tail *Node
	len  int
}

func (l *LinkedList) PushBack(task Task) {
	node := &Node{Value: task}
	if l.tail == nil {
		l.head = node
		l.tail = node
		l.len = 1
		return
	}
	l.tail.Next = node
	l.tail = node
	l.len++
}

func (l *LinkedList) PopFront() (Task, bool) {
	if l.head == nil {
		return Task{}, false
	}

	node := l.head
	l.head = node.Next
	if l.head == nil {
		l.tail = nil
	}
	l.len--
	return node.Value, true
}

func (l *LinkedList) Len() int {
	return l.len
}

这就是一个最小可用单链表：

PushBack 在尾部追加
PopFront 在头部弹出
head 和 tail 分别保存头尾
len 单独维护长度，避免每次遍历统计

1. 链表为什么不是默认首选

因为链表虽然头尾插入删除方便，但它有明显代价：

不能像数组或切片那样按下标直接访问
节点分散，缓存局部性差
每个节点多一个或多个指针
代码复杂度高于切片

所以在 Go 业务代码里，链表通常不是“默认集合”。
大部分时候，切片已经够用，而且更简单。

2. 链表在哪些地方更合适

这些位置更容易看到链表思路：

重试链
空闲连接链
LRU 的双向链表部分
需要 O(1) 级别移除当前节点的结构

标准库里也有现成实现：container/list。
它是双向链表，适合这些场景：

需要从中间删除某个已知元素
需要把节点从一个位置移到另一个位置
需要稳定的元素句柄

如果只是想要“一个可以放数据的集合”，直接上 container/list 往往没有必要。

3. 链表最容易写错的地方

第一类错误是忘了同步更新 tail。

func (l *LinkedList) PopFront() (Task, bool) {
	if l.head == nil {
		return Task{}, false
	}

	node := l.head
	l.head = node.Next
	l.len--
	return node.Value, true
}

这段代码在最后一个节点被弹出时，tail 还指向旧节点。
后面再追加元素，就可能把链表状态弄乱。

第二类错误是把“需要随机访问”的需求硬塞给链表。
例如第 100 个元素访问，如果每次都要从头走，复杂度就是 O(n)。

五、栈在 Go 里怎么实现

栈的核心不是“长得像什么”，而是操作约束只有一条：后进先出。

在 Go 里，实现最简单的栈通常直接用切片。

package stack

import "errors"

var ErrEmptyStack = errors.New("empty stack")

type RollbackAction struct {
	Name string
}

type Stack struct {
	items []RollbackAction
}

func (s *Stack) Push(action RollbackAction) {
	s.items = append(s.items, action)
}

func (s *Stack) Pop() (RollbackAction, error) {
	if len(s.items) == 0 {
		return RollbackAction{}, ErrEmptyStack
	}

	last := len(s.items) - 1
	item := s.items[last]
	s.items[last] = RollbackAction{}
	s.items = s.items[:last]
	return item, nil
}

func (s *Stack) Len() int {
	return len(s.items)
}

1. 为什么栈在工程里很常见

因为只要遇到“失败时按相反顺序撤销”这类动作，栈就天然合适。

例如一个任务执行三步：

创建目录
写配置
启动进程

如果第三步失败，回滚顺序通常是：

停掉已启动的资源
删除配置
删除目录

这个顺序和执行顺序刚好相反，天然就是栈。

2. 栈的错误示例

最常见的错误是把 Pop 写成“取到了值，但没缩切片”。

func (s *Stack) Pop() (RollbackAction, error) {
	if len(s.items) == 0 {
		return RollbackAction{}, ErrEmptyStack
	}
	return s.items[len(s.items)-1], nil
}

这个版本会导致：

每次 Pop 都取到同一个尾元素
长度永远不变
调用方以为已经弹出，实际数据还留在里面

另一个问题是把栈拿去做跨 goroutine 共享容器。
上面这个版本没有并发保护，多协程同时 Push/Pop 会有竞态。

六、队列在 Go 里怎么实现

队列的核心约束是先进先出。

先看一个能工作的最小版本：

package queue

import "errors"

var ErrEmptyQueue = errors.New("empty queue")

type Task struct {
	ID string
}

type Queue struct {
	items []Task
	head  int
}

func (q *Queue) Push(task Task) {
	q.items = append(q.items, task)
}

func (q *Queue) Pop() (Task, error) {
	if q.head >= len(q.items) {
		return Task{}, ErrEmptyQueue
	}

	item := q.items[q.head]
	q.items[q.head] = Task{}
	q.head++

	if q.head > 64 && q.head*2 >= len(q.items) {
		next := make([]Task, len(q.items)-q.head)
		copy(next, q.items[q.head:])
		q.items = next
		q.head = 0
	}

	return item, nil
}

func (q *Queue) Len() int {
	return len(q.items) - q.head
}

这个版本比 items = items[1:] 多做了两件事：

用 head 记录队首位置
在前半段空洞过多时做一次压缩

1. 为什么不直接写 `q.items = q.items[1:]`

因为那个版本虽然能工作，但有两个工程问题：

频繁切头部，底层数组仍然可能保留旧数据引用
队列长期运行时，容量和实际有效长度容易脱节

一个最容易在值班时看到的现象是：

任务处理速度正常
队列长度看上去不大
进程内存却一直不降

如果队列元素本身又比较大，问题会放得更明显。

2. 队列在哪些地方最常见

这些场景都很典型：

worker pool 待处理任务
消息消费缓存
批处理分发器
限流器内部待办集合
广度优先搜索

如果是多 goroutine 协作，channel 也经常承担队列角色。
但 channel 和手写队列不是同一个问题：

channel 更偏并发通信
手写队列更偏数据结构控制

需要自定义删除、重排、批量取出、观测长度、做快照时，手写队列更直接。

3. 队列最容易写错的地方

第一类错误是直接从头部 append/copy，每次出队都做大搬移。
第二类错误是一直切头部，旧元素引用不清空。
第三类错误是把单线程队列拿去并发场景直接共用。

七、时间复杂度先放到一张表里

写到这里，可以先把复杂度放平：

结构	头部插入	头部删除	尾部插入	尾部删除	随机访问
数组	`O(n)`	`O(n)`	固定长度不适用	固定长度不适用	`O(1)`
链表	`O(1)`	`O(1)`	有尾指针时 `O(1)`	单链表删尾通常 `O(n)`	`O(n)`
栈	不关注头部	不关注头部	`Push O(1)` 均摊	`Pop O(1)`	不适用
队列	取决于实现	`Pop O(1)`	`Push O(1)` 均摊	不关注尾删	不适用

这个表不是让你背，而是让你形成结构直觉：

想按下标读，就先看数组/切片
想 FIFO，就先看队列
想 LIFO，就先看栈
想频繁移动节点位置，再考虑链表

八、一个更接近真实项目的小场景：最小任务执行器

下面把四种结构放进一个完整点的小项目里。

需求：

进程里固定开 4 个 worker
新任务先进入待执行队列
每个任务执行时记录回滚动作
执行失败的任务挂进重试链
每轮执行结束后，输出 4 个 worker 当前槽位状态

1. 先定义任务和执行器

package executor

import "fmt"

type Task struct {
	ID    string
	Steps []string
}

type WorkerSlot struct {
	ID     int
	Busy   bool
	TaskID string
}

type RetryNode struct {
	Value Task
	Next  *RetryNode
}

type RetryList struct {
	head *RetryNode
	tail *RetryNode
	len  int
}

func (l *RetryList) PushBack(task Task) {
	node := &RetryNode{Value: task}
	if l.tail == nil {
		l.head = node
		l.tail = node
		l.len = 1
		return
	}
	l.tail.Next = node
	l.tail = node
	l.len++
}

type ActionStack struct {
	items []string
}

func (s *ActionStack) Push(v string) {
	s.items = append(s.items, v)
}

func (s *ActionStack) Pop() (string, bool) {
	if len(s.items) == 0 {
		return "", false
	}
	last := len(s.items) - 1
	v := s.items[last]
	s.items[last] = ""
	s.items = s.items[:last]
	return v, true
}

type TaskQueue struct {
	items []Task
	head  int
}

func (q *TaskQueue) Push(task Task) {
	q.items = append(q.items, task)
}

func (q *TaskQueue) Pop() (Task, bool) {
	if q.head >= len(q.items) {
		return Task{}, false
	}
	task := q.items[q.head]
	q.items[q.head] = Task{}
	q.head++
	return task, true
}

type Executor struct {
	Workers [4]WorkerSlot
	Queue   TaskQueue
	Retry   RetryList
}

func NewExecutor() *Executor {
	exec := &Executor{}
	for i := range exec.Workers {
		exec.Workers[i].ID = i + 1
	}
	return exec
}

func (e *Executor) RunOne(shouldFail bool) error {
	task, ok := e.Queue.Pop()
	if !ok {
		return fmt.Errorf("no task")
	}

	slotIndex := -1
	for i := range e.Workers {
		if !e.Workers[i].Busy {
			slotIndex = i
			e.Workers[i].Busy = true
			e.Workers[i].TaskID = task.ID
			break
		}
	}
	if slotIndex == -1 {
		return fmt.Errorf("no idle worker")
	}
	defer func() {
		e.Workers[slotIndex].Busy = false
		e.Workers[slotIndex].TaskID = ""
	}()

	var actions ActionStack
	for _, step := range task.Steps {
		actions.Push("rollback_" + step)
		if shouldFail && step == "start" {
			for {
				action, ok := actions.Pop()
				if !ok {
					break
				}
				fmt.Println("rollback:", action)
			}
			e.Retry.PushBack(task)
			return fmt.Errorf("run task %s failed", task.ID)
		}
	}

	return nil
}

2. 这里四种结构分别承担什么角色

Workers [4]WorkerSlot
这是固定长度数组，表达的是“进程只管理 4 个槽位”
TaskQueue
这是 FIFO 队列，表达的是“谁先进入就先处理谁”
ActionStack
这是 LIFO 栈，表达的是“回滚顺序和执行顺序相反”
RetryList
这是单链表，表达的是“失败任务先挂起来，下一轮再统一扫”

这个场景有两个现实意义：

结构不是为了炫技，而是和业务约束一一对应
不是所有集合都该默认用一个 []T 糊过去

九、先看一个运行示例

可以给执行器塞两条任务：

func main() {
	exec := NewExecutor()
	exec.Queue.Push(Task{ID: "task-1", Steps: []string{"prepare", "write", "start"}})
	exec.Queue.Push(Task{ID: "task-2", Steps: []string{"prepare", "start"}})

	_ = exec.RunOne(true)
	_ = exec.RunOne(false)
}

示例输出：

1
2
3

rollback: rollback_start
rollback: rollback_write
rollback: rollback_prepare

这里可以直接看到栈的价值：

执行顺序：prepare -> write -> start
回滚顺序：start -> write -> prepare

这类动作如果不用栈，代码通常会散成很多 if/else 和临时状态。

十、怎么测试这几种结构

数据结构文章如果只讲实现，不讲验证，后面很容易在边界条件上翻车。

1. 测数组相关行为

先测“数组传参是复制”。

func fill(arr [3]int) {
	arr[0] = 99
}

func TestArrayPassByValue(t *testing.T) {
	arr := [3]int{1, 2, 3}
	fill(arr)

	if arr[0] != 1 {
		t.Fatalf("expected arr[0] to remain 1, got %d", arr[0])
	}
}

2. 测链表头尾边界

func TestLinkedListPushBackAndPopFront(t *testing.T) {
	var list LinkedList
	list.PushBack(Task{ID: "a"})
	list.PushBack(Task{ID: "b"})

	first, ok := list.PopFront()
	if !ok || first.ID != "a" {
		t.Fatalf("expected first task a, got %+v ok=%v", first, ok)
	}

	second, ok := list.PopFront()
	if !ok || second.ID != "b" {
		t.Fatalf("expected second task b, got %+v ok=%v", second, ok)
	}

	if _, ok := list.PopFront(); ok {
		t.Fatalf("expected empty list")
	}
}

这里测的不是“能不能跑”，而是：

头节点弹出后链是否正确前移
最后一个元素弹出后 tail 是否同步清空

3. 测栈的 LIFO

func TestStackPopOrder(t *testing.T) {
	var stack Stack
	stack.Push(RollbackAction{Name: "prepare"})
	stack.Push(RollbackAction{Name: "write"})
	stack.Push(RollbackAction{Name: "start"})

	item, _ := stack.Pop()
	if item.Name != "start" {
		t.Fatalf("expected start, got %s", item.Name)
	}
}

4. 测队列的 FIFO 与长度

func TestQueueFIFO(t *testing.T) {
	var q Queue
	q.Push(Task{ID: "1"})
	q.Push(Task{ID: "2"})

	first, _ := q.Pop()
	second, _ := q.Pop()

	if first.ID != "1" || second.ID != "2" {
		t.Fatalf("unexpected order: first=%s second=%s", first.ID, second.ID)
	}
	if q.Len() != 0 {
		t.Fatalf("expected queue len 0, got %d", q.Len())
	}
}

5. 测完整任务执行器

func TestExecutorRetryOnFailure(t *testing.T) {
	exec := NewExecutor()
	exec.Queue.Push(Task{
		ID:    "task-1",
		Steps: []string{"prepare", "write", "start"},
	})

	err := exec.RunOne(true)
	if err == nil {
		t.Fatalf("expected run failure")
	}

	if exec.Retry.len != 1 {
		t.Fatalf("expected retry list len 1, got %d", exec.Retry.len)
	}
	if exec.Queue.head != 1 {
		t.Fatalf("expected queue head moved to 1, got %d", exec.Queue.head)
	}
}

6. 实际执行命令

1	go test ./...

如果按上面的最小结构拆包，正常输出会类似：

ok  	example.com/ds/list	0.003s
ok  	example.com/ds/queue	0.003s
ok  	example.com/ds/stack	0.002s
ok  	example.com/ds/executor	0.004s

十一、错误示例：把队列写成了“能跑但会慢慢涨内存”的版本

先看一个常见的坏版本：

type BadQueue struct {
	items []Task
}

func (q *BadQueue) Push(task Task) {
	q.items = append(q.items, task)
}

func (q *BadQueue) Pop() (Task, bool) {
	if len(q.items) == 0 {
		return Task{}, false
	}
	task := q.items[0]
	q.items = q.items[1:]
	return task, true
}

这个版本的问题不是“完全不能用”，而是长期运行时会出现这些迹象：

处理量已经下来了，内存占用还在高位
队列看起来很短，GC 压力却一直偏高
元素对象较大时，问题更明显

原因是切头部只是移动了切片视图，底层数组仍然可能保留旧元素引用。

实际修正动作通常有三步：

出队时把旧位置显式清空
用 head 表示逻辑起点
在空洞积累到一定程度后做一次压缩

也就是前面 Queue 的实现方式。

十二、一个真实排错型场景：任务执行器的内存为什么不降

假设线上有一个最小任务执行器，症状是：

每小时处理几十万条任务
CPU 正常
单次任务耗时正常
进程 RSS 却一路往上走

第一眼看，很容易先怀疑：

goroutine 泄漏
日志写爆了
某个 map 忘记删

如果把 pprof 拉出来看，发现大头落在任务对象和切片底层数组上，这时排查顺序可以这样走：

看任务队列实现是不是在头部做 q = q[1:]
看出队时有没有清空旧元素
看队列是否存在“逻辑长度很小，但容量很大”的情况
看是否缺少压缩或重建逻辑

修完后通常会看到两类变化：

GC 压力下降
任务洪峰过去后，进程内存能回落

这类问题正好说明：
数据结构不是算法面试题，它直接影响线上进程行为。

十三、数组、链表、栈、队列在真实系统里通常会出现在哪

把视角再拉回工程代码，四种结构常见落点可以这样理解。

1. 数组

固定 worker 槽位
固定长度滑动窗口
固定数量的分片桶
协议头字段

2. 链表

LRU 的访问顺序维护
就绪链、空闲链、超时链
需要稳定元素引用的调度结构
中间节点频繁移动的位置

3. 栈

回滚动作
解析器
DFS
嵌套结构展开

4. 队列

任务分发
消息消费缓冲
worker pool 待处理队列
BFS、逐层扫描、批次处理

如果读到某段代码时，发现它在做下面这些动作：

先来的先处理
后做的先撤销
固定槽位直接按编号找
节点位置频繁前后移动

那大概率已经进入这些结构的使用边界了。

十四、什么时候该用，什么时候不要硬套

这一节比“会实现”更重要。

1. 数组

适合：

大小固定
数据布局明确
下标访问频繁

不适合：

长度动态变化
需要频繁传参和切分
更适合切片接口的业务集合

2. 链表

适合：

已知节点位置后要频繁增删
需要稳定节点句柄
LRU、空闲链、重试链这类链式结构

不适合：

大量随机访问
只需要简单遍历和追加
代码越简单越好的普通业务集合

3. 栈

适合：

回滚
递归改迭代
嵌套结构解析

不适合：

需要 FIFO
需要按任意位置删除

4. 队列

适合：

任务按到达顺序处理
批量消费
调度和缓冲

不适合：

需要按优先级排序
需要频繁按条件删除中间元素

如果已经进入优先级调度、延迟任务或定时任务场景，后面通常会继续碰到：

堆
时间轮
优先级队列

也就是这条线往后的下一批文章主题。

十五、写这些结构时常见的失控点

再把容易翻车的位置集中列一下。

1. 数组失控点

把数组当切片用，结果到处碰到类型不匹配
传参时没意识到是值拷贝
固定长度需求不明确，后面被迫改成切片

2. 链表失控点

头尾指针没同步更新
长度字段没同步维护
节点复用时留下脏 Next
想随机访问，却选了链表

3. 栈失控点

Pop 不缩容
空栈处理缺失
并发访问没保护

4. 队列失控点

切片头删但不清理引用
长期运行后容量与长度脱节
并发场景直接复用单线程实现
队列语义和优先级语义混在一起

十六、一个实际练习

可以按下面这个顺序练一次，不要只抄代码。

练习 1：固定 worker 表

目标：

用 [4]WorkerSlot 实现固定槽位
支持 Assign 和 Release

验证点：

分配满 4 个槽位后，第 5 个任务返回失败
释放后可以重新分配

练习 2：单链表重试队列

目标：

实现 PushBack
实现 PopFront
维护 len

验证点：

空链表弹出返回 false
最后一个节点弹出后 head/tail 都回到 nil

练习 3：回滚栈

目标：

执行 prepare -> write -> start
在 start 失败时按逆序输出回滚动作

验证点：

输出顺序必须是 start -> write -> prepare

练习 4：带压缩逻辑的队列

目标：

用 head 实现 FIFO
空洞达到阈值时压缩底层切片

验证点：

连续入队 1000 次、出队 900 次后，Len() 正确
压缩后 head 回到 0

十七、结语

数组、链表、栈、队列这四种结构，真正难的地方从来不是定义，而是知道什么业务约束该落到什么结构上。

把这一篇压成一句话，就是：

固定长度，看数组
头尾链式增删，看链表
逆序撤销，看栈
顺序处理，看队列

再往下一层看，这些结构的价值不是“面试能答出来”，而是：

代码复杂度会不会失控
性能和内存行为是不是可预期
出问题时排查路径是不是清楚

如果这一篇读完后，已经能把最小数组、单链表、切片栈、带 head 的队列写出来，并且知道它们分别在哪些位置合适，Go 里数据结构这条线就算真正起步了。

后面继续补这条线，最自然的方向就是：

堆和优先级队列
哈希与去重结构
树与索引结构
图、搜索、遍历和依赖关系建模

也就是从“基础容器”继续走向“调度、缓存、索引和搜索”这些更接近真实工程的问题。

一、先把四种结构的角色讲清楚

1. 数组

2. 链表

3. 栈

4. 队列

二、先给一个最小示例，看它们长什么样

三、数组在 Go 里怎么理解

1. 数组的最小工程示例

2. 为什么数组在 Go 里不常直接当作“动态集合”

3. 数组最容易写错的地方：传参复制

4. 数组与切片的关系

四、链表在 Go 里怎么自己实现

1. 链表为什么不是默认首选

2. 链表在哪些地方更合适

3. 链表最容易写错的地方

五、栈在 Go 里怎么实现

1. 为什么栈在工程里很常见

2. 栈的错误示例

六、队列在 Go 里怎么实现

1. 为什么不直接写 q.items = q.items[1:]

2. 队列在哪些地方最常见

3. 队列最容易写错的地方

七、时间复杂度先放到一张表里

八、一个更接近真实项目的小场景：最小任务执行器

1. 先定义任务和执行器

2. 这里四种结构分别承担什么角色

九、先看一个运行示例

十、怎么测试这几种结构

1. 测数组相关行为

2. 测链表头尾边界

3. 测栈的 LIFO

4. 测队列的 FIFO 与长度

5. 测完整任务执行器

6. 实际执行命令

十一、错误示例：把队列写成了“能跑但会慢慢涨内存”的版本

十二、一个真实排错型场景：任务执行器的内存为什么不降

十三、数组、链表、栈、队列在真实系统里通常会出现在哪

1. 数组

2. 链表

3. 栈

4. 队列

十四、什么时候该用，什么时候不要硬套

1. 数组

2. 链表

3. 栈

4. 队列

十五、写这些结构时常见的失控点

1. 数组失控点

2. 链表失控点

3. 栈失控点

4. 队列失控点

十六、一个实际练习

练习 1：固定 worker 表

练习 2：单链表重试队列

练习 3：回滚栈

练习 4：带压缩逻辑的队列

十七、结语

1. 为什么不直接写 `q.items = q.items[1:]`