栈(简单介绍及其应用)_栈的特点是什么,列举一个例子

栈的定义

栈是一种只能在一端进行插入或者删除操作的线性表。表中允许插入，删除操作的一端叫做栈顶，另一端叫栈底。
但栈没有数据元素时称为空栈，插入数据操作为进栈或入栈，删除数据操作为出栈或退栈。
栈的特点为后进先出，栈也成为后进先出表。如存入一组数据，顺序为1， 2， 3， 4，则出栈时顺序为4， 3， 2， 1 。

顺序栈

顺序栈采用顺序存储结构进行存储，分配一块连续的存储空间来存放栈中元素，并用一个变量(如int类型的top)指向当前的栈顶元素。

代码实现：

• 声明顺序栈的类型SqStack(最大个数不超过MaxSize):

typedef struct{
	int data[MaxSize];
	int top;
}SqStack;
1
2
3
4

• 初始化栈 //这时可以把top值赋值为-1，表示此栈为空

void InitStack(SqStack*& s) {
	s = (SqStack*)malloc(sizeof(SqStack));  //分配空间，首地址放在s中
	s->top = -1;							//栈顶指针为-1；
}
1
2
3
4

• 销毁栈（释放顺序栈占用的空间）

void DestroyStack(SqStack* &s) {
	free(s);
}
1
2
3

• 进栈

bool Push(SqStack*& s, int e) {
	if (s->top == MaxSize - 1) return false;	//判断是否栈满
	s->top++;
	s->data[s->top] = e;
	return true;
}
1
2
3
4
5
6

• 出栈

bool Pop(SqStack*& s, int e) {
	if (s->top == -1) return false;		//栈为空
	e = s->data[s->top];				//取出栈顶元素
	s->top--;
	return true;
}
1
2
3
4
5
6

链栈

链栈一般采用带头结点的单链来实现，相比顺序栈，链栈的优点就是不存在栈满溢出的问题。
在进行插入和删除操作时，采用头插法进行插入，删除即删除首结点，在更换头结点的下一个结点。

代码如下：

• 声明：

typedef struct node {
	int e;
	node* next;
};
1
2
3
4

• 初始化

void InitStack(node* &s) {
	s = (node*)malloc(sizeof(node));	//栈顶指针为-1；
	s->next = NULL;						//栈空
}
1
2
3
4

• 销毁栈

void DestroyStack(node* &s) {
	node* pre = s, * p = s->next;		//pre为头结点， p为首结点
	while (p != NULL) {
		free(p);
		pre = p;						//更换头结点的位置，仍用pre指向头结点
		p = pre->next;					//p指向后一个结点，仍用p指向首结点
	}
	free(pre);
}
1
2
3
4
5
6
7
8
9

• 进栈

void Push(node*& s, int e) {
	node* p = (node*)malloc(sizeof(node));
	p->e = e;								//存入数据
	p->next = s->next;						//让p连接后面的数据结点
	s->next = p;							//p成为新的首结点
}

1
2
3
4
5
6
7

• 出栈

bool Pop(node*& s, int e) {
	node* p = s->next;						//p为首结点
	if (p == NULL) return false;			//栈空
	e = p->e;								//取值
	s->next = p->next;						//删除首结点
	free(p);								//释放被删除结点的储存空间
	return true;
}
1
2
3
4
5
6
7
8

栈的简单运用

输入包含±*/四种运算，（含有()括号的合法算术表达式，且操作数为多位整数，并计算其值，表达式以#开始，并以#结束）。

1. 创建两个栈，一个运算符栈来存储运算符，一个数字栈来存储数字。

2. 对一个输入的式子进行遍历，例如给一个字符数组str[100]赋值为 #(4+3)*12#

3. 对str遍历
   （1）第一为#存入运算符栈；
   （2）遍历第二为‘（’，根据符号优先级，‘（’比‘#’优先级高，应该压入运算符栈；
   （3）再第三次遍历为数字4，压入数字栈，并再压入一个‘|’来隔开下一位数字；
   （4）第四次为‘+’，根据符号优先级，应该入运算符栈；
   （5）第五压入数字3进数字栈，压入分隔符’|’；
   （6）第六为‘）’，根据优先级比‘+’低，不应该入栈【判断是否运算符栈顶为‘（’，若是，把‘（’弹出，并遍历下一位str数组元素】，并且需要在数字栈中弹出两个数字进行运算【取出数字时，是一个顺序颠倒的字符数组，需要进行转化，如若取出为“|21”需转化为数字12】，在将运算结果压入数据栈，在压入一个分隔符’|‘；
   （7）第七为元素为‘ * ’，比栈顶’#‘优先级高，入栈；
   （8）第八为数字12，入栈，此时栈内数据为 |21|7
   （9）最后是#，优先级最低，在数字栈弹出两个数字，运算符栈弹出*，进行计算，压入计算结果和分隔符；

4. 将数字栈中的结果弹出，得到的是字符数组 |48，转化为int类型84；【转化方法如下代码】

5. 了解运算符的优先级，参考下面代码的Panduan（）函数；

   可将数字栈的数据元素类型改为int类型，这样就无需进行字符数组反转再转化。也正由于栈的后进先出的特点，才需要对此问题进行处理。

参考代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
const int MaxSize = 100;

typedef struct linknode {
	char data[MaxSize];
	int top;
};

void InitStack(linknode* &s) {
	s = (linknode*)malloc(sizeof(linknode));
	s->top = -1;
}

bool Push(linknode* &s, char e) {
	if (s->top == MaxSize-1) {
		return false;
	}
	s->top++;
	s->data[s->top] = e;
	return true;
}

bool Pop(linknode*& s, char &a) {
	if (s->top == -1) {
		return false;
	}
	a = s->data[s->top];
	s->top--;
	return true;
}

char GetTop(linknode* s) {
	return s->data[s->top];
}

int PanDuan(char a, char b) { //-1表示a小于b  1表示a大于b  0表示相等
	if (a == '+') {
		if (b == '#' || b == '+' || b == '-' || b == '(') return 1;  
		else if (b == '/' || b == '*' || b == ')') return -1;
	}
	if (a == '-') {
		if (b == '#' || b == '-' || b == '+' || b == '(') return 1;
		else if (b == '/' || b == '*' || b == ')') return -1;
	}
	if (a == '*') {
		if (b == '+' || b == '-' || b == '*' || b == '/' || b == '(' || b == '#') return 1;
		else if (b == ')') return -1;
	}
	if (a == '/') {
		if (b == '+' || b == '-' || b == '*' || b == '/' || b == '(' || b == '#') return 1;
		else if (b == ')') return -1;
	}
	if (a == '(') {
		/*if (b == '-' || b == '+' || b == '*' || b == '/' || b == ')') return 1;
		else if (b == '(' || b == '#') return 1;*/
		return 1;
	}
	if (a == ')') {
		if (b == '-' || b == '+' || b == '*' || b == '/' || b == '(') return -1;
		else if (b == ')'|| b == '#') return 0;
	}
	if (a == '#') {
		if (b == '-' || b == '+' || b == '*' || b == '/' || b == '(' || b == ')') return -1;
		else if (b == '#') return 0;
	}
}

void rev(char str[], int i) {
	int s = 0, e = i;
	char temp;
	while (s < e) {
		temp = str[s];
		str[s] = str[e];
		str[e] = temp;
		s++;
		e--;
	}
}

int ExpEvaluation(char str[]) {
	int result;  //结果
	char Rch[10] = "";  //结果字符数组
	linknode* dataStack; //数字栈
	linknode* optrStack; //运算符栈
	InitStack(dataStack);
	InitStack(optrStack);
	int index = 0; //字符串索引
	Push(optrStack, str[index]);
	index++;
	while (str[index] != '\0' || GetTop(optrStack) != '#') {
		if ('0' <= str[index] && str[index] <= '9') {      //数字直接进入数字栈
			Push(dataStack, str[index]);
			index++;
			if ('0' <= str[index] && str[index] <= '9') continue;
			else Push(dataStack, '|');  //用|隔开每一个数字
		}
		else {
			if (PanDuan(str[index], GetTop(optrStack)) >= 0) {  // a比栈顶的运算符优先级大
				Push(optrStack, str[index]);
				index++;
			}
			else {
				char ch;
				if (optrStack->data[optrStack->top] == '(') {
					Pop(optrStack, ch);
					index++;
					continue;
				}
				char a[10] = {}, b[10] = {}, op;
				Pop(optrStack, op);
				int a1, b1;
				int flag = 0;
				int i = 0;
				Pop(dataStack, ch);
				while (1) {
					if (GetTop(dataStack) == '|' || dataStack->top == -1) break;
					Pop(dataStack, a[i]);
					i++;
				}
				rev(a, i - 1);
				char str[10]; //将a，b转化为字符串
				sscanf(a, "%s", str, _countof(str));
				sscanf(str, "%d", &a1);  //将a间接转化为数字
				Pop(dataStack, ch);
				i = 0;
				while (1) {
					if (GetTop(dataStack) == '|' || dataStack->top == -1) break;
					Pop(dataStack, b[i]);
					i++;
				}
				rev(b, i - 1);
				sscanf(b, "%s", str, _countof(str));
				sscanf(str, "%d", &b1);  //将b间接转化为数字
				
				i = 0;
				switch (op)
				{
				case '-': result = b1 - a1;
					snprintf(Rch, sizeof(Rch), "%d", result);
					for (int i = 0; i < strlen(Rch); i++) {
						Push(dataStack, Rch[i]);
					}
					Push(dataStack, '|');
					break;
				case '+': result = b1 + a1;
					snprintf(Rch, sizeof(Rch), "%d", result);
					for (int i = 0; i < strlen(Rch); i++) {
						Push(dataStack, Rch[i]);
					}
					Push(dataStack, '|');
					break;
				case '*': result = a1 * b1;
					snprintf(Rch, sizeof(Rch), "%d", result);
					for (int i = 0; i < strlen(Rch); i++) {
						Push(dataStack, Rch[i]);
					}
					Push(dataStack, '|');
					break;
				case '/': result = b1 / a1;
					snprintf(Rch, sizeof(Rch), "%d", result);
					for (int i = 0; i < strlen(Rch); i++) {
						Push(dataStack, Rch[i]);
					}
					Push(dataStack, '|');
					break;
				}
			}
		}
	}
	char dataStackTop; //数字栈栈顶的‘|’
	Pop(dataStack, dataStackTop);  //去掉‘|’
	int i = 0;
	while (dataStack->top != -1) {
		Pop(dataStack, Rch[i]);
		i++;
	}
	rev(Rch,i-1);
	sscanf(Rch, "%d", &result);
	return result;
}

int main() {
	printf("输入包含+-*/四种运算，（表达式以#开始，并以#结束）:\n");
	char str[MaxSize];
	int result = 0;
	scanf_s("%s", str);
	result = ExpEvaluation(str);
	printf("\n结果为：%d", result);
}
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

测试结果：