数学和计算机科学板块_辛酸网
数据结构与算法5
BY TSherry
对于栈而言，给定一个有n个元素的序列，你只要在入栈时就按照这个先后顺序入栈就行了，中间也可以出栈。问：出栈的情况一共有几种可能性？这个数是卡特兰数：
队列也是种操作受限的线性表。和栈相反，队列是先进先出。队列的应用有任务的按顺序调度、进程或线程之前资源的分配、BFS、进程或线程间通信、数据缓存等。为了方便，一般用链表实现队列。链队列要做的无菲是在开头用删去结点，结尾用尾插法添加结点。然而对于链队列我有什么好说的呢？额，好像没有什么好说的。那就不说了吧，反正也没什么话可说。那就扯顺序存储的队列吧。
顺序队列必然是循环队列，为什么呢？因为顺序队列会实现对空间的重复利用。设有一个数组A用于实现队列，现在为了方便管理，设front为最前面元素下标，rear为最后一个结点的下一个位置下标。是的，这里设置的是一个尾结点。当然你要是懒得也可以不设置。尾结点内部不会存储什么真正要用的东西，于是所谓出队就是拿出A[front]，顺便front++，所谓入队就是在A[rear-1]赋值，再rear++。但是数组大小毕竟有限，这又不是list或vector，是实打实的C语言的数组。而众所周知，当入队入了一阵子，出队出了一阵子，front≠0是很正常的。也就是说，如果你不采取特殊措施，A[0]~A[front-1]这段空间的闲置不用的，不属于队列。那么可用的空间就小了。此时入队，rear变大，直至超过所允许的最大下标时，就不能再入队了。因为再入队，数组就越界了。但是问题来了，这个时候队列的存储溢出了吗？溢出了。顺序表的空间用完了吗？没有，还能放得下至少一个结点的信息。所以这种溢出叫做假溢出，具体地，我可以说这是假上溢。
所以，为了充分利用空间，顺序队列一定要循环利用空出的位置，这就导致其必然是循环队列。一开始，当front不为0且front<rear时，数组前面一定还有可以利用的空间，此时如果要插入元素，那么我们就得看rear在入队后是否会超过最大允许的下标，比如说n。要是rear还小于n，就加1，否则，令rear=0，重新开始增加，从而重新利用开头的空间。但如果rear就这么加下去，当rear大到一定程度后，前面的空间用完了，后面的空间也用完了，那就真的满了，不能入队了。我前面说过假设rear指向尾结点，所以当队列中只有一个元素时A[front]后面就是尾结点。front==rear-1，队空的时候rear再减1就二者相等了。不过考虑到循环的特性，所有加减的结论都要取余。
于是，带尾点的循环队列判空条件为front==rear mod n。
而满队条件是rear==front-1 mod n。
相应地，不带尾结点的循环队列,队满对空都有rear==(front-1) mod n。
另外设置变量tag记录有无元素即可。
然而这样又有一个问题，如果front>rear，随着出队的过程front越来越大直至超过n，那么数组前面还有元素没有出队呢，然front已达到极限，无法继续出队，这又是假溢出了，或者我具体地说是假下溢。【doge】
因此，我们需要设立一套和rear出队机制相类似地front入队机制，即确保队列不会满的条件下，front要是加1后不会超过n那就加1得了，否则也是从0开始重新增加。学过群论的应该知道，这就是在0~n设了一个模加群，front和rear在这个群中做的是模加运算，也就是入队和出队分别造成了rear=rear+1 mod n和front=front+1 mod n。
辛酸网 ©版权所有