【C语言 数据结构】栈 - 顺序栈

---

---

栈

一、栈的表示和实现

1.1 栈的概念

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端（表尾）被称为栈顶，相对地，把另一端称为栈底。

向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。栈又称为后进先出表（LIFO）

主要接口：

#pragma one

#include 
#include 
#include 
#include 

// 自定义数据类型
typedef int StackDataType;
// 定义栈结构体
typedef struct Stack {
	StackDataType* a; // 指向动态开辟的数组
	int top; // 栈顶
	int capacity;  // 栈的容量
} ST;

// 初始化栈
void StackInit(ST* ps);

// 销毁栈
void StackDestory(ST* ps);

// 入栈
void StackPush(ST* ps,StackDataType x);

// 出栈
void StackPop(ST* ps);

// 返回栈顶元素
StackDataType StackTop(ST* ps);

// 栈的大小
int StackSize(ST* ps);

// 判断空栈
bool StackEmpty(ST* ps);

// 栈的打印
void StackPrint(ST* ps);
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

返回顶部

---

1.2 栈的初始化

创建一个新的空元素栈，栈顶指向下标0，此后指向栈顶数据的下一个；初始容量赋为0。

// 初始化栈
void StackInit(ST* ps) {
	// 断言
	assert(ps);
	// 初始化栈
	ps->a = NULL; 
	ps->top = 0; // 指向栈顶数据的下一个
	ps->capacity = 0;
}
1
2
3
4
5
6
7
8
9

返回顶部

---

1.3 栈的销毁

将栈的内存地址释放并置空，将栈顶归零，栈的容量大小置零。

// 销毁栈
void StackDestory(ST* ps) {
	// 断言
	assert(ps);
	// 释放
	free(ps->a);
	// 置空
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

1
2
3
4
5
6
7
8
9
10
11

返回顶部

---

1.4 栈的扩容

如果栈顶指向与栈的空间大小相等（同为0，初始分配4个大小空间；同不为0，栈满，扩容）

// 扩容
if (ps->top == ps->capacity) {
    // 定义新的空间大小
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    // 重新开辟内存
    StackDataType* tmp = realloc(ps->a, sizeof(StackDataType) * newCapacity);
    if (tmp == NULL) {
        printf("开辟空间失败！");
        exit(-1);
    }
    // 开辟成功
    ps->a = tmp;
    ps->capacity = newCapacity;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

返回顶部

---

1.5 元素入栈

入栈，首先判断栈满（空栈），进行扩容（初始分配空间）操作。接着，将元素从top位置进行插入，并将 top++。

// 入栈
void StackPush(ST* ps, StackDataType x) {
	// 断言
	assert(ps);
	// 扩容
	if (ps->top == ps->capacity) {
		// 定义新的空间大小
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		// 重新开辟内存
		StackDataType* tmp = realloc(ps->a, sizeof(StackDataType) * newCapacity);
		if (tmp == NULL) {
			printf("开辟空间失败！");
			exit(-1);
		}
		// 开辟成功
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	// 栈顶添加新的元素
	ps->a[ps->top] = x;
	ps->top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

返回顶部

---

1.6 元素出栈

出栈，需要进行判空操作，否则一直出栈会发生下标越界（C语言中不报错，通过断言终止程序）。top--实现了栈的上界阻断，以达到元素出栈的目的。

// 出栈
void StackPop(ST* ps) {
	// 断言
	assert(ps);
	// 不为空
	assert(!StackEmpty(ps));
	// 栈顶下移一位
	ps->top--;
}
1
2
3
4
5
6
7
8
9

返回顶部

---

1.7 返回栈顶元素

这里我们考虑 top = 0 ，所以top每次添加完元素后，指向的是下一个栈元素的位置，所以输出栈顶元素的时候需要将其减1。

// 返回栈顶元素
StackDataType StackTop(ST* ps) {
	// 断言
	assert(ps);
	// 不为空
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}
1
2
3
4
5
6
7
8

返回顶部

---

1.8 返回栈的元素个数

同理，top从0开始，元素的个数即为top的值大小。

// 栈的大小
int StackSize(ST* ps) {
	// 断言
	assert(ps);
	return ps->top;
}
1
2
3
4
5
6

返回顶部

---

1.9 栈的判空与清空

同理，栈元素的个数为0，即为空栈。

// 判断空栈
bool StackEmpty(ST* ps) {
	assert(ps);
	return ps->top == 0;
}
1
2
3
4
5

// 清空栈
void StackClear(ST* ps) {
	assert(ps);
	// if (ps->top == 0) printf("原本就是空栈！");
	while (ps->top!=0) {
		ps->top--;
	}
	if (ps->top == 0) printf("\n栈已被清空\n");
}
1
2
3
4
5
6
7
8
9

返回顶部

---

1.10 栈的打印输出

因为栈是先进后出表，所以必须将元素从栈顶依次取出，才能获取下面的元素，所以需要结合出栈、获取栈顶元素函数实现栈的打印输出。

// 栈的打印
void StackPrint(ST* ps) {
	assert(ps);
	// 当栈不为空
	while (!StackEmpty(ps)) {
		// 输出栈顶元素
		printf("%d",StackTop(ps));
		// 栈顶元素出栈
		StackPop(ps);
	}
	printf("\n");
	// 销毁栈
	StackDestory(ps);
}

void TestStack() {
    // 创建栈
	ST stack;
    // 初始化查娜
	StackInit(&stack);
    // 元素入栈
	StackPush(&stack, 1);
	StackPush(&stack, 2);
	StackPush(&stack, 3);
	StackPush(&stack, 4);
	StackPush(&stack, 5);
	// 打印输出栈
	StackPrint(&stack);
}

int main() {
	// 测试
	TestStack();
	system("pause");
	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
32
33
34
35
36

返回顶部

---

二、栈的应用

2.1 数制转换

十进制数 $N$ 和其他 $d$ 进制数的转换时计算机实现计算的基本问题，其解决方案很多，其中一个简单算法如下：
$$N=(Ndivd)\times d+Nmodd$$
$div$ 为整除运算， $mod$ 为求余运算

例如：$(1348{)}_{10}=(2504{)}_8$

分析：对于任意的一个非负十进制整数，打印输出与其相等的8进制数。按照上述的计算过程，从低位到高位依次产生，最后逆序输出。其过程与栈的存取十分相似，满足先进后出的条件。

// 进制问题
void Conversion(ST* ps, int N) {
	// 初始化栈
	StackInit(ps);
	// 求余入栈
	while (N > 0) {
		StackPush(ps, N % 8);
		N = N / 8;
	}
	// 输出出栈
	while (!StackEmpty(ps)) {
		printf("%d", StackTop(ps));
		StackPop(ps);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

返回顶部

---

2.2 括号匹配检验

{ [ ( ) ] } 、 [ ] { } ( ) 、 { [ ] ( ) 、 ( { ] } ) \{ [ ( ) ] \}、[]\{ \}()、\{ []()、(\{ ] \}) {[()]}、[]{}()、{[]()、({]})

括号匹配的思想：

• 依次从左至右检查字符串，若为左括号，则入栈；

• 若遇右括号则获取栈顶元素，检查栈顶元素与当前元素是否匹配，

  • 若匹配，则栈顶元素出栈。

  • 反之，则不匹配，程序结束。

以此类推，直至检查完所有字符串。如果此时栈空则匹配，反之则不匹配。

// 自定义数据类型
typedef char StackDataType;
// 定义栈结构体
typedef struct Stack {
	StackDataType* a; // 指向动态开辟的数组
	int top; // 栈顶
	int capacity;  // 栈的容量
} ST;

// 括号匹配问题
void Match(ST* ps, char str[]) {
	// 初始化栈
	StackInit(ps);
	// 初始化变量存储、计数
	char ch;
	int i;
	for (i = 0; str[i] != '\0'; i++) {
		switch (str[i]) {
		case '{':
		case '[':
		case '(':
			StackPush(ps, str[i]);
			break;
		case '}':
		case ']':
		case ')':
			// 如果栈为空
			if (StackEmpty(ps)) {
				return 0;
			}
			else {
				// 获取栈顶元素
				char top = StackTop(ps);
				// 比较栈顶元素与当前的括号是否匹配 
				if (top + 1 == str[i] || top + 2 == str[i]) {
					StackPop(ps);
				} else {
					return 0;
				}
			}
		}
	}
	// 如果最后栈为空，则整体是匹配的
	if (StackEmpty(ps)) {
		printf("该字串符合条件！");
	} else {
		printf("该字串不符合条件！");
	}
    StackDestory(ps);
}
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

解析：if (top + 1 == str[i] || top + 2 == str[i]) {...} ，通过如下的Ascall码字符匹配表可以看到，[ ] 、{ }之间相差为2，（ ） 之间相差为1。

返回顶部

---

2.3 行编辑程序

一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。

由于用户在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。

较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。

例如，当用户发现刚刚键入的一个字符是错的时，可补进一个退格符“#”，以表示前一个字符无效；如果发现当前键入的行内差错较多或难以补救，则可以键入一个退行符“@”，以表示当前行中的字符均无效。

// 栈的打印
void StackPrint(ST* ps) {
	assert(ps);
	// 当栈不为空
	while (!StackEmpty(ps)) {
		// 输出栈顶元素
		printf("%c", StackTop(ps));
		// 栈顶元素出栈
		StackPop(ps);
	}
	printf("\n");
}

// 行编辑程序
void LineEdit(ST* ps) {
	// 初始化栈
	StackInit(ps);
	char ch = getchar();
	// EOF为全文结束符
	while (ch != EOF) {
		while (ch != EOF && ch != '\n') {
			switch (ch) {
				case '#':
					StackPop(ps);  // 栈顶元素出栈
					break;
				case '@':
					StackClear(ps); // 清空栈
					break;
				default:
					StackPush(ps, ch); // 元素入栈
					break;
			}
			ch = getchar();
		}
		StackPrint(ps);
		// 数据传输，清空栈
		StackClear(ps);
		if (ch != EOF) { ch = getchar(); }
	}
	// 销毁栈
	StackDestory(ps);
}
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

返回顶部

---

2.4 表达式求值

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include

#define N 1000+10           // 字符串长度
#define STACK_INIT_SIZE 100 // 栈初始化大小
#define STACKINCREMENT 10   // 扩容大小
#define OK 1                // 状态码
#define OVERFLOW 0
#define ERROR 0

char str[N];            // 输入的字符串表达式
typedef int Status;    // 自定义状态码类型
// 定义算符优先关系字符二维数组
unsigned char prior[7][7] = {
    {'>','>','<','<','<','>','>'},
    {'>','>','<','<','<','>','>'},
    {'>','>','>','>','<','>','>'},
    {'>','>','>','>','<','>','>'},
    {'<','<','<','<','<','=',' '},
    {'<','<','<','<','<',' ','>'},
    {'<','<','<','<','<',' ','='} 
};
// 定义算符数组
char OPSET[7] = { '+','-','*','/','(',')','#' };

typedef  int SElemType; // 自定义栈数据类型
typedef struct {        // 定义栈
	SElemType* base;    // 栈尾
	SElemType* top;     // 栈顶
	int stacksize;      // 栈的大小
}SqStack;

// 初始化栈
Status InitStack(SqStack* s) {
	s->base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType)); // 开辟空间
	if (!s->base) exit(OVERFLOW);
	s->top = s->base;
	s->stacksize = STACK_INIT_SIZE;
	return OK;
}
 
// 入栈 
Status Push(SqStack* s, SElemType c){
	// 扩容
	if ((s->top - s->base) >= s->stacksize){
		s->base = (SElemType*)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(SElemType));
        // 扩容失败
		if (!s->base) exit(OVERFLOW);
		// 扩容成功
        s->stacksize += STACKINCREMENT;
	}
	// 赋值
	*(s->top)++ = c;
	return OK;
}

// 取栈顶元素 
Status GetTop(SqStack* s){
	SElemType e;
	if (s->base == s->top)
		return ERROR;
	e = *(s->top - 1);  // 获取栈顶元素
	return e;
}

// 出栈 脱括号函数 
Status Pop(SqStack* s){
	int e;
	if (s->base == s->top) return ERROR;
	e = *--(s->top);
	return e;
}

// 判断是否为运算符 3*(7-2) { '+','-','*','/','(',')','#' }
Status In(char c, char str[]){
	
	int i = 0;
    // 遍历字符串，
	while (c != str[i]){
		i++;
	}
    // 如果是运算符,最终i最大为6
	if (i < 7) return OK; // 1
	return ERROR; // 0
}
// 字符串连接函数，把字符串str2连接到str1后 
void  Strcat(char* str1, char* str2){
	int i = 0, j = 0;
	while (str1[i] != '\0'){
		i++;
	}
	// str2追加到str1后面
	while (str2[j] != '\0'){
		str1[i++] = str2[j++];
	}
	// 添加结束标志
	str1[i] = '\0';
}
// 把字符串转为数字 
Status Atoi(char* c){
	int data = 0, d = 0;
	int i = 0;
	while (c[i] != '\0'){
		data = data * 10 + c[i] - '0';
		i++;
	}
	return data;
}
// 判断优先级函数 
Status precede(int a, char b){
	int i = 0, j = 0;
	while (OPSET[i] != a){
		i++;
	}
	while (OPSET[j] != b){
		j++;
	}
	return prior[i][j];
}
// 运算函数 
Status Operate(int a, int b, int c){
	switch (b){
		case '+':
			return a + c;
		case '-':
			return a - c;
		case '*':
			return a * c;
		case '/':
			return a / c;
	}
}
// 表达式求值 - 算术表达式求值的算符优先算法
int EvaluateExpression(char* MyExpression) {

	// 设 OPTR 和 OPND 分别为 运算符栈 和 运算数栈
	SqStack OPTR;//运算符栈，字符元素 
	SqStack OPND;//运算数栈，实数元素 
	// 初始化栈
	InitStack(&OPTR);
	Push(&OPTR, '#');
	InitStack(&OPND);

    char* c, Dr[2];
	c = MyExpression;  // 输入的字符表达式：3*(7-2)
    char TempData[20];
	TempData[0] = '\0';
    int data, a, b, theta;
    
	while (*c != '#' || GetTop(&OPTR) != '#'){
		// 不是运算符则进栈 
		if (!In(*c, OPSET)){
            // 获取字串的一个字符
			Dr[0] = *c; // 3
			Dr[1] = '\0';
			Strcat(TempData, Dr);
			c++;
			// 是运算符时 
			if (In(*c, OPSET)){
				data = Atoi(TempData);
				Push(&OPND, data);
				TempData[0] = '\0';
			}
		} else {
            // 将运算符栈顶元素与输入表达式中的运算符比较优先级
			switch (precede(GetTop(&OPTR), *c)){
			case '<':
				Push(&OPTR, *c);
				c++;
				break;
			case '=':
				Pop(&OPTR);
				c++;
				break;
			case '>':
				a = Pop(&OPND);
				b = Pop(&OPND);
				theta = Pop(&OPTR);
				Push(&OPND, Operate(b, theta, a));
				break;
			}
		}
	}
	return GetTop(&OPND);
}
int main(){
	while (scanf("%s", str) != EOF){
		printf("%d\n", EvaluateExpression(str));
	}
	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
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

返回顶部

---

2.5 汉诺塔

汉诺塔（Tower of Hanoi），又称河内塔。源自印度古老传说的一个游戏，大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

• 若有1个圆盘时，需要移动1次；

• 若有2个圆盘时，需要移动3次；

• 若有3个圆盘时，需要移动7次……

不难看出，汉诺塔步数的数学规律为 $2^n-1$（n为柱子上的圆盘个数）。

所以若有64个圆盘那将会移动2^64-1次（即：18,446,744,073,709,551,615‬次），若每次移动需要1s时间，则需要将近5849亿年的时间才能够做到。

假设：现有三个柱子A、B、C，其中有n个圆盘在A柱上，最终要实现把这n个圆盘从A柱借助B柱移动到C柱上。实现实现思路：先将n-1个圆盘从A柱移动到B柱上，然后将A柱上最后一个圆盘n移动到C柱上，最后再把B柱上的n-2个圆盘移动到A柱上，再将B柱上的最后一个圆盘n-1移动到C柱上，如此往复。如下图所示：

#define _CRT_SECURE_NO_WARNINGS
#include

void move(char A, char C, int n) {
	printf("把第%d个圆盘从%c--->%c\n", n, A, C);
}

void HanoiTower(char from, char tmp, char to, int n) {
	if (n == 1){
		move(from, to, n);
	} else {
		// 将n-1个圆盘从A柱借助于C柱移动到B柱上
		HanoiTower(from, to, tmp, n - 1);
		// 将A柱子最后一个圆盘移动到C柱上
		move(from, to, n);
		// 将n-1个圆盘从B柱借助于A柱移动到C柱上
		HanoiTower(tmp, from, to, n - 1);
	}
}

int main() {
	int n = 0;
	printf("输入A柱子上的圆盘个数：");
	scanf("%d", &n);
	// 将n个圆盘从A柱借助于B柱移动到C柱上
	HanoiTower('A', 'B', 'C', 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

返回顶部

---