【数据结构】栈详解

1. 前言

在前面我们一起了解的数据结构有顺序表和链表，这次来介绍栈。
与顺序表和链表相同的是，栈也是常见的数据结构。而与前面两种不同的是，它在农村种的存储，接下来让我们一起来学习一下。

2. 栈

2.1 栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

2.2 如何实现栈

那该如何实现栈呢？
第一种使用数组栈
第二种使用链式栈

链表实现又分为双向链表，和单链表。
双向链表实现，栈顶可以是尾，也可以是头。
单链表实现，栈顶只能是头。

如果只选择一种来实现，那必然是数组，虽然有扩容，但不是频繁扩容。还有另外一个优势，它访问数据，CPU高速缓存命中率比较高，访问第一个，后面都在缓存了。

2.3 数组栈实现

2.3.1 top怎么确定

我们需要考虑top怎么确定？
如果top给0，那么表示的是栈顶还是栈顶位置的下一个？

如果空的时候top给的是0，那么插入一个数据之后top也是0，因为top指向栈顶。
此时就出现了歧义。top==0是一个元素还是空？区分不开。

那该怎么区分呢？
第一种如果top指向栈顶元素，那么top初始时给-1。

这种插入数据时：
要先加加top，再在这个位置赋值。

第二种指向栈顶元素的下一个。
此时top初始时就为0。

这种插入数据时：
要先在这个位置赋值，再加加top。

这里插入就取决于怎么初始化栈。

选择第二种来实现代码，这种更简单。

void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;//第二种
}
1
2
3
4
5
6
7
8

2.3.2 栈顶插入

2.3.2.1 栈顶插入分析

插入的代码非常简单：

pst->a[pst->top] = x;
	pst->top++;
1
2

但是在插入之前，要先判断一下栈有没有满，满的化要进行扩容。

if (pst->top == pst->capacity)
1

但我们要初始时候有没有给空间，如果有直接扩两倍，没有就给初始值4。
使用一个三目表达式

int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
1

如果没有开空间，就直接返回或者结束程序。

if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
1
2
3
4
5

2.3.2.2 栈顶插入代码实现

void STPush(ST* pst, STDataType x)
{
	assert(pst);

	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		pst->a = tmp;
		pst->capacity = newcapacity;
	}

	pst->a[pst->top] = x;
	pst->top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.3.3 栈顶删除

删除很简单，直接top–，就行，但减减之前判断一下top是不是0，加一个断言就行。
代码实现：

void STPop(ST* pst)
{
	assert(pst);
	// 不为空
	assert(pst->top > 0);

	pst->top--;
}
1
2
3
4
5
6
7
8

返回栈顶数据的代码:

STDataType STTop(ST* pst)
{
	assert(pst);
	// 不为空
	assert(pst->top > 0);

	return pst->a[pst->top - 1];
}
1
2
3
4
5
6
7
8

2.3.4 判空

2.3.4.1 分析

判空这里得看刚开始时：初始时top为0，就要判断top==0。初始为-1，那么就要判断top==-1。
可以用if来判断：

if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
1
2
3
4
5
6
7
8

但是有个更简单的：bool类型返回就是真假，利用返回值当结果就行，直接返回pst->top == 0。

2.3.4.2 代码实现

代码实现：

bool STEmpty(ST* pst)
{
	assert(pst);

	/*if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/

	return pst->top == 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.3.5 栈的元素个数

如果top是指向栈顶元素的下一个，那么元素个数就是top。
如果top就是指向栈顶，那么元素个数就是top+1。

代码实现：

int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}
1
2
3
4
5
6

2.3.6 栈销毁

直接将元素都free掉，再把它们都置为空。把栈顶和栈空间都置为0。

void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}
1
2
3
4
5
6
7
8

2.3.7 栈访问数据

因为栈是后进先出，所以栈不能随便打印。
那怎么打印呢？
判断栈是否为空，然后从栈顶开始访问。
访问了栈顶元素，要想访问下一个就要先将栈顶元素弹出，直到栈为空，就结束。

代码实现：

while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}
	printf("\n");
1
2
3
4
5
6

3. 源代码

3.1 Stack.h

#pragma once
#include
#include
#include
#include


typedef int STDataType;

typedef struct Stack
{
	int* a;
	int top;		// 标识栈顶位置的
	int capacity;
}ST;

void STInit(ST* pst);
void STDestroy(ST* pst);

// 栈顶插入删除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);

bool STEmpty(ST* pst);
int STSize(ST* pst);

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

3.2 Stack.c

#include"Stack.h"

void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	pst->capacity = 0;

	// 表示top指向栈顶元素的下一个位置
	pst->top = 0;

	// 表示top指向栈顶元素
	//pst->top = -1;
}

void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

// 栈顶插入删除
void STPush(ST* pst, STDataType x)
{
	assert(pst);

	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		pst->a = tmp;
		pst->capacity = newcapacity;
	}

	pst->a[pst->top] = x;
	pst->top++;
}

void STPop(ST* pst)
{
	assert(pst);
	// 不为空
	assert(pst->top > 0);

	pst->top--;
}

STDataType STTop(ST* pst)
{
	assert(pst);
	// 不为空
	assert(pst->top > 0);

	return pst->a[pst->top - 1];
}

bool STEmpty(ST* pst)
{
	assert(pst);

	/*if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/

	return pst->top == 0;
}

int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

3.3 test.c

#include"Stack.h"


int main()
{
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	printf("%d ", STTop(&s));
	STPop(&s);
	printf("%d ", STTop(&s));
	STPop(&s);

	STPush(&s, 4);
	STPush(&s, 5);

	//    一     对     多
	// 入栈顺序  --  出栈顺序
	while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}
	printf("\n");

	return 0;
}


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
28
29
30
31