数据结构第二周笔记——线性结构(慕课浙大版本--XiaoYu)中

2.2.1 什么是堆栈

计算机如何进行表达式求值？

由两类对象构成的：

1. 运算数，如2、3、4
   
2. 运算符号,如+、-、*、/
   

不同运算符号优先度不一样

后缀表达式：运算符号位于两个运算数之后。如abc*+de/-

中缀表达式：运算符号位于两个运算数之间。如a+b*c-d/e

两个表达式其实是同一个意思

还有一种表达式叫“前缀表达式”，即运算符号位于运算数之前,比如a+bc的前缀表达式是+abc。

你能写出a+bc-d/e的前缀表达式吗？正确答案：-+abc/de

【例】6 2 / 3 - 4 2 * + = ？   =>   先遇到6然后2接着是/，组成式子得到3，再遇到3然后再遇到-组成式子3-3=0，0接着遇到4跟2然后是*，4 * 2 = 8，然后目前是有0跟8，接着遇到+，相加为8

后缀表达式求值策略：从左往右"扫描"，逐个处理运算数和运算符号

1. 遇到运算数怎么办？如何"记住"目前还未参与运算的数？
   
2. 遇到运算符号怎么办？对应的运算数是什么？
   
3. 启示：需要有种存储方法，能顺序存储运算数，并在需要时"倒序"输出！
   
4. 先放进去的后拿出来，后放进去的先拿出来做运算  =>这就是堆栈
   
5. T(N) = O(N)
   

堆栈的抽象数据类型描述

堆栈(Stack):具有一定操作约束的线性表

1. 只在一端(栈顶，Top)做插入、删除
   
2. 插入数据：入栈(Push)
   
3. 删除数据：出栈(Pop)
   
4. 后入先出：Last In First Out(LIFO) 这是特点
   

数据对象集(堆栈)：一个有0个或者多个元素的有穷线性表

操作集(堆栈)：长度为MaxSize的堆栈S 属于Stack，堆栈元素item 属于ElementType

1.StackCreateStack( intMaxSize)：生成空堆栈，其最大长度为MaxSize;

2.intIsFull(StackS,intMaxSize)：判断堆栈S是否已满;

3.voidPush(StackS, ElementTypeitem )：将元素item压入堆栈;(重点)相当于插入操作，需要判别堆栈有没有满或空

4.intIsEmpty(StackS)：判断堆栈S是否为空;

5.ElementTypePop(StackS)：删除并返回栈顶元素;(重点)相当于删除操作，需要判别堆栈有没有满或空。空了就不能删除了

Push和Pop可以穿插交替进行;

按ABC顺序入栈，可以产生CAB这样的出栈序列？不可以，是CBA序列

Push：推(压入)

Pop：弹出

2.2.2 堆栈的顺序存储实现

栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成

#define MaxSize <存储数据元素的最大个数>

typedefstructSNode*Stack;

structSNode{

   ElementTypeData[MaxSize];

   intTop;//用来指示栈顶的位置，Top不是地址而是一个整型变量，代表了栈顶位置它的数组下标在哪里

};

//(1)入栈

voidPush (StackPtrS, ElementTypeitem)//包含两个参数，一个是堆栈本身，一个是用指针表示PtrS(Stack类型指针，Stack本身就是堆栈的意思)

{

   if( PtrS->Top==MaxSize-1 ){//入栈需要判断堆栈满了没有，满了就不能再加了，有极限的。下标从0开始，所以到MaxSize-1就已经满了

       printf("堆栈满") return;

   }else{

       PtrS->Data[++(PtrS->Top)] =item;//item放在Top上面的一个位置，这一个语句实际做了两个事情，一是把item放到Top+1这个位置上，同时把Top值加实现了入栈的操作

       return;

   }

}

//(2)出栈

ElementTypePop(StackPtrS)

{

   if(PtrS->Top==-1 ){

       printf("堆栈空");//一样的操作，出栈之前要检查以下是不是空了，空了可就没东西往外掏了

       returnERROR;//ERROR是ElementType的特殊值，标志错误

   }else{

       return(PtrS->Data[(PriS->Top)--]);

   }

}

【例】请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功

//简单将把数组对分的话来做两个堆栈会有一个问题：有一个堆栈满了，但另一个堆栈是空的，还有空余空间

//要求是数组还有空余空间，就允许有入栈操作

//用法就是一个从最左边往里放，另一个从最右边往里放。中间就是空余的大家都可以用

//根据刚才讲的方法，用一个数组来表示双堆栈，如果这两个堆栈的栈顶位置分别是top1和top2，那么可以用top1+top2==MaxSize(数组大小）来判别堆栈是否满？不可以

//因为top1跟top2代表的是数组的下标，所以top1代表的距离是中间空余的位置＋top2，top2也是同理

//正确的分析：使这两个栈分别从数组的两头开始向中间生长；当两个栈的栈顶指针相遇时，表示两个栈都满了

   #define MaxSize<存储数据元素的最大个数>

   structDStack{

       ElementTypeData[MaxSize];

       intTop1;//堆栈1的栈顶指针

       intTop2;//堆栈2的栈顶指针

   }S;

   S.Top1=-1;//这是堆栈1空的位置

   S.Top2=MaxSzie;//堆栈2空的位置，数组最后一个位置是MaxSize - 1

//Push(弹出)具体操作

voidPush (structDStack*PtrS,ElementTypeitem,intTag )

{

   //Tag作为区分两个堆栈的标志，取值为1和2，Tag的值1和2分别代表第一个堆栈跟第二个堆栈

   if( PtrS->Top2-PtrS->Top1==1){

       printf("堆栈满"); return;

   }

   if( Tag==1)//对第一个堆栈操作

       PtrS->Data[++(PtrS->Top1)] =item;//Top1后面一个位置

   else//对第二个堆栈进行操作

       PtrS->Data[--(PtrS->Top2)] =item;//Top2前面一个位置

}

//Pop(压入)操作

ElementTypePop (structDStack*PtrS,intTag )

{

   //Tag作为区分两个堆栈的标志，取值为1和2，Tag的值1和2分别代表第一个堆栈跟第二个堆栈

   if( Tag==1){//对第一个堆栈进行操作

       if( PtrS->Top1==-1){//堆栈1空

           printf("堆栈1空"); returnNULL;

       }else {

           returnPtrS->Data [(PtrS->Top1)--];

       }

   }else{//对第二个堆栈操作

   if( PtrS->Top2==MaxSize){//堆栈2空

       printf("堆栈2空"); returnNULL;    

   }else{

    returnPtrS->Data[(PtrS->Top2)++];  

   }

}

以下部分是百度内容(对堆栈的总结)

堆栈严格来说应该叫做栈（stack），先入后出

四种类型：满增栈、满减栈、空增栈、空减栈。

 

满、空栈区别：根据当前指针所在位置是否有东西。

满栈（full stack）：栈指针指向最后压入栈的数据，数据入栈时，sp先减一（或加一）再入栈。

空栈（empty stack）：栈指针指向下一个将要放入数据的位置，数据入栈时，先入栈sp再减一（或加一）。

 

增、减栈区别：根据堆栈的生成方向不同。

递增堆栈(ascending stack)：堆栈由低地址向高地址生长。

递减堆栈(secending stack)：堆栈由高地址向低地址生长。

 

总结：

 

满栈进栈是先移动指针再存；

满栈出栈是先出数据再移动指针；

空栈进栈先存再移动指针；

空栈出栈先移动指针再取数据。

2.2.3 堆栈的链式存储实现

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能再链栈的栈顶进行。

栈顶指针Top应该再链表的哪一头？若用单向链表实现一个堆栈，链表的头和尾都可以作为top？

只有链表的头才行。链表的尾空余插入，但是删除就有问题，找不到前面的结点了，因为这是单项链表找不到前面的结点

   

   typedefstructSNode*Stack;

   structSNode{

       ElementTypeData;

       structSNode*Next;

   };

StackCreateStack()

{//构建一个堆栈的头结点，返回指针

   StackS;

   S= (Stack)malloc(sizeof(structSNode));

   s->Next=NULL;

   returnS;

}

intIsEmpty(StackS)

{

   //判断堆栈s是否为空，若为空函数返回整数1，否则返回0

   return (S->Next==NULL);

}

voidPush(ElementTypeitem,StackS)

{

   //将元素item压入堆栈S

   structSNode*TmpCell;

   TmpCell= (structSNode*)malloc(sizeof(structSNode));

   TmpCell->Element=item;

   TmpCell->Next=S->Next;

   S->Next=TmpCell;

}

使用链表来进行Push操作的时候不用判别堆栈满不满的问题，因为链表通过不断申请结点空间往里面插

数组实现堆栈的话，数组大小是固定的，存在着满不满的问题

ElementTypePop(StackS)

{

   //删除并返回堆栈s的栈顶元素

   structSNode*FirstCell;

   ElementTypeTopElem;

   if( IsEmpty (S) ){

       printf("堆栈空");returnNULL;

   }else{

       FirstCell=S->Next;

       TopElem=FirstCell->Element;

       free(FirstCell);

       returnTopElem;

   }

}

2.2.4 堆栈应用：表达式求值

回忆：应用堆栈实现后缀表达式求值的基本过程：

1. 从左到右读入后缀表达式的各项(运算符或运算数);
   

1.运算数：入栈;

2.运算符：从堆栈中弹出适当数量的运算数，计算并结果入栈;

3.最后，堆栈顶上的元素就是表达式的结果值

中缀表达式求值

基本策略：将中缀表达式转化为后缀表达式，然后求值

如何将中缀表达式转化为后缀？

观察一个简单例子：2+9/3-5  ->  2 9 3 / + 5 -

1.运算数相对顺序不变

2.运算符号顺序发生改变

   1.需要存储"等待中"的运算符号

   2.要将当前运算符号与"等待中"的最后一个运算符号比较(如果前面的一个运算符号的优先级比我来得高，就说明可以拿来计算，如果优先度比我低，那么当前的运算符号还不能说就直接拿来运算，因为后面可能还有优先级比我高的，所以需要保留起来，这个时候我们就需要一种结构来实现我们运算符号的存储，那结构就是堆栈)

       输出：2 9 3

       记下：+ /

       碰到运算数 我们就把它输出

       碰到运算符号 我们等着

       

有括号怎么办？

【例】a*(b+c)/d = ?        a b c + * d /

当括号被丢进堆栈里面的时候，它的优先级降到最低，优先算括号里的内容

算数规则：当遇到同一个优先级的时候，它的顺序是从左到右

T(N) = O(N)

请试试应用堆栈将中缀表达式2*(6/3+4)-5转换为后缀表达式。在这个转换过程中，堆栈元素最多时元素个数是多少？3个

中缀表达式如何转换为后缀表达式

从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。

1.运算数：直接输出

2.左括号：压入堆栈

3.右括号：将栈顶的运算符弹出并输出，直到遇到左括号(出栈，不输出);

4.运算符：

   1.若优先级大于栈顶运算符时，则把它压栈;

   2.若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出;再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈;

5.若各对象处理完毕，则把堆栈中存留的运算符一并输出

堆栈的其他应用：

函数的调用及递归实现

深度优先搜索(图)

回溯算法(老鼠走迷宫案例)等等