本篇介绍有关队列的知识。队列也是一种特殊的线性表，只允许在表的表的一端进行插入，而在表的另一端进行删除。插入元素称为入队或进队；删除元素称为出队或离队。操作的特性是先进先出。
队列的常见操作和栈类似，有初始化队列，队列判空，入队，出队，读队头元素。下面介绍队列的顺序存储和链式存储。
一：队列的顺序存储
1.普通的顺序存储队列
实质是分配一块连续的存储单元存放队列中的元素，并附设两个指针，一个队头指针front指向队头元素，一个队尾指针rear指向队尾元素的下一个位置，也有其他的定义，操作是不同的。
顺序队列描述为：
#define MaxSize 20 //定义队列中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //存放队列元素
int front,rear; //队头指针和队尾指针
}SqQueue;
初始状态(队空)： Q.front == Q.rear == 0。
进队操作：队不满时，先先送值到队尾元素，队尾指针再加一。
出队操作：队不空时，先取队头元素值，再将队头指针加一。
但是这种简单的队列会出现假溢出的现象，是因为队满时Q.front仍然等于Q.rear。如何进行改进呢，可以用一种叫做循环队列的存储结构。
2.循环队列
就使用一种环状结构存储队列，当队首指针Q.front在队满的位置MaxSize-1时，再前进一个位置就自动回到0，这时候可以用取余操作%来实现。
初始时：Q.front==Q.rear=0。
队首指针加一：Q.front=(Q.front+1)%MaxSize。
队尾指针加一：Q.rear=(Q.rear+1)%MaxSize。
队列长度：(Q.rear+MaxSize-Q.front)%MaxSize。
出队入队时，指针都按顺时针的方向进1。
为了区别当Q.rear == Q.front时，是队满还是队空，可以有三种处理方式。
(1)牺牲一个存储单元区分队空还是队满，即入队的时候少用一个队列单元。则有
队空：Q.front == Q.rear
队满：(Q.rear+1)%MaxSize == Q.front
队列中元素个数：(Q.rear+MaxSize-Q.front)%MaxSize
(2)用一个计数器计算元素个数
(3)用一个tag数据成员区分队空还是队满,tag为0时队空，tag为1时队满。
操作如下：
初始化：
void InitQueue(SqQueue &Q){
Q.rear = Q.front = 0; //初始化队首，队尾指针
}
判队空：
bool isEmpty(SqQueue Q){
if(Q.rear == Q.front) return true; //队空条件
else return false;
}
入队：
bool EnQueue(SqQueue &Q,ElemType x){
if((Q.rear+1)%MaxSize == Q.front) return false; //队满则报错
Q.data[Q.rear] = x;
Q.rear = (Q.rear+1)%MaxSize;
return true;
}
出队：
bool DeQueue(SqQueue &Q,ElemType &x){
if(Q.rear == Q.front) return false; //队空则报错
x = data[Q.front];
Q.front = (Q.front+1)%MaxSize;
return true;
}
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
