Tim的资源站

一、顺序队列的概念

与线性表、栈类似，队列的实现也有两种方式：顺序存储和链式存储。

顺序存储的队列称之为顺序队，要为其分配一块连续的存储空间来存放队列中的元素，并且由于队头和队尾都是活动的，所以需要队头和队尾两个指针。

这里约定队头指针指向实际队头元素所在的位置的前一位置，队尾指针指向实际队尾元素所在的位置。存储结构如下图所示：

顺序队的存储结构：

（一）顺序队的假溢出问题

由于顺序队是静态分配存储空间，并且队列的活动是动态的：入队操作是在队尾rear+1的位置插入一个元素，rear移动到存储空间的最后一位位置队满；出队操作是在队头删除一个元素，然后有两种方法，第一种是将所有的队列元素向前移一位，rear减1，front始终指向0位置不变。第二种方法是不需要移动元素，修改队列头指针front+1。

但是，第二种方法会造成假溢出。

这是由于出队删除元素时，为了避免移动元素，只是修改了队头指针，随着入队、出队的进行，队列整体向后移动。最终，发生这样的情况：队尾指针已经移到最后，再有元素入队就会出现溢出，而事实上，此时队列中并未真正“满员”，这种现象称为假溢出。

（二）假溢出问题的解决

解决假溢出的方法之一是将队列的数据区看成头尾相连的循环结构，头尾指针关系不变，将其称为循环队列，如下图所示。

循环队列：

因为是头尾相连接的循环结构，入队时的队尾指针加1操作修改为: rear=(rear+1)%size; size为顺序队列空间的大小，出队时的队头指针加1操作修改为：front=(front+1)%size。

（三）队空与队满

基于循环队列，队空的条件为：front=rear；队满的条件为：如果队列的入队比出队快，队列中的元素逐渐增多，rear会追上front，此时队满front=rear。

因次，队满与对出的判断条件是一致的，这显然存在问题。

解决办法有二，第一种是附设一个存储队中元素个数的变量，如num，当num=0时为队空，当num=size时为队满。

另一种方法是少用一个元素空间，使队尾指针永远赶不上front，即当队尾指针加1就会从后面赶上队头指针时，视为队满。在这种情况下，队满的条件是：(rear+1)%size=front。

二、顺序队列的实现

typedef int DataType;   //这里以整型为队列的数据类型

class SeqQueue {
  private:
    DataType *base;
    int front;
    int rear;
    int size;

  public:

    SeqQueue(int Queuesize=100) { //构造一个空队列，默认空间大小为 100
      base = new DataType [Queuesize];
      front = 0;
      rear = 0;
      size = Queuesize;
    };

    ~SeqQueue() { //销毁一个已存在的队列
      delete[] base;
    }

    int Empty_Queue();  //判断队列是否为空
    int En_Queue(DataType e);  //入队将元素 e 插入队尾
    int De_Queue(DataType &e);  //出队从队头删除一个元素到 e 中返回
    int Front_Queue(DataType &e); //取队头元素，从队头取出一个元素到 e 中返回
}

（一）判断循环队列是否为空

算法思想：只需判断front是否等于rear即可。实现如下：

int SeqQueue::Empty_Queue() {
  return (front == rear)
}

（二）进队操作

算法思想：首先判断队列是否已满，若满则退出，否则，由于队列的rear指向队尾元素，先修改rear到新的队尾位置，再将入队元素赋到rear的位置即可。

int SeqQueue::En_Queue(DataType e) {
  if (((rear + 1) % size) != front) { // 判断队列是否已满
    rear = (rear + 1) % size;
    base[rear] = e;
    return 1;
  } else 
    return 0;
}

（三）出队操作

算法思想：首先判断队列是否为空，若空则退出；否则，由于队列的front指向队头元素的前一位置，因此要先修改front，再将front所指向的元素以引用参数e返回即可。

int SeqQueue::De_Queue(DataType &e) {
  if (rear != front) {
    front = (front + 1) % size;
    e = base[front];
    return 1;
  } else
    return 0;
}

（四）取队头元素操作

算法思想：首先判断队列是否为空，若空则退出；否则，由于队列的front指向队头元素的前一位置，因此要返回的队头元素时front后一位置。

int SeqQueue::Front_Queue(DataType &e) {
  if (rear != front) {
    e = base[(front + 1) % size];
    return 1;
  } else
    return 0;
}