开发者LT的博客
0%

数据结构 —— 栈

发表于 分类于
本文字数： 4k 阅读时长 ≈ 4 分钟
顺序栈和链式栈的C++实现

什么是栈

栈是只允许在一端插入和删除的线性表，特点是先进后出，后进先出。

允许操作的那一端叫栈顶，另一端叫栈底。元素只能从栈顶进、从栈顶出，想拿栈底的元素，必须先把上面的都弹走。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
        栈顶
         ↓
┌──────────────┐
│      5       │ ← 最后入栈，最先出栈
├──────────────┤
│      4       │
├──────────────┤
│      3       │
├──────────────┤
│      2       │
├──────────────┤
│      1       │ ← 最先入栈，最后出栈
└──────────────┘
        栈底

基本操作：

操作 说明
入栈 push 把元素放到栈顶
出栈 pop 把栈顶元素拿走
取栈顶 top 看一眼栈顶元素，不拿走

栈可以用数组实现（顺序栈），也可以用链表实现（链式栈）。

一、顺序栈

1.1 结构定义、构造和析构

SeqStack/main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class SeqStack
{
public:
	SeqStack(int size = 10) : mtop(0), mcap(size)
	{
		mpStack = new int[mcap];
	}
	~SeqStack()
	{
		delete[]mpStack;
		mpStack = nullptr;
	}
	// ...
private:
	int* mpStack;	// 栈的指针
	int mtop;		// 栈顶
	int mcap;		// 栈的容量
};

三个成员：

  • mpStack 指向堆上申请的数组
  • mcap 是这块数组的总容量
  • mtop 是当前元素个数

mtop 有两个身份，它既是”元素个数”，也是”下一个可写入位置的下标“。因为数组下标从 0 开始，存了 3 个元素时，下一个该写的位置正好是下标 3。

1
2
3
4
5
6
7
mpStack:  ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
          │ 10 │ 11 │ 12 │    │    │    │    │    │    │    │
          └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
            [0]  [1]  [2]  [3]  ...
                          ↑
                    mtop = 3（下一个写入位置）
                    栈顶元素是 mpStack[mtop-1] = mpStack[2] = 12

1.2 入栈

SeqStack/main.cpp - Push
1
2
3
4
5
6
7
8
void Push(int val)
{
	if (mtop == mcap)		// 如果满了，先扩容
	{
		expand(2 * mcap);
	}
	mpStack[mtop++] = val;	// 写入 + 栈顶上移
}

mpStack[mtop++] = val 是两步：先把 val 写到下标 mtop 处，再把 mtop 加一。写完之后 mtop 又指向了新的空位。

mtop == mcap 是栈满的判断。容量为 10 时下标范围是 0~9，mtop 涨到 10 就说明 10 个位置全占满了。

1.3 扩容

SeqStack/main.cpp - expand
1
2
3
4
5
6
7
8
void expand(int size)
{
	int* p = new int[size];					// ① 申请新数组
	memcpy(p, mpStack, mtop * sizeof(int));	// ② 拷贝旧数据
	delete[]mpStack;						// ③ 释放旧数组
	mpStack = p;							// ④ 指针更新，指向新数组
	mcap = size;							// ⑤ 更新容量
}

申请 → 拷贝 → 释放 → 换指针 → 改容量，顺序不能乱。

拷贝长度是 mtop * sizeof(int) 而不是 mcap * sizeof(int)。只有前 mtop 个位置是有效数据，后面的空位不用拷。

1.4 出栈与取栈顶

SeqStack/main.cpp - Pop / Top
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Pop()
{
	if (mtop == 0)
	{
		throw "Stack is empty";
	}
	mtop--;				// 栈顶下移一格 = 出栈
}

int Top() const
{
	if (mtop == 0)
	{
		throw "Stack is empty";
	}
	return mpStack[mtop - 1];
}

mtop--没有真的删除数据，因为 mtop 就是有效元素的边界，下标大于等于 mtop 的内存不会被访问到。出栈是 O(1)，不需要移动任何元素。

1.5 获取元素个数、判断是否为空、打印元素

SeqStack/main.cpp - 其他
1
2
3
4
5
6
7
8
9
10
11
int Size() { return mtop; }
bool Empty() { return mtop == 0; }

void Show()
{
	for (int i = 0; i < mtop; i++)	// 只打印有效元素
	{
		cout << mpStack[i] << " ";
	}
	cout << endl;
}

二、链式栈

2.1 结构定义、构造和析构

LinkStack/main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class LinkStack
{
public:
	LinkStack() : size_(0)
	{
		head_ = new Node();		// 哨兵头节点
	}
	~LinkStack()           //析构函数
	{
		Node* p = head_;
		while (p != nullptr)
		{
			head_ = head_->next;
			delete p;
			p = head_;
		}
	}
private:
	struct Node
	{
		Node(int data = 0) : data_(data), next(nullptr) {}
		int data_;
		Node* next;
	};
	Node* head_;	// 头节点（哨兵）
	int size_;		// 元素个数
};

链式栈就是带头节点的单链表，只不过所有操作都限制在一端。

链式栈的栈顶不在数组末尾，而是 head_->next。

1
2
3
4
5
6
7
8
head_（哨兵）
  │
  ▼
┌──────┐    ┌──────┐    ┌──────┐    ┌──────┐
│ next │──→ │  19  │──→ │  18  │──→ │  17  │──→ nullptr
└──────┘    └──────┘    └──────┘    └──────┘
    ↑
 栈顶（最后入栈的）

2.2 入栈

LinkStack/main.cpp - push
1
2
3
4
5
6
7
void push(int val)
{
	Node* p = new Node(val);
	p->next = head_->next;	// ① 新节点接上原栈顶
	head_->next = p;		// ② 头节点指向新节点
	size_++;
}

入栈就是头插法，先让新节点接上原链，再让头节点改指向新节点。

头插之后，新节点成了第一个有效节点，也就是新的栈顶。

2.3 出栈与取栈顶

LinkStack/main.cpp - pop / top
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void pop()
{
	if (head_->next == nullptr)		// 判断是否为空栈
	{
		throw "stack is empty";
	}
	Node* p = head_->next;		// 备份栈顶节点
	head_->next = p->next;		// 头节点跳过它
	delete p;					// 释放
	size_--;
}

int top() const
{
	if (head_->next == nullptr)
	{
		throw "stack is empty";
	}
	return head_->next->data_;
}

2.4 遍历

LinkStack/main.cpp - main
1
2
3
4
5
6
7
8
9
10
11
LinkStack s;
for (int i = 0; i < 10; i++)
{
	s.push(i + 10);
}
while (!s.empty())
{
	cout << s.top() << " ";
	s.pop();
}
cout << endl;

输出是 19 18 17 16 15 14 13 12 11 10，正好是入栈顺序的倒序。

三、两种实现对比

顺序栈 链式栈
底层结构 动态数组 带头节点的单链表
栈顶在哪 mpStack[mtop-1] head_->next
入栈 尾部写入，满则扩容 头插
出栈 mtop-- 删第一个节点
时间复杂度 入栈均摊 O(1)，扩容那次 O(n) 严格 O(1)
额外开销 有预留空间（容量 ≥ 元素数） 每个节点多一个 next 指针
内存布局 连续，缓存友好 离散
容量上限 受连续内存大小限制 有内存就能继续加

元素数量可预估、追求速度，选顺序栈。数组连续存储对 CPU 缓存友好，实际跑起来往往更快。

元素数量浮动大、不想浪费空间，选链式栈。不用扩容，用多少申请多少。

四、常见问题

  1. 栈的特点是什么？ 后进先出（LIFO），只允许在栈顶一端插入和删除。
  2. 顺序栈和链式栈怎么选？ 数量可预估、要速度选顺序栈；数量浮动大、不想预留空间选链式栈。
  3. 顺序栈为什么按 2 倍扩容？ 均摊下来每次入栈是 O(1)。每次扩固定大小会让整体退化到 O(n²)。
  4. 链式栈为什么用头插？ 头插 O(1)，且头节点的 next 天然就是栈顶，不用额外维护尾指针。
  5. 出栈为什么不真的删数据？ mtop 就是有效元素的边界，越界部分不会被访问，清理是多余操作。
  6. 栈有什么实际应用？ 函数调用栈、括号匹配、表达式求值（中缀转后缀）、深度优先搜索、编辑器的撤销功能。