一、顺序队列的概念
与线性表、栈类似,队列的实现也有两种方式:顺序存储和链式存储。
顺序存储的队列称之为顺序队,要为其分配一块连续的存储空间来存放队列中的元素,并且由于队头和队尾都是活动的,所以需要队头和队尾两个指针。
这里约定队头指针指向实际队头元素所在的位置的前一位置,队尾指针指向实际队尾元素所在的位置。存储结构如下图所示:
顺序队的存储结构:
(一)顺序队的假溢出问题
由于顺序队是静态分配存储空间,并且队列的活动是动态的:入队操作是在队尾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;
}