c++ 栈和栈的应用（图解）

1栈的基本介绍

栈( stack〉是限制插入和删除操作只能在一个位置上进行的表，该位置是表的末端，称为栈的顶〈 top)。对栈的基本操作是push(进栈〉和pop(出栈)，前者相当于插入，后者则是删除最后插入的元素。最后插入的元素可以通过使用top例程在执行pop之前进行访问。对空栈进行的pop或top操作，在栈ADT中一般认为是一个错误。另一方面，当运行push时在空间之外操作是实现限制，但不是ADT错误。

栈的简单模型：

 栈有时又称为LIFO（后进先出）表。在上图中描述的模型意味着只有push是输入操作，并且只有pop和top是输出操作。普通的清空栈的操作和判断是否空栈的测试都是栈的操作指令系统的一部分，但是，对栈所能够做的所有操作基本上就是push和pop操作。

抽象的表（只有栈顶可以访问）：

 2.栈的实现

最流行的两个办法：

1.栈的链表实现：

栈的第一种实现方法是使用单向链表。我们通过在表顶端插入元素来实现push，通过删除表顶端元素实现pop。top操作只是访问表顶端元素并返回它的值。有时pop操作和top操作合二为

2.栈的数组实现

另一种可选的实现避免了使用链并且可能是更流行的解决方案。由于使用vector中的back、push_back和pop_back实现,因此这个实现很简单。

每个栈有一个theArray和一个topofstack,对于空栈其值为-1(这也就是空栈的初始化)。为了将某个元素x压入到栈中，将topofstack加1，然后置theArray[topofstack]=x。为了弹出栈元素，置pop函数的返回值为theArray [topofstack]，然后将topofstack减1。

3.栈的应用

3.1 平衡符号

做-一-个空栈。读入字符直至文件尾。如果字符是一个开放符号，则将其压入栈中。如果字符是一个封闭符号，那么若栈为空，则报错;若栈不为空，则将栈元素弹出。如果弹出的符号不是对应的开放符号，则报错。在文件尾，如果栈非空则报错。

代码如下：

实现的大致原理是将所有左符号添加到栈中，当遇到右符号的时候就和栈顶元素做匹配，如果能匹配这将当前栈顶元素pop掉，
从而使栈内始终都是左符号，只是将新输入的右括号与栈顶的做匹配，注意右符号是没有入栈的！
 
/*
	date: 2014/6/5
	time: 20:07
	运行环境：windows 7 + MinGW + Sublime_text_3
	注意：此代码不能判断符号相互交叉的匹配，比如({)},只能测试{([])({})}类型的
*/
#include 
#include 
#include 
 
using namespace std;
 
struct Stack
{
	int size;//stack's max size
	char *base;
	char *top;
};
 
bool init_stack(Stack &s)//初始化栈
{
	char *tmp = new char[100];
	if (tmp == NULL)
	{
		cout << "applay for memory failed" << endl;
		exit(1);
	}
	s.base = s.top = tmp;
	s.size = 100;//最大栈容量
	return true;
}
 
bool push(Stack &s, char ch)//插入元素
{
	if (s.top - s.base > s.size - 1)//检查是否溢出
	{
		cout << "ERROR! STACKOVERFLLOW" << endl;
		return false;
	}
	*s.top = ch;//插入入元素
	s.top++;//栈顶指针上移
	return true;
}
 
bool pop(Stack &s)//删除元素
{
	if (s.base == s.top)
	{
		return false;
	}
	s.top--;//顶端指针下移
}
 
char get_top(Stack &s)//获取栈顶元素
{
	if (s.base == s.top)
	{
		return false;
	}
	char *tmp = s.top;//使用tmp表示临时指针，防止栈顶指针被修改
	tmp--;
	return *tmp;
}
 
bool empty(Stack &s)//判断是否为空栈
{
	if (s.base == s.top)
		return true;
	else
		return false;
}
 
//遍历全栈的函数，测试时用，能正常使用时可以不用
void traversal(Stack &s)
{
	if (s.base == s.top)
	{
		cout << "empty" << endl;
		return;
	}
 
	char *tmp = s.top;
	tmp--;
 
	while (tmp >= s.base)
	{
		cout << *tmp << "";
		tmp--;
	}
	cout << endl;
}
 
 
int main(int argc, char const *argv[])
{
	Stack s;
	init_stack(s);
	char str[100];
	cout << "input a charactor string \"() {} []\"" << endl;
	cin >> str;
	for (int i = 0; i < strlen(str); ++i)
	{
		switch(str[i])
		{
			//如果是左括号都将其入栈
			case '(': 
				push(s, '('); 
				break;
			case '[': 
				push(s, '[');
				break;
			case '{': 
				push(s, '{');
				break;
			//如果是右括号，
			case ')': 
				if (empty(s) || get_top(s) == ')')//判断当前栈是否为空，或者栈顶已经是右括号
					push(s, ')');//继续入栈
				else if (get_top(s) == '(') //如果正好前后匹配，则清除栈顶元素
					pop(s);
				break;
			case ']':
				if (empty(s) || get_top(s) == ']')
					push(s, ']');
				else if (get_top(s) == '[')
					pop(s);
				break;
			case '}':
				if (empty(s) || get_top(s) == '}')
					push(s, '}');
				else if (get_top(s) == '{')
					pop(s);
				break;
			default:
				cout << "what you've input is invalid" << endl;
				return 1;
		}
	}
 
	if (s.base == s.top)
		cout << "congratuate, all charactor has matched" << endl;
	else
		cout << "sorry! \'" << *s.base << "\' can not matched" << endl;//只能输出栈底没有匹配的符号
	return 0;
}
/*
测试字符串：
((({{[[[(({[]}))]]]}})))
*/

3.2后缀表达式

假设我们有一个便携计算器并想要计算一趟外出购物的花费。为此，我们将一列数据相加并将结果乘以1.06;它是所购商品的价格加上部分商品的地方税。如果各项购物花销为4.99、5.99和6.99、那么输入这些数据的自然的方式将是
                                             

随着计算器的不同，这个结果或者是所要的答案19.05，或者是科学的答案18.39。最简单的四功能计算器将给出第一个答案，但是许多先进的计算器是知道乘法的优先级高于加法的。

另一方面，有些项是需要上税的而有些项则不需要上税，因此，如果只有第一项和最后一项是要上税的，那么计算的顺序

                                             

该例子的典型计算顺序是将4.99和1.06相乘并存为A，然后将5.99和A相加，再将结果存入A;再将6.99和1.06相乘并将答案存为A，最后将A和A,相加并将最后结果放入A,。可以将这种操作顺序书写如下:

                                            4.99 1.06 *5.99 + 6.99 1.06 * +

这种记法叫作后缀( postfix）或逆波兰记法（reverse Polish notation) 

实践：        

                                           6 5 2 3 +8 *＋３＋*

（1）

          

 

 （2）:读到+ 把 3 2 pop出去 push3+2

 

 （3）push 8进栈

 

 （4）读到* pop8 5 push 8* 5

（5）3入栈 读到+ pop45 3 push 45+3

(6) 最后，遇到一个“*”号，从栈中弹出48和6;将结果6*48= 288压进栈中。

 

 6 5 2 3 +8 *＋３＋*->

3.3中缀到后缀的转化

栈个仅可以用来计算后缀表达式的值，而且还可以用米将一个杯准形式的表达式（或叫作中缀式(infix)）转换成后缀式。通过只允许操作符“+”、“*”、“(”、“)”，并坚持普通的优先规则而将一般的问题浓缩成小规模的问题。还要进一步假设表达式是合法的。设欲将中缀表达式

a+b∗c+(d∗e+f)∗g" role="presentation" style="position: relative;">a+b∗c+(d∗e+f)∗g$a+b\ast c+(d\ast e+f)\ast g$

转化成a b c * + d e * f + g *+

这个算法的思想是，当遇到一个操作符的时候，把它放到栈中。栈代表挂起的操作符。然而，当栈中那些具有高优先级的操作符完成使用时，就不需要再被挂起而是应该被弹出。这样，在把当前操作符放入栈中之前，那些栈中在使用当前操作符之前将要完成使用的操作符被弹出。详细的解释见下表;

 上面算式转化

（1）a b 输出 +入栈

（2）*入栈 操作符栈顶比*的优先级低

* 不进栈 c读入并输出

 

（3） 后面读入 + （优先级比* + 低或相同）弹出* + 入栈+

 

继续进行，乂读到一个（（最高优先级）和“*”。山于除非正在处理闭括号，否则开括号不会从栈中弹出，因此没有输出。下---个是。.它枇读入并输出

 

再往后读到的符号是“+”。将“*”弹出并输出，然后将“+”压入栈中。这以后，读到f并输出

最后读到）把之间pop

 

 下面又读到一个“*”;该操作符被压入栈中。然后，g被读入并输出。

 

现在输入为空，因此我们将栈中的符号全部弹出并输出，直到栈变成空栈。 

 

 3.4.函数调用

参考资料c++内存管理

检测平衡符号的算法提出一种在编译的过程语言和面向对象的语言中实现函数调用的方式。这里的问题是，当调用一个新函数时，主调例程的所有局部变量需要由系统存储起来，否则被调用的新函数将会重写由主调例程的变量所使用的内存。不仅如此，该主调例程的当前位置必须要存储，以便在新函数运行完后知道向哪里转移。这些变量一般由编译器指派给机器的寄存器，但存在某些冲突（通常所有的函数都得到指定给1#寄存器的某些变量)，特别是涉及递归的时候。该问题类似于平衡符号问题的原因在于，函数调用和函数返回基本上类似于开括号和闭括号，二者想法是-一样的。

当存在函数调用的时候，需要存储的所有重要信息，诸如寄存器的值（对应变量的名字）和返回地址（它可从程序计数器得到，一般情况下是在寄存器中）等，都要以抽象的方式存在“一-张纸上”并被置于--个堆( pile）的顶部。然后控制转移到新函数，该函数自由地用它的值代替这些寄存器。如果它又进行其他的函数调用，那么也遵循相同的过程。当该函数要返回时，它查看堆顶部的那张“纸”并复原所有的寄存器。然后它进行返回转移。

显然，所有工作均可由一个栈来完成，而这正是在实现递归的每一种程序设计语言中实际发生的事实。所存储的信息或称为活动记录(activation record)，或称为栈帧( stack frame)。一般情况下，需要做些微调:当前环境是由栈顶描述的。因此，一条返回语句就可给出前面的运行环境（不用复制)。在实际计算机中，栈常常是从内存分区的高端向下增长，而在许多系统中是不检测溢出的。由于同时有太多的正在运行着的函数，因此用尽栈空间的情况总是可能发生的。勿庸置疑，用尽栈空间总是致命的错误。

template<typename T>
void print(T start,T end,ostream& out=cout)
{
if(start==end)return;
out<<*start++<
print(start,end,out);
}

在正常情况下不应该用尽栈空间;发生这种情况通常意味着有失控递归（忘记基准情形)的存在。另一方面，某些完全合法并且表面上无害的程序也可能用尽栈空间。图3-25中的例程打印一-个容器，该例程完全合法而且事实上也是正确的。它正确地处理空容器的基准情形，并且递归也没问题。可以证明这个程序是正确的。但是，如果这个链表含有20000个元素要打印，那么就存在表示第11行嵌套调用的20 000个活动记录的一个栈。一般这些活动记录由于它们包含全部信息而特别庞大，因此这个程序很可能要用尽栈空间（如果20000个元素还不足以使程序崩溃，那么可用更大的数字代替)。