前言

部分内容摘自程杰的《大话数据结构》

1. 栈的定义

1.1 栈的定义

很多软件，比如Word、 Photoshop 等文档或图像编辑软件中，都有撤销（undo）的操作，也是用栈这种方式来实现的，当然不同的软件具体实现代码会有很大差异，不过原理其实都是一样的。

栈( stack )是限定仅在表尾进行插入和删除操作的线性表。

我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。
理解栈的定义需要注意：
首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。
它的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。
栈的插入操作，叫作进栈，也称压栈、入栈。如下图所示。

栈的删除操作，叫作出栈，也有的叫作弹栈。如下图所示。

1.2 进栈出栈变化形式

栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制，也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就可以。
举例来说，如果我们现在是有 3 个整型数字元素 1、2、3 依次进栈，会有哪些出栈次序呢？

第一种：1、2、3 进，再 3、2、1 出。这是最简单的最好理解的一种，出栈次序为 3、2、1。
第二种：1 进，1 出，2 进，2 出，3 进，3 出。也就是进一个就出一个，出
栈次序为 1、2、3。
第三种：1 进，2 进，2 出，1 出，3 进，3 出。出栈次序为 2、1、3.
第四种：1 进，1 出，2 进，3 进，3 出，2 出。出栈次序为 1、3、2。
第五种：1 进，2 进，2 出，3 进，3 出，1 出。出栈次序为 2、3、1。

有没有可能是 3、1、2 这样的次序出栈呢？答案是肯定不会。因为 3 先出栈，就意味着，3 曾经进栈，既然 3 都进栈了，那也就意味着，1 和 2 已经进栈了，此时，2 一定是在 1 的上面，就是更接近栈顶，那么出栈只可能是 3、2、1，不然不满足 1、2、3 依次进栈的要求，所以此时不会发生 1 比 2 先出栈的情况。
从这个简单的例子就能看出，只是 3 个元素，就有 5 种可能的出栈次序，如果元素数量多，其实出栈的变化将会更多的。

2. 栈的抽象数据类型

对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，所以针对它在操作上会有些变化。特别是插入和删除操作，我们改名为push和pop，英文直译的话是压和弹，更容易理解。你就把它当成是弹夹的子弹压入和弹出就好记忆了，我们一般叫进栈和出栈。

ADT栈(stack)
Data
	同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
	Initstack(*S)：初始化操作，建立一个空栈S。
	DestroyStack(*S)：若栈存在，则销毁它。
	Clearstack(*S)：将栈清空。
	StackEmpty(S)：若栈为空，返回true,否则返回false。
	GetTop(S,*e)：若栈存在且非空，用e返回S的栈顶元素。
	Push(*S,e):若栈S存在，插入新元素e到栈S中并成为栈顶元素。
	Pop(*S,*e) :删除栈S中栈顶元素，并用e返回其值。
	StackLength(S) :返回栈S的元素个数。
endADT

由于栈本身就是一个线性表，那么线性表的顺序存储和链式存储，对于栈来说，也是同样适用的。

3. 栈的顺序存储结构及实现

3.1 栈的顺序存储结构

既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。线性表是用数组来实现的，想想看，对于栈这种只能一头插入删除的线性表来说，用数组哪一端来作为栈顶和栈底比较好?
对，没错，下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以让它作栈底。
我们定义一个top变量来指示栈顶元素在数组中的位置，这top就如同中学物理学过的游标卡尺的游标，它可以来回移动，意味着栈顶的top可以变大变小，但无论如何游标不能超出尺的长度。同理，若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于 0，因此通常把空栈的判定条件定为top等于 -1。
来看栈的结构定义：

typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

/* 顺序存储结构 */
typedef struct
{
	SElemType data[MAXSIZE];
	int top;	/* 用于栈顶指针 */
}SqStack;

若现在有一个栈，StackSize是 5，则栈普通情况、空栈和栈满的情况示意图如下图所示。

3.2 栈的顺序存储结构——进栈操作

出栈pop：

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回oK;否则返回ERROR */
Status Pop(SqStack *s,SElemType *e)
{
	if(S->top==-1)
		return ERROR;
	*e=S->data[S->top];	/* 将要删除的栈顶元素赋值给e */
	S->top--;	/* 栈顶指针减一 */
	return OK;
}

两者没有涉及到任何循环语句，因此时间复杂度均是O(1)。

4. 两栈共享空间

其实栈的顺序存储还是很方便的，因为它只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个很大的缺陷，就是必须事先确定数组存储空间大小，万一不够用了，就需要编程手段来扩展数组的容量，非常麻烦。对于一个栈，我们也只能尽量考虑周全，设计出合适大小的数组来处理，但对于两个相同类型的栈，我们却可以做到最大限度地利用其事先开辟的存储空间来进行操作。
打个比方，两个大学室友毕业同时到北京工作，开始时，他们觉得住了这么多年学校的集体宿舍，现在工作了一定要有自己的私密空间。于是他们都希望租房时能找到独住的一居室，可找来找去却发现，最便宜的一居室也要每月 1500 元，地段还不好，实在是承受不起，最终他俩还是合租了一套两居室，一共2000元，各出一半，还不错。
对于两个一居室，都有独立的卫生间和厨房，是私密了，但大部分空间的利用率却不高。而两居室，两个人各有卧室，还共享了客厅、厨房和卫生间，房间的利用率就显著提高，而且租房成本也大大下降了。
同样的道理，如果我们有两个相同类型的栈，我们为它们各自开辟了数组空间，极有可能是第一个栈已经满了，再进栈就溢出了，而另一个栈还有很多存储空间空闲。这又何必呢？我们完全可以用一个数组来存储两个栈，只不过需要点小技巧。
我们的做法如下图，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为 0 处，另一个栈为数组的末端，即下标为数组长度n-1处。这样，两个栈如果增加元素，就是两端点向中间延伸。

其实关键思路是：它们是在数组的两端，向中间靠拢。top1和top2是栈 1 和栈 2 的栈顶指针，可以想象，只要它们俩不见面，两个栈就可以一直使用。.
从这里也就可以分析出来，栈 1 为空时，就是top1等于 -1 时；而当top2等于n时，即是栈 2 为空时，那什么时候栈满呢？
想想极端的情况，若栈 2 是空栈，栈 1 的top1等于n-1时，就是栈 1 满了。反之，当栈 1 为空栈时，top2等于 0 时，为栈 2 满。但更多的情况，其实就是刚才说的，两个栈见面之时，也就是两个指针之间相差 1 时，即top1+1==top2为栈满。
两栈共享空间的结构的代码如下：

/* 两栈共享空间结构 */
typedef struct
{
	SElemType data[MAXSIZE];
	int top1;	/* 栈1栈顶指针 */
	int top2;	/* 栈2栈顶指针 */
}SqDoubleStack;

对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈 1 还是栈 2 的栈号参数stackNumber。插入元素的代码如下：

/* 插入元素e为新的栈顶元素 */
Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{
	if (S->top1+1==S->top2)	/* 栈已满，不能再push新元素了 */
		return ERROR;
	return ERROR;
	if (stackNumber==1)	/* 栈1有元素进栈 */
		S->data[++S->top1]=e;	/* 若是栈1则先top1+1后给数组元素赋值 */
	else if (stackNumber==2)	/* 栈2有元素进栈 */
		S->data[--S->top2]=e;/* 若是栈2则先top2-1后给数组元素赋值 */
	return OK:
}

因为在开始时已经判断了是否有栈满的情况，所以后面的top1+1或top2-1是不担心溢出问题的。
对于两栈共享空间的pop方法，参数就只是判断栈 1 栈 2 的参数stackNumber，代码如下：

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR */
Status Pop(SqDoubleStack *s,SElemType *e,int stackNumber)
{
	if (stackNumber==1)
	{
		if (S->top1==-1)
			return ERROR;	/* 说明栈1已经是空栈，溢出 */
		*e=s->data[S->top1--];	/* 将栈1的栈顶元素出栈 */
	}
	else if (stackNumber==2)
	{
		if (S->top2==MAXSIZE)
			return ERROR:	/* 说明栈2已经是空栈，溢出 */
		*e=S->data[S->top2++];	/* 将栈2的栈顶元素出栈 */
	}
	return OK:

事实上，使用这样的数据结构，通常都是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况。就像买卖股票一样，你买入时，一定是有一个你不知道的人在做卖出操作。有人赚钱，就一定是有人赔钱。这样使用两栈共享空间存储方法才有比较大的意义。否则两个栈都在不停地增长，那很快就会因栈满而溢出了。
当然，这只是针对两个具有相同数据类型的栈的一个设计上的技巧，如果是不相同数据类型的栈，这种办法不但不能更好地处理问题，反而会使问题变得更复杂，大家要注意这个前提。

5. 栈的链式存储结构及实现

5.1 栈的链式存储结构

讲完了栈的顺序存储结构，我们现在来看看栈的链式存储结构，简称为链栈。
想想看，栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？由于单链表有头指针，而栈顶指针也是必须的，那干吗不让它俩合二为一呢？所以比较好的办法是把栈顶放在单链表的头部（如下图所示）。另外，都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。
但对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候。
链栈的结构代码如下：

/* 链栈结构 */
typedef struct StackNode
{
	SElemType data;
	struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct Linkstack
{
	LinkstackPtr top;
	int count;
}Linkstack;

链栈的操作绝大部分都和单链表类似，只是在插入和删除上，特殊一些。

5.2 栈的链式存储结构——进栈操作

对于链栈的进栈push操作，假设元素值为e的新结点是s，top 为栈顶指针，如下所示：

/* 插入元素e为新的栈顶元素 */
Status Push(Linkstack *S,SElemType e)
{
	LinkstackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
	s->data=e;
	s->next=S->top;	/* 把当前的栈頂元素赋值给新结点的直接后继，如图中① */
	S->top=s;	/* 将新的结点s赋值给栈顶指针，如图中② */
	S->count++:
	return OK;
}

5.3 栈的链式存储结构——出栈操作

至于链栈的出栈pop操作，也是很简单的三句操作。假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可，如下所示。

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR */
Status Pop(LinkStack *S,SElemType *e)
{
	LinkStackPtr p;
	if(StackEmpty(*S))
		return ERROR;
	*e=S->top->data;
	p=S->top;	/* 将栈顶结点赋值给p，如图③ */
	S->top=S->top->next;	/* 使得栈顶指针下移一位，指向后一结点，如图④ */
	free(p);	/* 释放结点p */
	S->count--:
	return OK;
}

链栈的进栈push和出栈pop操作都很简单，没有任何循环操作，时间复杂度均为O(1)。
对比一下顺序栈与链栈，它们在时间复杂度上是一样的，均为O(1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一一些。

6. 栈的作用

有的人可能会觉得，用数组或链表直接实现功能不就行了吗？干嘛要引入栈这样的数据结构呢？
其实这和我们明明有两只脚可以走路，干吗还要乘汽车、火车、飞机一样。理论上，陆地上的任何地方，你都是可以靠双脚走到的，可那需要多少时间和精力呢？我们更关注的是到达而不是如何去的过程。
栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。而像线性表顺序存储结构用到的数组，因为要分散精力去考虑数组的下标增减等细节问题，反而掩盖了问题的本质。
所以现在的许多高级语言，比如Java、C#等都有对栈结构的封装，你可以不用关注它的实现细节，就可以直接使用Stack的push和pop方法，非常方便。

7. 栈的应用——递归

栈有一个很重要的应用：在程序设计语言中实现了递归。那么什么是递归呢？
当你往镜子前面一站，镜子里面就有一个你的像。但你试过两面镜子起照吗？如果A、B两面镜子相互面对面放着，你往中间一站，嘿，两面镜子里都有你的千百个“化身”。为什么会有这么奇妙的现象呢？原来，A镜子里有B镜子的像，B镜子里也有A镜子的像，这样反反复复，就会产生一连串的“像中像”。这是一种递归现象。
我们先来看一个经典的递归例子：斐波那契数列（Fibonacci）。为了说明这个数列，这位斐老还举了一个很形象的例子。

7.1 斐波那契数列的实现

说如果兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。假设所有兔都不死，那么一年以后可以繁殖多少对兔子呢？
我们拿新出生的一对小兔子分析一下：第一个月小兔子没有繁殖能力，所以还是一对；两个月后，生下一对小兔子数共有两对；三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对……以此类推可以列出下表。

所经过的月数	1	2	3	4	5	6	7	8	9	10	11	12
兔子对数	1	1	2	3	5	8	13	21	34	55	89	144

表中数字 1，1，2，3，5，8，13，.....… 构成了一个序列。这个数列有个十分明显的特点，那就是：前面相邻两项之和，构成了后一项，如下图所示。

可以发现，编号①的一对兔子经过 6 个月就变成 8 对兔子了。如果我们用数学函数来定义就是：

先考虑一下，如果我们要实现这样的数列用常规的迭代的办法如何实现？假设我们需要打印出前 40 位的斐波那契数列数。代码如下：

int main()
{
	int i;
	int a[40];
	a[0]=0;
	a[1]=1;
	printf ("%d ",a[0]);
	printf ("%d ",a[1]);
	for(i = 2;i < 40;i++)
	{
		a[i] = a[i-1] + a[i-2];
		printf("%d ",a[1]);
	}
	return 0;
}

代码很简单，几乎不用做什么解释。但其实我们的代码，如果用递归来实现，还可以更简单。

/* 斐波那契的递归函数 */
int Fbi(int i)
{
	if( i < 2 )
		return 1 == 0 ? 0 : 1;
	return Fbi(i-1)+Fbi(i-2);	/* 这里Fbi就是函数自己，等于在调用自己 */
}

int main()
{
	int i;
	printf("递归显示斐波那契数列：\n");
	for (i = 0;i < 40;i++)
		printf("%d ", Fbi(i));
	return 0;
}

函数怎么可以自已调用自己？听起来有些难以理解，不过你可以不要把一个递归函数中调用自己的函数看作是在调用自己，而就当它是在调另-一个函数。只不过，这个函数和自己长得一样而已。
我们来模拟代码中的Fbi(i)函数当i= 5的执行过程，如下图所示。

7.2 递归的定义

在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。
当然，写递归程序最怕的就是陷入永不结束的无穷递归中，所以，每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。比如刚才的例子，总有一次递归会使得i<2的，这样就可以执行return i的语句而不用继续递归了。
对比了两种实现斐波那契的代码。迭代和递归的区别是：迭代使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同情况选择不同的代码实现方式。
那么我们讲了这么多递归的内容，和栈有什么关系呢？这得从计算机系统的内部说起。
前面我们已经看到递归是如何执行它的前行和退回阶段的。递归过程退回的顺序是它前行顺序的逆序。在退回过程中，可能要执行某些动作，包括恢复在前行过程中存储起来的某些数据。
这种存储某些数据，并在后面又以存储的逆序恢复这些数据，以提供之后使用的需求，显然很符合栈这样的数据结构，因此，编译器使用栈实现递归就没什么好惊讶的了。
简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。
当然，对于现在的高级语言，这样的递归问题是不需要用户来管理这个栈的，一切都由系统代劳了。

8. 栈的应用——四则运算表达式求值

8.1 后缀（逆波兰）表示法的定义

栈的现实应用也很多，我们再来重点讲一个比较常见的应用：数学表达式的求值。
我们小学学数学的时候，有一句话是老师反复强调的，“先乘除，后加减，从左算到右，先括号内后括号外”。这个大家都不陌生。我记得我小时候，天天做这种加减乘除的数学作业，很烦，于是就偷偷拿了老爸的计算器来帮着算答案，对于单纯的两个数的加减乘除，的确是省心不少，我也因此潇酒了一两年。可后来要求要加减乘除，甚至还有带有大中小括号的四则运算，我发现老爸那个简陋的计算器不好使了。比如9+(3-1)×3+10÷2，这是一个非常简单的题目，心算也可以很快算出是 20。可就这么简单的题目，计算器却不能在一次输入后马上得出结果，很是不方便。
当然，后来出的计算器就高级多了，它引入了四则运算表达式的概念，也可以输入括号了，所以现在的 00 后的小朋友们，更加可以偷懒、抄近路做数学作业了。
那么在新式计算器中或者计算机中，它是如何实现的呢？如果让你用C语言或其他高级语言实现对数学表达式的求值，你打算如何做?
这里面的困难就在于乘除在加减的后面，却要先运算，而加入了括号后，就变得更加复杂。不知道该如何处理。
但仔细观察后发现，括号都是成对出现的，有左括号就一定会有右括号，对于多重括号，最终也是完全嵌套匹配的。这用栈结构正好合适，只有碰到左括号，就将此左括号进栈，不管表达式有多少重括号，反正遇到左括号就进栈，而后面出现右括号时，就让栈顶的左括号出栈，期间让数字运算，这样，最终有括号的表达式从左到右巡查一遍，栈应该是由空到有元素，最终再因全部匹配成功后成为空栈的结果。
但对于四则运算，括号也只是当中的一部分，先乘除后加减使得问题依然复杂，如何有效地处理它们呢？
20 世纪 50 年代，波兰逻辑学家 Jan tukasiewicz，当时也和我们现在一样，困惑于如何才可以搞定这个四则运算，不知道他是否也像牛顿被苹果砸到头而想到万有引力的原理，或者还是阿基米德在浴缸中洗澡时想到判断皇冠是否纯金的办法，总之他也是灵感突现，想到了一种不需要括号的后缀表达法，我们也把它称为逆波兰（Reverse Polish Noation, RPN）表示。我想可能是他的名字太复杂了，所以后人只用他的国籍而不是姓名来命名，实在可惜。这也告诉我们，想要流芳百世，名字还要起得朗朗上口才行。这种后缀表示法，是表达式的一种新的显示方式，非常巧妙地解决了程序实现四则运算的难题。
我们先来看看，对于“9+(3-1)×3+10÷2"，要用后缀表示法应该是什么样子。
正常数学表达式：9+(3-1)×3+10÷2
后缀表达式：9 3 1-3 * + 10 2 / +
“9 3 1-3 * + 10 2 / +”这样的表达式成为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。显然，这里没有了括号。对于从来没有接触过后缀表达式的人来讲，这样的表述是很难受的。不过你不喜欢，有“人”喜欢，比如我们聪明的计算机。

8.2 后缀表达式的计算结果

为了解释后缀表达式的好处，我们先来看看，计算机如何应用后缀表达式计算出最终的结果 20 的。
后缀表达式：9 3 1-3 * + 10 2 / +
规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

初始化一个空栈。此栈用来对要运算的数字进出使用。
后缀表达式中前三个都是数字，所以 9、3、1 进栈，如下图所示。
接下来是 “-”，所以将栈中的 1 出栈作为减数，3 出栈作为被减数，并运算 3-1 得到 2，再将 2 进栈。
接着是数字 3 进栈，如下图所示。
后面是 “*”，也就意味着栈中 3 和 2 出栈，2 与 3 相乘，得到 6，并将 6 进栈。
下面是 “+”，所以栈中 6 和 9 出栈，9 与 6 相加，得到 15，将 15 进栈，如下图所示。
接着是 10 与 2 两数字进栈。
接下来是符号 “/”，因此，栈顶的 2 与 10 出栈，10 与 2 相除，得到 5，将5 进栈，如下图所示。
最后一个是符号 “+”，所以 15 与 5 出栈并相加，得到 20，将 20 进栈。
结果是 20 出栈，栈变为空，如下图所示。

果然，后缀表达法可以很顺利解决计算的问题。那么现在应该都有同样的疑问，就是这个后缀表达式 “9 3 1-3 * + 10 2 / +” 是怎么出来的？这个问题不搞清楚，等于没有解决。所以下面，我们就来推导如何让 “9+(3-1)×3+10÷2”转化为 “9 3 1-3 * + 10 2 / +”。

8.3 中缀表达式转后缀表达式

我们把平时所用的标准四则运算表达式，即 “9+(3-1)×3+10÷2” 叫做中缀表达式。因为所有的运算符号都在两数字的中间，现在我们的问题就是中缀到后缀的转化。
中缀表达式 “9+(3-1)×3+10÷2" 转化为后缀表达式“9 3 1-3 * + 10 2 / +”。
规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

初始化一空栈，用来对符号进出栈使用。
第一个字符是数字 9，输出 9，后面是符号 “+”，进栈。如下图所示。
第三个字符是 “("，依然是符号，因其只是左括号，还未配对，故进栈。
第四个字符是数字 3，输出，总表达式为 9 3，接着是“-"，进栈。如下图所示。
接下来是数字 1，输出，总表达式为 9 3 1，后面是符号 “)”，此时，我们需要去匹配此前的 “(“，所以栈顶依次出栈，并输出，直到 “(” 出栈为止。此时左括号上方只有 “-”，因此输出 “-”。总的输出表达式为 9 3 1-。
紧接着是符号 “×”，因为此时的栈顶符号为 “+”，优先级低于 “×”，因此不能输出，“*” 进栈。接着是数字 3，输出，总的表达式为 9 3 1 - 3》如下图所示。
之后是符号 “+'，此时当前栈顶元素 “*” 比这个 “+” 的优先级高，因此栈中元素出栈并输出（没有比 “+” 号更低的优先级，所以全部出栈），总输出表达式为 9 3 1-3 * +。然后将当前这个符号 “+” 进栈。也就是说，前 6 张图的栈底的 “+” 是指中缀表达式中开头的 9 后面那个 “+”，而下图中左图中的栈底（也是栈顶）的 “+” 是指 “9+(3-1)×3+” 中的最后一个 “+”。
紧接着数字 10，输出，总表达式变为 9 3 1-3 * + 10。后是符号 “÷”，所以“/” 进栈。如下图中右图所示。
最后一个数字 2，输出，总的表达式为 9 3 1 - 3 * + 10 2。
因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为 9 3 1 - 3 * + 10 2 / +。如下图所示。

从刚才的推导中你会发现，要想让计算机具有处理我们通常的标准（中缀）表达式的能力，最重要的就是两步：

将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。
将后缀表达式进行运算得出结果（栈用来进出运算的数字）。

整个过程，都充分利用了栈的后进先出特性来处理，理解好它其实也就理解好了栈这个数据结构。

9. 总结

栈就是特殊的线性表，只不过对插入和删除操作做了限制。
栈（stack）是限定仅在表尾进行插入和删除操作的线性表。
它可以用线性表的顺序存储结构来实现，但存在着顺序存储的一些弊端。如果是两个相同数据类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化地利用数组的空间。
它也可以通过链式存储结构来实现，实现原则上与线性表基本相同。