hello,everybody. 我们又见面了，这次我们一起来学习数据结构中，非常有意思的两种结构—Stack ,Queue.
首先来学习一下栈:
栈:限定只在表尾进行删除插入操作的线性表。
顾名思义，栈是一种特殊的线性表。它特殊在什么地方呢？它只能在表尾进行插入或删除操作，又就意味着，它只能是先进后出。给大家举个现实中，利用栈的例子。我们都用浏览器浏览过网页，我们对浏览器的前进后退按钮一定都不陌生。当我们打开第一个网页时，有一个图片链接，于是我们又跳到了第二个网页。此时，又有一个文字链接，我们又跳到了第三个网页。此时，我点击浏览器的后退按钮，我们会回到第二个网页。再点击浏览器的后退按钮，我们又跑到了第一个网页。是不是最先打开的第一个网页，是最后一个恢复的？是不是，先进后出？
看来，我们在学习第二章线性表时，付出的心血没有白费。看看，我在学习栈与队列时，感到很轻松，因为它讲的一些概念，我都掌握了。所以，我们在学习知识时，一定要踏实，耐心。付出一定会有回报的，你用心付出，回报巨大，回报明显。你不用心付出，回报微小，回报不明显。你不付出，只是随意看看，那么当别人说起这些知识时，你也可以装下B。所以，付出是有回报的。只是为了，回报巨大，回报明显，我们需要用心，态度要端正。
我们把允许删除的一端称为栈顶（Top）,另一端称为栈底（Bottom）.不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表。大家需要注意了，我们说，栈是限定了，只能在表尾进行删除插入操作的线性表。这里所说的表尾，是指栈顶，而不是栈底。
栈的插入操作，叫作进栈，栈的删除操叫做出栈。如下图:
栈的抽象数据类型:
既然栈也是线性表，那么我们上章所学的线性表操作，也同样适用于栈。那么，栈也同样有顺序存储，与链式存储的存储方式。
栈的顺序存储结构：
我们在学习线性表的顺序存储时，我们是用数组来表示的。对于栈的顺序存储，我们同样可以用数组来表示。那么大家思考一下，我们用哪头来表示栈顶，哪头来表示栈底呢？
因为，插入、删除操作都是在栈顶进行。相对于栈顶，栈底是比较”安静的”，比较稳定。那么，我们就用下标为0的位置，来定义我们的栈底。大家看下图:
我们用Top来指向栈顶元素所在数组的下标，这个Top就相当于游标卡尺的游标。游标可以变大变小，意味着我们的Top可以变大表小，但是再怎么变，它也不能超过游标卡尺的长度。Top，不能超过我们的数组长度。当栈存在一个元素时，我们定义Top指向0.当栈为空时，我们定义Top指向-1.
栈的结构定义:
进栈操作:
Status Push(SqStack *S,SElemType e)
{
if(S->top==MAXSIZE-1) /*栈满*/
return ERROR;
S->top++;
S->data[S->top]=e;/*将元素e添加栈顶空间*/
return ok;
}
出栈操作:
Status Pop(SqStack *S,SElemType *e)
{
if(S->top==-1)
return ERROR;
*e=S->data[S->top];/*将栈顶元素赋值给e*/
S->top—;
return ok;
}
两者没有涉及任何的循环操作，所以时间复杂度为O【1】.
其实，栈的顺序存储还是很方便的。因为它只允许在表尾进行删除插入操作，不必移动其他元素。但是它有一个很大的不足，我们事前必须清楚数组的大小，给少了，溢出。给多了，浪费。
两栈共享空间:
对于两个相同类型的栈，我们可以把他们结合起来，用一个数组来存储。充分利用数组的空间，提高效率。数组有两个端点，栈也有两个断点。我们可以用数组下标为0的位置，存放栈的栈底。数组下标为n-1的位置，存放另一个栈的栈底。这样两个栈如果插入元素，就是从数组两端向中间插入数据。如下图:
这样，我们就充分利用了数组的空间。大家可以发现，Top1是栈1的栈顶指针，Top2是栈2的栈顶指针。只要Top1与Top2不见面，两栈就可以一直使用。那么当栈1为空栈时，Top1=-1.栈2为空栈时，Top2=n。那么什么时候栈满呢？
想想极端情况，栈2为空栈。当Top1=n-1时，栈1为满栈。栈1为空栈时，Top2=0时，栈2为满栈。但是，更多的时候，是Top1与Top2见面时。也就是它们相差1.Top1+1=Top2.
下图是两栈共享空间结构
插入元素e为新栈顶元素:
Status Push(SqDoubleStack *S,SElemType e, int StackNumber)
{
if(S->top1+1==S->top2)/*栈满了*/
return ERROR;
if(StackNumber==1)/*栈1有元素进栈*/
S->data[++S->top1]=e;/*Top1+1,把e赋值给栈顶元素*/
else if(StackNumber==2);/*栈2有元素进栈*/
S->data[--S->top];/*Top—,把e赋给栈2的栈顶元素*/
}
出栈操作：
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
{
if(stackNumber==1)
{
if(S->top1==-1)/*栈1为空栈*/
return ERROR;
*e=S->data[S->top1—];
}
else if(stackNumber==2)
{
if(S->Top2==Maxsize)/*栈2为空栈*/
return ERROR;
*e=S->data[S->top2++];
}
return ok;
}
栈的链式存储结构及定义:
好了，我们来学习一下栈的链式存储结构吧，简称链栈。
因为链表有头指针，而栈又有栈顶指针，那么为何不让它们合二为一呢？所以，我们通常将头结点定义为栈顶。因为已经有了栈顶在头部了，头结点作用就不大了。所以，对于链栈，是不需要头结点的。
对于空表来说，原来的链表是头指针指向空，那么链栈的空其实就是Top=NULL的时候。
链栈的结构代码如下图:
链栈的插入:
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;
}
/*链栈的删除*/
Status Pop(LinkStack *S,SElemType *e)
{
LinkStackPtr p;
if(StackEmpty(S))
return ERROR;
*e=S->top->data;
p=S->top;
S->top=S->top->next;
free(p);
S->count—;
return OK;
}
大家可以发现，链栈的入栈与出栈的算法，都没有循环语句，时间复杂度都是O【1】.我们可以发现，顺序存储的栈与链式存储的栈，他们的时间性能都是一样的。不同的是，空间性能上。线性栈，需要事前给出固定长度，这就可能造成内存空间浪费的可能。但是，线性栈，存取时定位很方便。而链式存储虽然不用事前分配固定大小，但是每个元素必须开辟指针域，这也造成了空间的消耗。线性栈与链栈与线性表与链表是一样的，当我们的元素变化比较大时，建议使用链栈，否则使用线性栈。
栈的作用:
大家可能会有疑问，既然栈也是一种线性表。那么我们已经有了线性表，为什么还要学习栈呢？李白说过:”天生我材必有用”。存在即合理，既然有这种数据结构，就一定有它的用武之地。线性表相当于我们的脚，理论上我们用脚可以走遍地球上 任何地方。但是，从北京到上海，我们是选择用脚走，还是乘交通工具呢？栈，就相当于飞机、火车、汽车等交通工具。它的出现，是为了简化程序的设计，使我们把精力全部放在问题本身上。是不是不好理解啊，呵呵，没事儿的，我们一起来看看栈的实际用途吧。
栈的应用：
栈的一个重要应用，就是实现了程序设计语言的递归操作。什么是递归呢？通过学习一个经典的算法来了解递归的含义吧。
斐波那契(Fibonacci)数列实现:
1 1 2 3 5 8 13 21……..
前面相邻的两项的和，构成了后面的项。像这样的数列，就叫做斐波那契数列。首先，我们设计一个算法实现这个斐波那契数列。
void Fibonacci()
{
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[i]);
}
}
运行结果:
我们设计的这个算法，是利用迭代功能实现的，我们将这个利用迭代实现斐波那契算法成为迭代斐波那契。
现在，我们再来看看利用递归实现斐波那契的算法。
int Fbi(int i)
{
if(i<2)
return i==0?0:1;
return Fbi(i-1)+Fbi(i-2);
}
运行结果:
两种算法，结果是一样的。大家可以观察研究一下这两个算法，通过观察，我们发现利用递归斐波那契算法要比迭代斐波那契算法干净，简洁。所谓的递归，不过是一直在调用自己。那么我们就好了递归的含义.
递归:我们把一直调用自己或通过一系列语句间接地调用自己的函数，称为递归。
设计递归算法时，最怕的就是陷入无限的调用中。所以，我们会给出一个条件，当递归函数满足这个条件时，结束递归调用。这也是，这两个算法的不同点。迭代算法，递归算法，说白了，前者是使用循环结构，而后者使用选择结构。递归算法，使得代码简洁，易懂，减少了理解代码的时间。但是，会创建多个函数副本，会耗费大量的时间和内存。迭代则不用反复调用函数和占用额外的内存。
因此，我们要根据实际情况来选择不同的代码实现方式。
那么，讲这么多，递归跟栈到底有什么关系呢？大家可以发现，递归是一层层的在调用函数，我们把调用函数想象成栈的入栈，我们把参数、调用地址都压入栈中。当满足判断条件时，我们在将位于栈顶的参数、调用地址弹出栈中。这样，函数就会一层一层的返回，直至最先调用的函数。这样大家是不是就明白了，栈是如何实现递归的吧。
栈还有一些其他应用:
栈的现实应用还有很多，我们来学习一下用的比较多的一个应用:四则运算表达式。
我们都用过高级计算器，它的高级之处是，可以进行带括号的四则运算。那么计算器内部是如何实现的呢？就是利用栈这个数据结构实现的，一起来学习一下吧。
后缀表示法:
首先，我们要先了解一下后缀表示法。波兰逻辑学家,想到了一种不需要括号的后缀表达法，我们称为后缀表示法。称为后缀表示法，是因为运算符全在要计算数字的后面。例如,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 * +
第十一个字符为10，输出10 .9 3 1 – 3 * + 10
第十二个字符为/，因为栈顶元素为+,比/运算级别低，所以/进栈。如上图右.
第十三个字符为2，输出2.
没有字符了，所以栈内符号依次 输出。
最终输出为9 3 1 – 3 * + 10 2 / +
以上就是中缀法转后缀法。
我们有了后缀法的表达式，就可以让计算机来计算了。那么计算机是如何计算的呢？
后缀表达式计算结果:
规则，从左到右依次遍历后缀法表达式，遇到数字就进栈，遇到符号，就将栈内头两个数字出栈进行计算，计算结果再入栈，直到结算完为止。我们就拿9+(3-1)*3+10/2的后缀法9 3 1 – 3 * 10 2 / +来练习。
前三个字符分别为9 3 1，依次入栈。如下图:
第四个字符为-，栈内头两个数字出栈，计算结构入栈。1、3 出栈。执行3-1 结果 2 入栈。
第五个字符3 入栈 。如下图:
第六个字符*，栈内数字3、2出栈。执行2*3，结果6入栈。如下图:
第7个字符+,6、9出栈，执行9+6,结果15入栈。如上图右。
第八、九字符分别为10 ，2依次入栈。
第10字符为/，10 2 出栈，执行10/2 结果5入栈，如下图:
第十一个字符为+，栈内数字5 15 出栈，执行15+5 结果20.入栈
因为是最后一个字符，所以20出栈，栈为空。20是最终的计算结果。如下图:
计算机就是这样执行四则运算的，到这里，你应该能明白栈、线性表同样是线性表，为什么又要学习栈了。
好了，这就是栈全部内容，休息一下，我们再来学习队列。