数据结构3-栈和队列的操作

• 一.栈和队列
• • 1.栈stack
  • 2.队列queue
• 二.应用
• • 1.stack数制转换
  • 2.stack括号匹配
  • 3.表达式的计算和优先级的处理（中缀转后缀）
  • 4.queue输出杨辉三角行
  • 5.利用堆栈把递归过程改成非递归过程

    栈stack是一种特殊的数据结构，它的逻辑结构和线性表相同，但是他的运算操作收到了更多的限制，即只能从一端放入数据，也只能从一端读取数据。存取数据的一端称作栈顶top，另一端的栈底bottom不允许做任何存取的操作。取出栈最上面的元素（栈顶top）这个操作叫做pop，存入元素的操作叫push，当堆栈为空时叫做空栈。
    举个通俗的栗子：洗完碗，我们一个叠一个放好，自然是先放最下面一个碗，然后才能继续往上放碗，拿碗的时候也是先拿上面的碗，拿完了才能拿下面的碗。
    栈的特征是后进先出。至于栈的具体实现，我们可以自己写。最简单的实现方式就是用一个数组，只在数组的尾部进行元素的push和pop即可。当然更常用的是调用C++的STL库，里面有封装好的stack数据类型，使用起来更加方便。

    队列queue是另一种限定存取位置的线性表。它只允许在队列的一段存入数据push，只允许在队列的另一端取出数据pop。允许插入的一端叫做队尾，允许取出的一端叫做队头。
    举个通俗的栗子：一队人在食堂排队打饭，大家的素质都很高。每来一个人都自动站到队尾，队头的那个人先打饭，打完饭后离开队伍。这种先进先出的数据结构就叫做队列。

    一个数从10进制转换为2进制，方法为：将这个数不停的整除2，直到余数为0为止。所有的商运算结果倒序输出就是最终的答案。因为这个计算算过程是从低位到高位逐个进行的，但是输出过程是从高位到低位的。因此需要用栈来实现。

#include 
#include 
using namespace std;
int main() {
	int x;
	printf("请输入一个十进制数：");
	scanf("%d", &x);
	int tmp = x;
	stackn;
	while (tmp != 0) {
		n.push(tmp % 2);
		tmp /= 2;
	}
	printf("%d 的二进制为 ", x);
	while (!n.empty()) {
		printf("%d", n.top());
		n.pop();
	}
	printf("n");
}

    一串算式，里面会有很多括号，我们需要面对的难题是：

• 这个算式中的括号是否合法：(1+2))
• 加上了括号，算式的优先级又该如何考虑

    这里我们先解决第一个问题，也就是括号匹配问题。
    自左向右开始扫描算式，只要遇到左括号‘（’就立刻让它进栈。如果遇到右括号‘）’，分两种情况考虑：如果堆栈是空的，那么直接报错后退出程序。如果堆栈不是空的，再看栈顶，若栈顶是左括号‘（’，就将左括号‘（’抛出，如果栈顶是右括号‘）’，就将当前读到的右括号压入栈中。
    具体的代码实现我们在下一部分一并给出。

    在前面，我们已经知道了如何进行括号的匹配。但是，在进行表达式计算的时候，我们还需要考虑到各运算符的优先级的问题。

• 加减<乘除<幂运算
• 当符号优先级一样时，从左往右先出现的运算符优先运算。（幂运算很特殊，要注意不遵守此条，可以考虑 a b c a^{b^c} abc，就是ｂ和ｃ先结合)

    基于上述考虑，我们已经有了如下思路：
    开两个堆栈，figures存放字母,opt存放运算符。读到数字就往figures里push，读到运算符就往opt里push。如果当前读到的运算符的优先级比opt的top低的话，那opt就出栈，并从figures中出栈２个字母参与运算，直到opt的栈顶优先级比当前读到的运算符低或者空栈，再将当前的运算符push。
    注意：左括号在堆栈外优先级最高，一旦进入栈中优先级变最低。

#include 
#include 
#include 
using namespace std;
char operation[100000];
stackx;
int compare_opt(char a, char b) {//如果负数，a优先级比b低，如果正数，a优先级比b高
	int x, y;
	if (a == '+' || a == '-') x = 1;
	else if (a == '^')x = 3;
	else if (a == '(')x = 0;
	else x = 2;
	if (b == '*' || b == '/')y = 2;
	else if (b == '^')y = 10;
	else if (b == '(')y = 0;
	else y = 1;

	return x - y;
}
int main() {
	int N;
	scanf("%d", &N);
	getchar();
	while (N) {
		gets(operation);
		int len = strlen(operation);
		for (int i = 0; i < len - 1; i++) {
			if ((operation[i] <= 'z' && operation[i] >= 'a') || (operation[i] <= 'Z' && operation[i] >= 'A')) {
				//当前读到的是字母
				printf("%c", operation[i]);
			}
			else {
				//当前读到的是运算符
				//首先判断是不是特殊运算符
				if (operation[i] == '(') {
					x.push(operation[i]);
				}
				else if (operation[i] == ')') {
					//遇到了右括号
					while (x.top() != '(') {
						printf("%c", x.top());
						x.pop();
					}
					x.pop();
				}
				else {
					//常规运算符
					if (x.empty()) {
						x.push(operation[i]);
					}
					else {
						while (!x.empty() && compare_opt(x.top(), operation[i]) >= 0) {
							if (operation[i] == '^' && compare_opt(x.top(), operation[i]) == 0)break;//注意幂运算的特殊
							printf("%c", x.top());
							x.pop();
						}
						x.push(operation[i]);
					}

				}

			}
		}
		while (!x.empty()) {
			printf("%c", x.top());
			x.pop();
		}
		printf("n");
		N--;
	}
}

    在计算机中，队列常常用于解决需要逐行处理的问题。杨辉三角行就是一个典型的分层处理的例子。杨辉三角行的每一行的数字正好对应二项式 ( a + b ) i (a+b)^i (a+b)i展开各项的系数。

    杨辉三角行的一个性质为：它的第i行的各个数字对应第i-1相应的两个数字的相加。我们可以采用一个队列，逐层处理这个分层结构。具体代码如下

#include 
#include 
using namespace std;
int main() {
	int n;
	int x = 0, y;
	queueque;
	scanf("%d", &n);
	//第一行的两个系数预先压入队列
	que.push(1);que.push(1);
	for (int i = 1; i < n; i++) {
		printf("n");
		que.push(0);
		for (int j = 1; j <= i + 2; j++) {
			y = que.front(); que.pop();
			que.push(x + y);
			x = y;
			if (j != i + 2)printf(" %d", x);
		}
	}
}

    先来看一个递归的经典，汉诺塔问题。

#include 
void Hanoi(int n, char A, char B, char C) {
	//有n个盘子，从A借助B挪动到C
	if (n == 1)
		printf("Move disk from %c to %c.n", A, C);
	else {
		Hanoi(n - 1, A, C, B);//把A上的n-1个盘子通过C移动到B
		printf("Move disk from %c to %c.n", A, C);
		Hanoi(n - 1, B, A, C);//把刚刚挪动的B通过A堆到C上
	}
}
int main() {
	int n;
	scanf("%d", &n);
	Hanoi(n, 'A', 'B', 'C');
}

    这里采用了分治法的思路。将n个盘子的移动分解为一个盘子（把n-1个盘子打包看作1个）和另一个盘子之间如何移动，将求解规模为n的问题分解成了两个规模为n-1的问题。按照这种自顶向下，逐层分解的原则，从而设计出来递归算法。
    但是，稍加分析我们发现，这个算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2),和递归深度的平方成正比。同时，由于递归调用时需要调用递归工作栈存放每一轮递归的局部变量的，因此空间复杂度为 O ( n ) O(n) O(n)。
    这很不妙。因此，我们希望利用栈把它改成非递归的，希望能对其时空复杂度进行优化。