数据结构栈和队列笔记(数据结构栈和队列知识点总结)
导语：数据结构栈与队列之作死攻略
先看个漫画放松下
目录
1 栈是啥？2 栈的实现方式2.1 顺序栈（Array-based Stack）2.2 链式栈（Linked Stack）2.3 共享栈2.4 栈的应用-四则运算表达式求值2.3.1 后缀表达式后缀表达式：运算符号位于两个运算数之后。
用堆栈实现后缀表达式求值：
运算数：入栈运算符：从栈中弹出最前的两个数，计算并将结果入栈栈顶上的元素就是表达式的结果值例：
漫画乱入，纯属娱乐。
2.3.2 中缀表达式中缀表达式：运算符号位于两个运算数之间。
中缀表达式求值：将中缀表达式转换为后缀表达式，然后求值。
中缀表达式转换为后缀表达式：
从头到尾读取中缀表达式的每个对象运算数：直接输出左括号：压入堆栈右括号：将栈顶的运算符弹出并输出，知道遇到左括号（出栈，括号不输出）运算符：若优先级大于栈顶运算符时，把它压栈若优先级小于栈顶运算符时，将栈顶运算符弹出并输出，而它进栈若各对象处理完毕，则把堆栈中存留的运算符一并输出2 队列2.1 队列是啥？2.2 队列的实现方式2.2.1 顺序队列例子：假设现在顺序队列Q分配了6个空间
(1) 开始时为空队，Q.front=Q.rear
(2) 元素a1进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位
(3) 元素a2进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位
(4) 元素a3，a4，a5分别按顺序进队，尾指针Q.rear依次后移
(5) 元素a1出队，头指针Q.front（整型下标）后移一位
(6) 元素a2出队，头指针Q.front（整型下标）后移一位
(7) 元素a6进队，放入尾指针rear（整型下标）的位置，rear后移一位
(8) 元素a7进队，此时尾指针Q.rear已经超过了数组的下标，无法再存储进队，但是我们发现前面明明有2个空间，却出现了队满的情况，这种情况称为。
2.2.2 循环队列上面第（7）步元素a6进队之后，尾指针Q.rear要后移一个位置，此时已经超过了数组的下标，即Q.rear+1=Maxsize（最大空间数6），那么如果前面有空闲，Q.rear可以转向前面0的位置
然后元素a7进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位
元素a8进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位
这时候虽然队列空间存满了，但是出现了一个大问题，队满时Q.front=Q.rear，这和队空的条件一模一样，无法区分队空还是队满，如何解决呢？有两种办法：一是设置一个标志，标记队空和队满；另一种办法是浪费一个空间，当尾指针Q.rear的下一个位置Q.front是时，就认为是队满。如图所示：
上述到达尾部又向前存储的队列称为循环队列，为了避免，我们通常采用循环队列。
循环队列无论入队还是出队，队尾、队头加1后都要取模运算，例如入队后队尾后移一位：Q.rear =(Q.rear+1)%Maxsize。
为什么要%Maxsize呢？
主要是为了处理临界状态，即Q.rear向后移动一个位置Q.rear+1后，很有可能超出了数组的下标，这时它的下一个位置其实是0，如果将一维数组画成环形图，如图所示：
上图中最大空间Maxsize，当Q.rear=Maxsize-1时，(Q.rear+1)%Maxsize=0，而且Q.front=0，正好满足队满的条件：(Q.rear+1) %Maxsize= Q.front，此时为队满。
因此无论是front还是rear向后移动一个位置时，都要加1与最大空间Maxsize取模运算，处理临界问题。
总结：
队空：Q.front=Q.rear; // Q.rear和Q.front指向同一个位置
队满： (Q.rear+1) %Maxsize=Q.front; // Q.rear向后移一位正好是Q.front
入队：
Q.base[Q.rear]=x; //将元素放入Q.rear所指空间
Q.rear =( Q.rear+1) %Maxsize; // Q.rear向后移一位
出队：
e= Q.base[Q.front]; //用变量记录Q.front所指元素
Q.front=(Q.front+1) %Maxsize // Q. front向后移一位
循环队列中包含的元素个数：
2.2.3 链式队列2.2.4 双端队列双端队列可以在队列任意一端入队和出队。将队列的两端分别称为前端和后端。
（1）输出受限的双端队列
允许在一端进行入队和出队，在另一端只允许入队。
（2）输入受限的双端队列
允许在一端进行入队和出队，在另一端只允许出队
漫画乱入，甭管我。
2.3 队列的应用2.3.1 队列在计算机系统中的应用参考自：
张铭《数据结构与算法》
陈越，何钦铭《数据结构》
程杰《大话数据结构》
邓俊辉《数据结构》
本文内容由小薇整理编辑！