数据结构:第二章 - 栈 587次阅读 数据结构 2022-07-18 目录 [TOC] ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 一、基本概念 栈是一种只能在一端进行插入或删除操作的线性表。允许进行插入删除操作的一端称为栈顶(Top),表的另一端为栈底。特点是先进后出。 栈是用来存储逻辑关系为 "一对一" 数据的线性存储结构。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit2/DS.Unit2.%281_1%29.png) ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit2/DS.Unit2.%281_2%29.png) ## **栈的具体实现** 栈是一种 "特殊" 的线性存储结构,因此栈的具体实现有以下两种方式: 1. 顺序栈:采用顺序存储结构可以模拟栈存储数据的特点,从而实现栈存储结构。 2. 链栈:采用链式存储结构实现栈结构。 > 两种实现方式的区别,仅限于数据元素在实际物理空间上存放的相对位置,顺序栈底层采用的是数组,链栈底层采用的是链表。 > ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 二、顺序栈 ## (一)基本知识 顺序栈,即用顺序表实现栈存储结构,将数顺序表(数组)的一端作为栈底,另一端为栈顶。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit2/DS.Unit2.%282.1_1%29.png) 设定一个实时指向栈顶元素的变量(一般命名为 top), * top 初始值为 -1,表示栈中没有存储任何数据元素,及栈是"空栈"。 * 一旦有数据元素进栈,则 top 就做 +1 操作。 * 反之,如果数据元素出栈,top 就做 -1 操作。 ### 1、顺序栈定义 ```c typedef struct { int data[maxsize];//存放栈中元素,maxsize是已定义存储结构最大值 int top;//栈顶指针 }SqStack;//顺序栈类型定义 ``` ### 2、状态 #### (1)栈空状态 ```c st.top == -1; ``` #### (2)栈满状态 ```c st.top == maxsize - 1 ; ``` #### (3)非法状态 栈满后继续入栈会出现上溢;栈空时继续出栈救护出现下溢。 ## (二)定义并初始化 ```c int stack[maxsize]; int top=-1; ``` ## (三)进栈 ```c stack[++top]=x;//x放到top变化后的位置上,即:top++;stack[top]=x; ``` ## (四)出栈 ```c x=stack[top--];//top从x变化前的位置上去掉,即:x=stack[top];top--; ``` ## (五)判断栈空 ```c int isEmpty(SqStack &st) { if(st.top==-1) return 1; else return 0; } ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 三、链栈 ## (一)基本知识 链栈,即用链表实现栈存储结构,将链表的头部作为栈顶,尾部作为栈底。 > 将链表头部作为栈顶的一端,可以避免在实现数据 "入栈" 和 "出栈" 操作时做大量遍历链表的耗时操作。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit2/DS.Unit2.%283.1_1%29.png) 链表的头部作为栈顶,意味着: * 在实现数据"入栈"操作时,需要将数据从链表的头部插入。 * 在实现数据"出栈"操作时,需要删除链表头部的首元节点。 ### 1、链栈结点定义 ```c typedef struct { int data;//数据域 struct LNode *next;//指针域 }LNode; ``` ### 2、状态 #### (1)栈空状态 ```c lst->next==NULL; ``` #### (2)栈满状态 不存在栈满的情况。 ### 3、初始化 ```c void initStack(LNode*&lst) { lst=(LNode*)malloc(sizeof(LNode));//建立头结点 lst->next=NULL;//下一个结点为空 } ``` ## (二)进栈 核心代码: ```c p->next=lst->next; lst->next=p; ``` 整体程序: ```c void push(LNode *lst,int x) { LNode *p; p=(LNode*)malloc(sizeof(LNode));//为进栈元素申请结点空间 p->next=NULL; /*头插法进栈操作*/ p->data=x; p->next=lst->next; lst->next=p->next; } ``` ## (三)出栈 核心代码: ```c p=lst->next; x=p->data; lst->next=p->next; free(p); ``` 整体程序: ```c int pop(LNode *lst,int &x) { LNode *p; if(lst->next==NULL) return 0; /*删除操作*/ p=lsat->next; x=p->data; lst->next=p->next; free(p); return 1; } ``` ## (四)判断栈空 ```c int isEmpty(LNode *lst) { if(lst->next==NULL) return 1; else return 0; } ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 四、表达式转换 ## (一)中缀-> 前缀 ```c void infixToPostFix(char infix[], char s2[], int &top2) { char s1[maxSize]; int top1 = -1; int i = 0; while(infix[i] != '\0') { if('0' <= infix[i] && infix[i] <= '9') { s2[++top2] = infix[i]; ++i; } else if (infix[i] == '(') { s1[++top1] = '('; ++i; } else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/' ) { if (top1 == -1 || s1[top1] == '(' || getPriority(infix[i]) > getPriority(s1[top1])) { s1[++top1] = infix[i]; ++i; } else s2[++top2] = s1[top1--]; } else if (infix[i] == ')') { while (s1[top1] != '(') s2[++top2] = s1[top1--]; --top1; ++i; } } while (top1 != -1) s2[++top2] = s1[top1--]; } ``` ## (二)中缀-> 后缀 因与上述 Code 相似度高,所以把不同处写在下边: 1. 将第 11、16、28、38 行的 “ ++i ” 改成 “ --i ” 。 2. 将第 13、15、24、35 行的 “ ( ” 改成 “ ) ” 。 3. 将第 33 行中的“ ) ” 改成 “ ( ” 。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 五、表达式求值 ## (一)共用函数 ```c int getPriority(char op) { if (op == '+' || op == '-') return 0; else return 1; } int calSub(float opand1, char op, float opand2, float &result) { if (op == '+') result = opand1 + opand2; if (op == '-') result = opand1 - opand2; if (op == '*') result = opand1 * opand2; if (op == '/') { if (fabs(opand2) < MIN)//fabs()是对其传入的数求绝对值;MIN是预先设置的宏, //无限接近0的正数;当fabs() getPriority(s2[top2])) { s2[++top2] = exp[i]; ++i; } else { int flag = calStackTopTwo(s1, top1, s2, top2); if (flag == 0) return 0; } } else if (exp[i] == ')') { while (s2[top2] != '(') { int flag = calStackTopTwo(s1, top1, s2, top2); if (flag == 0) return 0; } --top2; ++i; } } while (top2 != -1) { int flag = calStackTopTwo(s1, top1, s2, top2); if (flag == 0) return 0; } return s1[top1]; } ``` ## (三)前缀表达式求值 ```c float calPreFix(char exp[], int len) { float s[maxSize]; int top = -1; for (int i = len - 1; i >= 0; --i) { if ('0' <= exp[i] && exp[i] <= '9') s[++top] = exp[i] - '0'; else { float opnd1, opnd2, result; char op; int flag; opnd1 = s[top--]; opnd2 = s[top--]; op = exp[i]; flag = calSub(opnd1, op, opnd2, result); if (flag == 0) { puts("ERROR"); return 0; } s[++top] = result; } } return s[top]; } ``` ## (四)后缀表达式求值 ```c float calPostFix(char exp[]) { float s[maxSize]; int top = -1; for(int i = 0; exp[i] != ‘\0’; ++i) { if ('0' <= exp[i] && exp[i] <= '9') s[++top] = exp[i] - '0'; else { float opnd1, opnd2, result; char op; int flag; opnd2 = s[top--]; opnd1 = s[top--]; op = exp[i]; flag = calSub(opnd1, op, opnd2, result); if (flag == 0) { puts("ERROR"); break; } s[++top] = result; } } return s[top]; } ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 六、输出序列 ## (一)由出栈序列判断容量 通过入栈、出栈序列,去判断栈内容纳元素的最大数量,即栈容量。 ## (二)出栈顺序问题 入栈:1、2、3、……、n;出栈:p1、p2、……、pn。 1、若 p1 = n ,则 pi = n-i-1。 2、若 pi = n(1 p(i+1) > pn。 3、若 i < j < k ,pi、pj、pk 的大小关系中没有 pk < pi < pj。 栈不像队列一样必须按前后顺序出栈。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 七、共享栈 两个栈共享同一片存储空间,两个栈顶(s1、s2)分别是这篇存储空间的两端。 ## (一)初始化 ```c (1)方法1 int stack[maxsize]; int top1=-1,top2=maxsize; (2)方法2 int stack[maxsize]; int top[2]={-1,maxsize}; ``` ## (二)状态 ### 1、栈空 * s1:top[0] == -1 为真,则 s1 为空。 * s2:top[1] == maxsize 为真,则 s2 为空。 ### 2、栈满 * top[0]+1==top[1] 为真,则栈满。 ## (三)入栈 ```c (1)s1 stack[++top[0]]=x; (2)s2 stack[--top[1]]=x; ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 八、用栈模拟队列 需遵守以下规则 ## (一)入队 1、若 s1 未满,则元素直接入 s1。 2、若 s1 满,s2 空,则将 s1 中元素全部出栈并入 s2,腾出位置后再 s1。 ## (二)出队 1、若 s2 不空,则从 s2 中直接出栈。 2、若 s2 空,则将 s1 中元素全部出栈并入 s2,然后从 s2 中出栈。 ## (三)队满 s1 满且 s2 不空,则不能继续入队,即为队满状态。 ## (四)队空 s1 空且 s2 空,则队空。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 九、括号匹配和计算 ## (一)匹配 ```c int isMatched(char left, char right) { if (left == '(' && right == ')') return 1; else if (left == '[' && right == ']') return 1; else if (left == '{' && right == '}') return 1; else return 0; } int isParenthesesBalanced(char exp[]) { char s[maxSize]; int top = -1; for (int i = 0; exp[i] != '\0'; ++i) { if (exp[i] == '(' || exp[i] == '[' || exp[i] == '{') s[++top] = exp[i]; if (exp[i] == ')' || exp[i] == ']' || exp[i] == '}') { if (top == -1) return 0; char left = s[top--]; if (isMatched(left, exp[i]) == 0) return 0; } } if (top > -1) return 0; return 1; } ``` ## (二)计算 ```c int calF(int m) { int cum = 1;//用于存储累乘的最终结果,累加为0 int s[maxSize], top = -1; while (m != 0) { s[++top] = m;//此两行,具体问题具体分析 m /= 3; //此两行,具体问题具体分析 } while (top != -1) cum *= s[top--]; return cum; } ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 参考资料 > **版权声明**:个人学习记录,本博客所有文章均采用 CC-BY-NC-SA 许可协议。转载请注明出处!若有侵权,请留言联系! > > * 2022 天勤计算机考研高分笔记-数据结构 > * 2022 王道计算机考研复习指导-数据结构 > * 解学武数据结构与算法教程(C 语言版):http://data.biancheng.net/ 如果您觉得文章对您有帮助,请点击文章正下方的小**红心**一下。您的鼓励是博主的最大动力! 2 最后一次更新于2022-10-23 数据结构
0 条评论