限定头的一种线性表（是一种逻辑结构）、只能在一端操作——插入或删除。
存储结构：
（1）顺序栈：（默认top所指位置为当前元素位置）初始化S.top=-1（栈空）
栈顶元素是S.data[S.top]（top指向栈顶元素）
进栈（push）先移动top，后传值：S.data[++S.top]=x;
出栈（pop）先取值，后移动top：x=S.data[S.top--];
共享栈满条件top2-top1=1时
共享栈（2）链式栈：通常用单链表实现，并且规定所有操作都在表头进行二、栈选择题判断技巧（1）抓住第一个出栈的元素，第一个入栈元素之前的元素相对位置一定不变。如：入栈顺序为abcde，求第一个出栈字母是d的可能出栈的循序序列
解：
我们第一个出栈元素是d
d←top
c
b
a
在d出栈时，cba已经被push进栈了,所以cba的相对顺序是无法改变的。
即可能的序列：
decba
dceba
dcbea
dcbae
所以得出结论：Xi出栈,Xi前未出栈元素一定逆置有序
（2）容量问题（手动模拟，选择栈容量可以达到最少的时候）（3）I（进栈）O（出栈）的合法性判断思想：在扫描的时候每一步都判断Count（I）=Count（O）
IOOIOIIO
×
第三个O的时候，已经没有元素在栈中了，所以这个进栈出栈序列是错误的
（4）对于n个不同的元素进栈，出栈序列个数为（卡特兰数）PS：在判断已知前序序列，中序序列有多少种情况？
（不懂没关系，这个考的不多）
前序序列和中序序列的关系相当于以前序序列入栈次序，中序为出栈次序（卡特兰数）
三、栈的应用（1）回文判断：把一半的元素放出栈中，然后将链表前一半元素依次出栈，边出栈（pop）边与后一半进行比较。（奇数时，中间不用比较）
（2）括号匹配：
算法思想:
①初始化设置一个空栈，顺序读人括号
②若是右括号“）”，消除置于栈顶的“（”消解，否则不合法。
③若是左括号“（”，则作为一个新的更急迫的期待压入栈中。
算法结束时：栈空success否则fail
（3）表达式求值：
中缀表达式转后缀表达式：从左往右扫→
①若当前op栈顶op压栈push
②若当前op=栈顶op出栈pop
③直到中缀表达式扫描完毕，若操作符栈中还有元素依次出栈输出到后缀表达式中
PS:同理中缀转前缀从右往左←
把判断条件①的“”换成“=”，把判断条件②的“=”换成“”
（4）计算后缀表达式（年考了选择题）
①从左到右扫描后缀表达式，如果是操作数压栈，如果是操作符（op）就弹出两个操作数（后弹出的是第一个操作数，先弹出的是第二个操作数）
②操作符操作，生成新的数压栈push
③直到后缀表达式扫描完毕，这时栈中只有一个元素，即所求。
四、队列（先进先出）一种只能在表的一端插，另一端删除的单链表
（1）
1.顺序存储结构：front指向队头，rear指向队尾元素的下一个位置（具体题目具体分析）
2.循环队列（不循环会有假溢出）：①利用“%”来实现循环，所有操作都+"%MaxSize"
②初始：Q.front=Q.rear=0;
出队：队首+1：Q.front=（Q.front+1）%MaxSize
入队：队尾+1：Q.rear=（Q.rear+1）%MaxSize
队列长度：（Q.rear+MaxSize-front）%MaxSize
队空：Q.front==Q.rear
队满：（Q.rear+1）%MaxSize==Q.front
（还有一些情况：牺牲一个单元来区分队空和队满的情况，了解书上的其他方法Q.size()，Q.tag）
（2）链式存储结构：头指针指向头结点，尾指针指向队尾结点一般设头结点（不存数）比较方便，可以统一插入和删除操作（跟链表一样）
PS:注意出队时只有一个结点的时候，要把Q.rear=Q.front（即修改尾指针，具体看辅导书课本）
（3）双端队列：（会手工模拟就行，而且不是重点）
1.输出受限（只能在一端出队）：
做题思路：因为出队确定，所以观察模拟其能不能有题中入队的情况（结合下图看）
输出受限2.输入受限（只能在一端插入）
做题思路：入队确定，所以观察模拟能不能有题中的出队情况（结合下图看）
输入受限五、队列的应用（1）二叉树的层次遍历，图的广度优先搜索
（2）缓冲区（主机或外部设备），就绪队列（多用户资源竞争）等。
来源于网络
赞赏