队列已满的条件：

队尾指针的下一个位置是队头（浪费一个位置，为了队满和空队区分开）

由于队列前面出了的部分可以继续放（也就是说队列是循环的）

出队-指向同一位置时

队列元素个数（常考）(背过)

$(rear+MaxSize-front)\%MaxSize$

多要求

不能浪费空间时
法1：使用size记录存放的数据元素数，即可拯救下那个空间。

法2：使用删除/插入操作记录，记录上次的插入/记录的判断（更省空间）

其他出题法

队尾指针指向队尾元素时，需要对代码进行部分变动。

另一种初始化方式：最后一个是尾指针

注意灵活使用数据结构，如需要使用队列且队列长度经常访问时，原本需要从头往尾遍历，时间复杂度为$O(n)$

但是如果提前加上一个数字变量size，则可以将复杂度变为$O(1)$

然而这同样会导致更多的占用和更多的操作次数，所以需要因地制宜的进行设计

双端队列

允许两端插入，两端删除。

双端队列常考：数据元素输入序列已知，判断哪些合法，哪些非法。

如输入序列为1234则：

输入方式共计$A_{4}^4=4!=24$种。
（可以按栈的方式判断，根据第一个看哪些已经入栈，然后再推）

（绝对不可能全部弄出来，卡特兰数需要记住但不需要验证）

因为双端序列可以头尾都出去，所以首先栈的肯定都能用->接下来判断剩下的即可

按照判断方式写一写出队的样式，然后看看能不能凑

栈和队列的典型问题

括号匹配问题

保证括号是成双成对的，形状上也需要匹配

(((()))) ->最后出现的左括号会最先被匹配上->后进先出，栈的特点

出现一个左括号就压到栈内，出现右括号就出栈

考试中可以使用基本接口，但需要写注释和定义。

考试中可以直接用最简单的数据结构处理。

表达式求值问题

后缀表达式常用->逆波兰式