408第一季 - 数据结构 - 栈与队列

栈

闲聊 

栈是一个线性表

栈的特点是后进先出

然后是一个公式

 比如123要入栈，一共有5种排列组合的出栈

栈的数组实现

这里有两种情况，，一个是有下标为-1的，一个没有

代码不用看，真题不会考

 栈的链式存储结构

L -> 4 ->3 ->2 -> 1

归并所有的操作都在表头进行，用链表实现

做题区

1

相当简单，fedc出栈了4次了

2 

 

可以看见，除了它本身取不到，其他都能取到，也就是n-1的取值个数

3

这题目不难，必要陷入题目的陷阱了， 意思是in和out可以随便取

可以看出来可以判断出来能不能出栈

过程是一样的，看看能不能找到出栈，可以判断

C：一定不同就幽默了，

D：确实可能互为倒序

队列

闲聊

也是操作受限的线性表

操作特点是先进先出 FIFO

记住这句话，rear有点大病

 入队的话是从尾部队列，上面的图就是当front走到最上面，发现数组中还有空位置，就很浪费，所以就有了循环队列，就是可以重头开始

循环队列

循环队列是用数组实现的，所以它属于存储结构（物理结构），逻辑结构反映不出来是用什么实现的

下面一共会画4种图，兄弟们

第一种

front和rear都会指向0

然后假设第一个元素放入A【0】

入队我们要做的就是尾指针先放后移

就可以发现

第二种

front和rear都会指向倒数倒数第一个

那就只能先移动在放了

尾指针终于指向队尾了

头指针就很屎了，在队头前一个

第三种

头指针在倒数第一个，尾指针在第一个（图已分裂！）

肯定是先放后移了

尾指针肯定是队尾下一个

头指针是队头的前一个，永远是这样记住，若头指针移动到下一个元素出栈，那头指针仍然是队头的前一个

第四种

队头是0，队尾是倒数第一个

先移再放不多说

尾指针指向队尾

头指针指向队头，爽了

然后看一下题目就知道该怎么用了

这里就是第四种情况了，选B

判断队空队满

拿第一个举例子

后面就是先放再移动，移啊移啊，变成了下面的样子

就能发现 空是 front == rear

                满是 front == rear

可以发现居然一样的，我不能接受！

所以牺牲一个单元

 

就变成了 （rear + 1）% M == front

看题目

 这里头指向队首元素，队尾指向队尾后一个也是队头元素

后面又说最多能容纳M-1个，也就是说，他牺牲了一个单元，非常感动

选A

计算元素个数

如果  rear > front  那rear - front

如果  front出队，rear又入队

就变成了 rear < front  那就是 rear + n - front

所以，如果要整一个汇总就是

(rear - front + n)%n 

双端队列

 输出受限双端队列：就是2边能随便进，但输出受限了

  输入受限双端队列：就是2边能随便输出，但输入受限了

做个题

只让从一端出，也就是图这个样子，最后只要能入成选项的样子就可以了，因为最后直接顺序输出就结束了

C选项无法入成我想要的样子，所以错

一模一样的题

 选D