数据结构06：栈及其简单应用_数据结构 栈的应用

摘要：栈是一种新的数据结构，在我们生活中其实也有很多，只是我们没有关注。栈可以形象为一个死胡同，秉承着“先进后出，后进先出”的原则。栈相较于之前的链表较为简单，但其应用十分广泛。
一.代码块
1）栈的创建

#define MAXSIZE 10

typedef struct charStack
{
	int top;//记录栈顶的位置，方便我们压栈和出栈 
	char data[MAXSIZE];//存储数据的本质还是数组 
}*charStackPtr;
1
2
3
4
5
6
7

2）栈的初始化

charStackPtr stackInit()
{
	charStackPtr resultStack = (charStackPtr)malloc(sizeof(struct charStack));
	
	resultStack->top = -1;//栈顶在-1，表示该栈为空栈
	return resultStack;
}
1
2
3
4
5
6
7

3）栈的打印

void outputStack(charStackPtr paraStack)
{
	int i;
	for(i = 0;i <= paraStack->top;i ++)
	{
		printf("%c ",paraStack->data[i]); 
	}
	
	printf("\r\n");
}
1
2
3
4
5
6
7
8
9
10

4）压栈

void push(charStackPtr paraStack,char paraChar)
{
	if(paraStack->top >= MAXSIZE-1)
	{
		printf("Cannot push element:stack full\r\n");
		return ;
	}
	
	paraStack->top ++;
	paraStack->data[paraStack->top] = paraChar;
}
1
2
3
4
5
6
7
8
9
10
11

5）出栈

char pop(charStackPtr paraStack)
{
	if(paraStack->top < 0)
	{
		printf("Cannot pop element:stack empty");
		return '\0'; /*在不能出栈，我们返回的是‘\0’.相当于空
		注意不是‘0’，这就是返回了字符0了*/
	}
	
	paraStack->top --;
	
	return paraStack->data[(paraStack->top)+1];
	/*我们注意到，压栈和出栈的操作时间复杂度度极低，为o(1),
	这也是栈的一个极大优势*/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

6）压栈出栈测试函数

void pushPopTest() 
{
	char ch;
	int i;
    printf("---- pushPopTest begins. ----\r\n");

    charStackPtr tempStack = stackInit();
    printf("After initialization, the stack is: ");
	outputStack(tempStack);

	for (ch = 'a'; ch < 'm'; ch ++) 
	{
		printf("Pushing %c.\r\n", ch);
		push(tempStack, ch);
		outputStack(tempStack);
	}

	for (i = 0; i < 3; i ++) 
	{
		ch = pop(tempStack);
		printf("Pop %c.\r\n", ch);
		outputStack(tempStack);
	}

    printf("---- pushPopTest ends. ----\r\n");
}
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

7）括号匹配（栈的简单应用）

int bracketMatching(char paraString[],int paraLength)
{
	//不知道为啥我的编译器不支持bool，我就用int代替的，效果一样
	int i;
	char tempChar,tempPopedChar;
	charStackPtr tempStack = stackInit();
	/*这里是个重要的地方，为了统一操作，我们在第栈的第0个位置手动push
	了一个#号，这个#号的作用相当于单链表的头结点，是不能触碰的，如果栈
	里面只剩下了#号说明为空栈，这个操作在我们后续写代码也会常用到*/
	push(tempStack,'#');
	tempStack->top = 0;
	
	/*是这样的，只要我们发现了([{,都将其存入栈中，发现了)]},就将栈顶pop
	出来，并且如果栈顶元素不是对应的左括号，代表括号不匹配，就直接return 0了*/
	for(i = 0;i < paraLength;i ++)
	{
		tempChar = paraString[i];
		
		switch (tempChar)
		{
			case '(':
			case '[':
			case '{':
				push(tempStack,tempChar);
				break;
			case ')':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar != '(')
				{
					return 0;
				}
				break;
			case ']':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar != '[')
				{
					return 0;
				}
				break;
			case '}':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar != '{')
				{
					return 0;
				}
				break;
			default :
				break;	
		}
			
	}
	//如何判断为空栈，直接用到了我们的#号
	tempPopedChar = pop(tempStack);
	if(tempPopedChar != '#')
	{
		return 0;
	}
	
	return 1;
}
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

8）括号匹配测试函数

void bracketMatchingTest() 
{
	char* tempExpression = "[2 + (1 - 3)] * 4";
	int tempMatch = bracketMatching(tempExpression, 17);
	printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);


	tempExpression = "( )  )";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);

	tempExpression = "()()(())";
	tempMatch = bracketMatching(tempExpression, 8);
	printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);

	tempExpression = "({}[])";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);


	tempExpression = "((((";
	tempMatch = bracketMatching(tempExpression, 4);
	printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);
	/*这个测试代码也用到了我们设置的#号，第一个字符就直接return 0,
	十分方便*/
	tempExpression = ")(";
	tempMatch = bracketMatching(tempExpression, 2);
	printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);
}
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

三.全部代码

#include <stdio.h>
#include <malloc.h>

#define MAXSIZE 10

typedef struct charStack
{
	int top;//记录栈顶的位置，方便我们压栈和出栈 
	char data[MAXSIZE];//存储数据的本质还是数组 
}*charStackPtr;

charStackPtr stackInit()
{
	charStackPtr resultStack = (charStackPtr)malloc(sizeof(struct charStack));
	
	resultStack->top = -1;//栈顶在-1，表示该栈为空栈
	return resultStack;
}

void outputStack(charStackPtr paraStack)
{
	int i;
	for(i = 0;i <= paraStack->top;i ++)
	{
		printf("%c ",paraStack->data[i]); 
	}
	
	printf("\r\n");
}

void push(charStackPtr paraStack,char paraChar)
{
	if(paraStack->top >= MAXSIZE-1)
	{
		printf("Cannot push element:stack full\r\n");
		return ;
	}
	
	paraStack->top ++;
	paraStack->data[paraStack->top] = paraChar;
}

char pop(charStackPtr paraStack)
{
	if(paraStack->top < 0)
	{
		printf("Cannot pop element:stack empty");
		return '\0'; /*在不能出栈，我们返回的是‘\0’.相当于空
		注意不是‘0’，这就是返回了字符0了*/
	}
	
	paraStack->top --;
	
	return paraStack->data[(paraStack->top)+1];
	/*我们注意到，压栈和出栈的操作时间复杂度度极低，为o(1),
	这也是栈的一个极大优势*/
}

void pushPopTest() 
{
	char ch;
	int i;
    printf("---- pushPopTest begins. ----\r\n");

	
    charStackPtr tempStack = stackInit();
    printf("After initialization, the stack is: ");
	outputStack(tempStack);

	
	for (ch = 'a'; ch < 'm'; ch ++) 
	{
		printf("Pushing %c.\r\n", ch);
		push(tempStack, ch);
		outputStack(tempStack);
	}

	
	for (i = 0; i < 3; i ++) 
	{
		ch = pop(tempStack);
		printf("Pop %c.\r\n", ch);
		outputStack(tempStack);
	}

    printf("---- pushPopTest ends. ----\r\n");
}

int bracketMatching(char paraString[],int paraLength)
{
	//不知道为啥我的编译器不支持bool，我就用int代替的，效果一样
	int i;
	char tempChar,tempPopedChar;
	charStackPtr tempStack = stackInit();
	/*这里是个重要的地方，为了统一操作，我们在第栈的第0个位置手动push
	了一个#号，这个#号的作用相当于单链表的头结点，是不能触碰的，如果栈
	里面只剩下了#号说明为空栈，这个操作在我们后续写代码也会常用到*/
	push(tempStack,'#');
	tempStack->top = 0;
	
	/*是这样的，只要我们发现了([{,都将其存入栈中，发现了)]},就将栈顶pop
	出来，并且如果栈顶元素不是对应的左括号，代表括号不匹配，就直接return 0了*/
	for(i = 0;i < paraLength;i ++)
	{
		tempChar = paraString[i];
		
		switch (tempChar)
		{
			case '(':
			case '[':
			case '{':
				push(tempStack,tempChar);
				break;
			case ')':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar != '(')
				{
					return 0;
				}
				break;
			case ']':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar != '[')
				{
					return 0;
				}
				break;
			case '}':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar != '{')
				{
					return 0;
				}
				break;
			default :
				break;	
		}
			
	}
	//如何判断为空栈，直接用到了我们的#号
	tempPopedChar = pop(tempStack);
	if(tempPopedChar != '#')
	{
		return 0;
	}
	
	return 1;
}

void bracketMatchingTest() 
{
	char* tempExpression = "[2 + (1 - 3)] * 4";
	int tempMatch = bracketMatching(tempExpression, 17);
	printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);


	tempExpression = "( )  )";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);

	tempExpression = "()()(())";
	tempMatch = bracketMatching(tempExpression, 8);
	printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);

	tempExpression = "({}[])";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);


	tempExpression = "((((";
	tempMatch = bracketMatching(tempExpression, 4);
	printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);
	/*这个测试代码也用到了我们设置的#号，第一个字符就直接return 0,
	十分方便*/
	tempExpression = ")(";
	tempMatch = bracketMatching(tempExpression, 2);
	printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);
}

int main()
{
	pushPopTest();
	bracketMatchingTest();
}
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

四.运行结果

---- pushPopTest begins. ----
After initialization, the stack is:
Pushing a.
a
Pushing b.
a b
Pushing c.
a b c
Pushing d.
a b c d
Pushing e.
a b c d e
Pushing f.
a b c d e f
Pushing g.
a b c d e f g
Pushing h.
a b c d e f g h
Pushing i.
a b c d e f g h i
Pushing j.
a b c d e f g h i j
Pushing k.
Cannot push element:stack full
a b c d e f g h i j
Pushing l.
Cannot push element:stack full
a b c d e f g h i j
Pop j.
a b c d e f g h i
Pop i.
a b c d e f g h
Pop h.
a b c d e f g
---- pushPopTest ends. ----
Is the expression '[2 + (1 - 3)] * 4' bracket matching? 1
Is the expression '( )  )' bracket matching? 0
Is the expression '()()(())' bracket matching? 1
Is the expression '({}[])' bracket matching? 1
Is the expression '((((' bracket matching? 0
Is the expression ')(' bracket matching? 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