数据结构与算法学习（day6）——栈

前言

本章我们学习栈。

（1）上一节我们学习了队列，它是一种先进先出的数据结构。还有一种先进后出的数据结构叫栈。

（2）栈限定为只能在一端就行插入和删除操作。

（3）生活中有很多栈的数据结构的例子，比如我们在浏览网页的时候需要退回之前的某个网页，我们需要一步步地点击后退键。还有手枪的弹匣，在装子弹的时候，最后装入的那发子弹是被第一个打出去的。

本章的学习目标：

（1）理解栈的基本原理

（2）理解栈的算法的基本原理

（3）能够使用栈算法解决简单的实际问题

例题引入

题目：运用栈来判断一串字符是否为回文，回文是这种对称的字符串：“xyzyx”、“aha”……

思路：

（1）首先读取这行字符串，并求出这个字符串的长度。

	gets(a);  //读入一行字符串
	len = strlen(a);  //求字符串的长度
	mid = len / 2 - 1;  //求字符串的中点
1
2
3

（2）将mid前的字符全部入栈（从头入栈）

	//将mid前的字符依次入栈
	for (i = 0; i <= mid; i++)
	{
		s[++top] = a[i];  //运行完后，top的值已经是中点前的最后一个值了
	}
1
2
3
4
5

（3）将栈中字符依次出栈（从最后一个开始元素出栈，后进先出），看看是否能与mid之后的字符一一匹配，如果都能匹配就是回文，若不能，则不是。

	//判断字符串的长度是奇数还是偶数，并找出需要进行字符匹配的起始下标next
	if (len % 2 == 0)  //偶数
		next = mid + 1;
	else
		next = mid + 2;

	//开始匹配
	for (i = next; i <= len - 1; i++)
	{
		if (a[i] == a[top])  //mid前和mid后的元素是否能一一匹配
			break;
		top--;  
	}
	if (top == 0)
		printf("YES");
	else
		printf("NO");
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（4）完整代码

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 

int main()
{
	char a[101], s[101];
	int i, len, mid, next, top;

	gets(a);  //读入一行字符串
	len = strlen(a);  //求字符串的长度
	mid = len / 2 - 1;  //求字符串的中点

	top = 0; //栈的初始化

	//将mid前的字符依次入栈
	for (i = 0; i <= mid; i++)
	{
		s[++top] = a[i];  //运行完后，top的值已经是中点前的最后一个值了，top的值就是s数组里存的元素个数
	}


	//判断字符串的长度是奇数还是偶数，并找出需要进行字符匹配的起始下标
	if (len % 2 == 0)  //偶数
		next = mid + 1;
	else
		next = mid + 2;

	//开始匹配
	for (i = next; i <= len - 1; i++)
	{
		if (a[i] != s[top])  //mid前和mid后的元素是否能一一匹配
			break;
		top--;  //若全部取出去，则top=0
	}
	if (top == 0)
		printf("YES");
	else
		printf("NO");

	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

也可以是

#define _CRT_SECURE_NO_WARNINGS 1
/*回顾： 运用栈来判断一串字符是否为回文，回文是这种对称的字符串：“xyzyx”、“aha”……*/
#include 
#include 
int main()
{
	char a[101],s[101];
	int len,mid,next,i,top;
	top = 0;
	gets(a);
	len = strlen(a);
	mid = len / 2 - 1;

	for (i = 0; i <= mid; i++)
		s[++top] = a[i];
	if (len % 2 == 0)  //偶数
		next = mid + 1;
	else
		next = mid + 2;

	for (i = next; i <= len - 1; i++)
	{
		if (a[i] == s[top])
			top--;
		else
			break;
	}

	if (top == 0)
		printf("YES");
	else
		printf("NO");
	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

Tips

有几点需要注意一下

1. 这个代码中，字符串的中点是strlen(a)-1；是符合把a[strlen(a)-1]自己及之前的所有元素都入栈的目的；字符串真正的中点还得看字符串的长度为计数偶数进行讨论。
2. 注意这道题的判断对象是字符，所以把数组的类型要定义为char。若粗心定义为int，肯定就错了。
3. 入栈和出栈的代码操作一定要掌握熟练，理解好原理。