队列与栈，是每个程序员都要经常打交道的基本数据结构，其使用方法也非常简单，队列是先进先出，而栈则是先进后出。
但是在实现数据结构的时候，有几个坑是初学数据结构的程序员们经常会碰到的。那么是哪几个呢？我们来看一下。 一、假溢出 通常来讲，顺序队列用一个一维数组来表示，同时设置一个队头指针front，一个队尾指针rear，但是由于进队的话rear指针会加1，而出列的话front指针会加1。这就造成了当rear已经到了数组下标较大一方的时候，数组下标较少一方由于有出队操作，所以还有空余。这就造成了假溢出的现象。
二、循环队列与取余操作 为了解决“假溢出”的问题，人们想到，要不把队列首尾相连，循环起来不就好了？像上图中的，当数组已经到了上标的时候，如果数组下标的位置还有有空间，那就把它利用起来就好了。
这样我们就需要一种简单的计算方法，能够简单而快速的找到rear下标所在的位置。 以上图为例，我们需要一个算法，使得2+1=3，而5+1=1，这样，我们就可以在数组2已经有数据的时候，rear指针移动到3，而在数组5已经有数据的时候，rear指针移动到1的位置。 那么，什么样的算法能解决这个问题呢？很简单，相信每个学过小学数学的程序员都能想到。那就是取余（或叫求模）运算。 以上图为例 (2+1) % 5取余就是3，而(5+1)%5就为1了，于是我们就找到了种简单的算法解决了快速找到正确的数组下标的算法。于是假溢出问题被完美的解决了。 但是，随之而来的就产生了第三个问题。就是如何确定队列是空还是满。 三、队列空满的判断 循环队列带来的一个问题是如何判断队列是空还是满的问题，在顺序队列中，只需要front指针与rear指针相同，就意味着队列是空的，而在循环队列中，front==rear，即可能是队列为空时，也可能是队列为满时。于是这时候，我们就需要另外的方法来确定队列到底是空还是满。 通常情况下，解决方法有三种。 方法一：使用一个计数器记录队列中元素个数 判队满：num==MaxSize 判队空：num==0 方法二：加设标志位 判队满：tag==1 && Q.rear==Q.front 判队空：tag==0 && Q.rear==Q.front 但是以上两种方法都存在一个问题，就是增加了队列操作的计算，每次入队出队操作都要为这个空满问题单独增加一步操作，影响性能。于是人们又提出了第三种，也是最常用的方法。 方法三：少用一个元素的空间，用于区别 判队满：Q.front==(Q.rear+1)% MaxSize 判队空：Q.rear==Q.front
这样一来，虽然我们少了一个可以存放数据的空间，但是操作效率却大为提高了。因此还是非常划算的。 大家可以看到，即使是最为熟悉的队列，在实现的时候，也有好几个问题和巧妙的解决方法。因此大家在实际工作中，要勤于思考，发现解决问题的不同路径哦。 喜欢本文的话，欢迎关注活在信息时代哦：） |
