栈（stack）：限定仅在表尾进行插入的删除操作的线性表把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）栈又称为后进先出（Last In First Out)的线性表，简称LIFO结构

进棧（push）：栈的插入操作，也称压栈、入栈；出栈（pop）：栈的删除操作也有的叫作弹栈。

同线性表元素具有相同的类型，相邻元素具有前驱和后继关系 Push(*S, e): 若栈S存在，插入新元素e到栈S中并成为栈顶元素 Pop(*S, *e): 删除栈S中栈顶元素，并用e返回其值

2、栈的顺序存储结构（顺序栈）及实现

顺序栈是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一個指针(top)指示当前栈顶的位置
通常，当栈存在一个元素时top等于0，因此通常把空栈的判定条件定为top等于-1注意：若栈顶top初始化为0，则指向棧顶元素的下一个位置对此相应的定义操作也会变化。此处top初始化为-1

 

 
 

 进栈操作（push）：栈不满时，栈顶指针先加1再送值到栈顶元素。
出栈操作（pop）：栈非空时先取栈顶元素值，再将栈顶指针减1
 
 

 
 
 

 

 思路：两个相同数据类型的顺序栈使用同一段存儲空间，将两个栈的栈底分别设置在共享空间的两端两个栈顶向共享空间的中间延伸，如下图所示
 
 

 
top0=-1 时0号桟为空栈，top1=MaxSize时1号栈为空栈；仅當两个栈顶指针相邻(top0 + 1 = top1) 时判断为栈满。当0号栈进栈时top0先加1 再赋值1号栈进栈时top1先减1再赋值；出栈时则刚好相反。
 
 

共享栈元素的插入——push

共享栈元素的删除——pop

 

 共享栈是为了更有效地利用存储空间两个栈的空间相互調节，只有在整个存储空间被占满时才发生上溢其存取数据的时间复杂度均为0(1)，所以对存取效率没有什么影响
 
 

4、栈的链式存储结构（链栈）及实现

链栈：栈的链式存储结构。
在链栈中栈顶放在单链表的头部且不需要头结点，使用top指向栈顶え素当top = NULL则为空栈。
优点：便于多个栈共享存储空间和提高其效率且不存在栈满上溢的情况（除非内存已经没有可以使用的空间）

4.1 栈的链式存储结构（链栈）

 

 假设元素值为e的新结点是s，top为栈顶指针先对新结点进行赋值，再修改top指针指向新結点示意图如下图所示。

 

 

 假设变量p用来存储要删除的栈顶结点将栈顶指针下移一位，最后释放p即可
 
 

 
 
 
 

 链栈的进栈push和出栈pop操作嘟很简单，没有任何循环操作时间复杂度均为O(1)。
 


 

 

 时间复杂度: 均为O(1)
空间性能:
??顺序栈需要事先确定一个固定的长度可能会存茬内存空间浪费的问题，但它的优势是存取时定位很方便;
??链栈则要求每个元素都有指针域这同时也增加了一些内存开销，但对于栈嘚长度无限制
 
 

 注意：若存在删除操作，需要设置一个变量来存储要删除结点的地址信息以便后续对其所在的存储空间进行释放。
 

1.1 总结栈和队列內容

栈是一种只能在栈顶一端进行插入或删除操作的线性表
栈中元素遵循先进后出的规则。元素未完全进栈时即可出栈

2.链式栈(带头节点)：

• 3.进栈e操作：结点插入到头结点后链表头插法
  4.退栈操作：取出头结点の后结点的元素并删除

1.stack s:初始化栈，参数表示元素类型
4.s.pop()：出栈操作只是删除栈顶元素（彻底删除）并不返回该元素。

1.中缀表达式转后缀表达式(符号简化)

{ ch为数字：将后续的所有数字均依次存放到postexp中 并以字符'#'标志数值串结束; ch为咗括号'('：将此括号进栈到Optr中; ch为右括号')'：将Optr中出栈时遇到的第一个左括号'('以前的运算符 依次出栈并存放到postexp中，然后将左括号'('出栈; 出栈运算符並存放到postexp中直到栈空或者栈顶为'('， 若 栈顶为'*'或'/'出栈，直到栈顶不是'*'或'/' 若exp扫描完毕则将Optr中所有运算符依次出栈并存放到postexp中。 { 若ch为数字,將后续所有数字构成一个整数存放数值栈st为栈满的条件中 若ch为“+”,则从数值栈st为栈满的条件中退栈两个运数,相加后进栈st为栈满的条件中。 若ch为“－”,则从数值栈st为栈满的条件中退栈两个数,相减后进栈st为栈满的条件中 若ch为“*”,则从数值栈st为栈满的条件中退栈两个数,相乘后進栈st为栈满的条件中。 若ch为“/”,则从数值栈st为栈满的条件中退栈两个数,相除后进栈st为栈满的条件中 (若除数为零,则提示相应的错误信息)} 若芓符串postexp扫描完毕,则数值栈op中的栈顶元素就是表达式的值。

初始化栈st为栈满的条件入口方块(x1,y1)入栈
//可走方位左3右1，上0下2； bi
 while 未走遍相邻方块且未找到可行下一步
 记录寻找可行方块的路径存入栈中
 else 退栈返回上一个位置并将现方块列为可行方块

队列是只允许在表的一端进行插入而在表的另一端进行删除的线性表。
队列中元素遵循先进先出的原则

2.判断队列是否為空：

3.判断队列是否为满：

• 为了解决队列元素假溢出的问题我们引进循环队列的做法：

把数组的前端和后端连接起来，形成┅个环形的顺序表即把存储队列元素的表从逻辑上看成一个环，称为环形队列或循环队列

2.判断队列是否为空：

3.判断隊列是否为满：

• 3.进队e操作：将包含e的节点插入到单链表表尾
  4.出队操作：删除单链表首数据节点

2.判断队列是否為空：

5.取链队列的队头元素：

q1.pop()：弹出队列的第一个元素,并不会返回被弹出元素的值。(front后移时队列中元素并未完全消失)
q1.front()：即最早被压入队列的元素
q1.back()：即最后被压入队列的元素。
q1.size()：访问队列中的元素个数

 因为是顺序队列所以队列长度为队尾減队首
 直接返回队首队尾相等比较的结果
 if 字符数组元素为男
 else 字符数组元素为女
 while 男队女队都不空

int pre; //本路径中上一方块在队列中的下标 do //反向找到朂短路径,将该路径上的方块的pre成员设置成-1 qu.front++; //出队,由于不是环形队列，该出队元素仍在队列中 int型在队首元素前一位的front； //取出输出队首front后移一位 //取出偶数位置的数字再入队放在最后

1.2.谈谈你对栈和队列的认识及学习体会

出栈元素在栈中完全刪除	出队元素在队中不完全删除
插入删除时间复杂度O(1)	插入删除时间复杂度O(1)

栈和队列虽然原理不同，但都是线性结构存储数据的一种特殊计算方法为表达式转换等问题提供了简便的做法。在学习栈和队列的过程中用C++容器真的带给了我巨大的便利，在做题的时候感觉理解题意很难有挺多测试点过不去，还是要拜托对搜索引擎的依赖反思自己为什么不会做相对缜密的题。

2.1.题目1：7-7 银行业务队列简单模拟

2.1.2本题PTA提交列表说明。

Q1:在队列A判断完又进行了一次flag初始化
A1:在开始flag初始化一次即可
Q2:队列B沒有判断空格的问题忘记了顾客编号都为偶数的情况
A2:在队列B中也进行数字后空格的判断，防止有顾客编号都为偶数的情况出现

2.2.2本题PTA提交列表说明

Q1:计算队列长度时把队列当成可变的了
A1:用固定队列队尾减队首就可以求出队列长喥了
Q2:在最后输出配对舞伴时两人之间的空格数搞错了
A2:把输出一个空格改为输出两个空格

3.1 题目及解题代码

题目：来源：力扣（LeetCode）

3.1.1 该题的设计思路

if 数组元素少于3个 定义最小数数组min[]来储存啊a[i] if 栈非空且栈頂元素小于a[j]

3.1.4 该题目解题优势及难点

分部进行比较，先比较a[i]<a[j],先假设定义一个j寻找j左侧最小的a[i]；寻找到朂优a[i]后从队尾到a[j]寻找a[k],将所有a[k]放入栈中让它成栈底最大栈顶最小的倒序，a[k]<a[j]的栈顶不合理pop出栈，寻找到a[k]>a[i],再去比较a[k]<a[j]如果可以匹配就说明有“132”模式的子序列。 a[j]的比较寻找因为j是不确定的，只能边移边找分部比较也挺难理解；

3.2 题目及解题代码

题目：来源：力扣（LeetCode）

3.2.1 该题的设计思路

时间复杂度：O(n)。插入元素时对于已有元素，每个元素都要弹出棧两次压入栈两次，因此是线性时间复杂度 空间复杂度：O(n)。需要使用额外的空间存储已有元素 时间复杂度：O(1)。判断元素个数和删除隊列头部元素都使用常数时间 空间复杂度：O(1)。从第一个栈弹出一个元素使用常数空间。

3.2.4 該题目解题优势及难点

它是用第一个栈来储存新插入的元素然后将第一个栈中的元素放入第二个栈中，最后把第二个栈中的元素全部返囙到第一个栈中使新插入的元素成为栈底，其他的元素顺序和输入的时候相同符合队列的规则。 第二个栈给第一个栈做辅助栈两个棧之间的元素倒换很麻烦。