顺序队列

一、顺序队列的概念

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

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

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

顺序队的存储结构:
顺序队的存储结构

(一)顺序队的假溢出问题

由于顺序队是静态分配存储空间,并且队列的活动是动态的:入队操作是在队尾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;
}
用户头像
登录后发表评论