栈与队列

PS：想来想去，为了节省时间，还是记一下笔者自认为重要的信息（笔试和机试的算法详解），其余概念啥的读者可以参考别的书目。

基本概念

栈和队列也是属于线性表。

1.栈和队列的顺序存储结构：

(1) 栈（先进后出）：栈顶元素位置：指向最后一个元素或指向最后一个元素的下一个位置

（想象成一口井就行，最上面即栈顶，最下面即栈底）

(2)一般开静态数组来存储模拟。下标0为栈底。

(3) 队列（先进先出）：一般采用循环队列。

（想象成一群人排成一队通过一个出口，排在第一个的叫队头，排在最后一个即队尾）

2.(a) 队头元素位置：指向第一个元素、指向第一个元素的前一个位置。
(b) 队尾元素位置：指向队尾元素、指向队尾元素的下一个位置。

上面队头和队尾元素的位置可以组合成四种情况。请读者视具体情况分析。

3.栈和队列的链式存储结构：

a. 栈：用单链表来模拟，表头为栈顶，表尾为栈底。插入和删除即是头插和头删。

栈和队列的应用

1. 栈的应用：表达式求值（中缀表达式转后缀表达式、括号匹配）、DFS（了解即可，笔试不涉及）

   PS：不是所有的递归程序都需要用到栈，当是尾递归的时候就不需要用栈。所谓尾递归，大概就是当前执行完操作回到上一层的时候没有别的执行操作了，可以直接结束的。

2. 队列的应用：BFS

3. 考题：2011-2、2011-3、2012-2、2013-2、2014-2、2014-3、2015-1、2016-3、2017-2、2018-1、2018-2、2019-42、2 020-2

   1.在做中缀表达式转后缀的题目的时候，我们对于优先级高的运算符需要处理掉（当前扫描到+、-；而前面一个入栈的是乘除，这时候就需要把前面的乘除处理掉 ），然后在进行低优先级的入栈。（一般问题，问栈中最多有几个运算符）
   2.循环队列队空和队满的情况判断，我们可以假设队列中有元素的情形时front和rear什么情况，然后反推到没有元素时的情况。队满的情况也是类似反推。
   3.2019-42:
   

押题：

AcWing 3302表达式求值