队列是一种 *** 作受限的线性表，它只允许在一端（队尾）进行插入，另一端（队头）进行删除。
队列具有先进先出（FIFO）的特点。
下面给出队列常见的基本 *** 作：
1）InitQueue(&Q)：队列初始化
2）IsEmpty(Q)：队列判空
3) EnQueue(&Q,e)：入队
4) DeQueue(&Q,&e)：出队
5) GetHead(Q,&e)：获取队头元素
6) GetLength(Q)：获取队列长度
由于队列的顺序存储中存在“假溢出”或“上溢出”，一般在使用中会采用循环队列或链式队列，下面给出循环队列和链式队列（带和不带头结点）的实现。
- 队列的顺序存储（循环队列）和链式存储（带和不带头结点）C/C++实现
- @[TOC](文章目录)
一、循环队列
- 1.结构
- 2.初始化
- 3.队空和队满的判断
- 4.入队 *** 作
- 5.出队 *** 作
- 6.完整代码
二、链式队列（不带头结点）
- 1.结构
- 2.初始化
- 3.队空的判断
- 4.入队 *** 作
- 5.出队 *** 作
- 6.完整代码
三、链式队列（ 带头结点）
- 1.结构
- 2.初始化
- 3.队空的判断
- 4.入队 *** 作
- 5.出队 *** 作
- 6.完整代码
四、总结
一、循环队列
循环队列其实是将顺序队列臆造成的一个环状空间，其中：
初始时 ：sq.front=sq.rear=0
队头指针+1：sq.front=(sq.front+1)%MAXSIZE
队尾指针+1：sq.rear=(sq.rear+1)%MAXSIZE
循环队列在一般情况下，判断队空的条件为sq.front == sq.rear，当入队元素的速度快于出队元素的速度时，则队尾指针就会很快赶上队头指针，此时队满条件仍为sq.front==sq.rear，因此无法判断当前为队空还是队满。
为了区分队空和队满情况，下面介绍三种常见的处理方式：
1）牺牲一个单元来区分队空和队满;入队时少用一个队列单元，这是一种较为普遍的做法，约定“队头指针在队尾指针的下一位置作为队满的标志”；此时队满条件为（sq.rear+1)%MAXSIZE ==sq.front，队空条件仍为sq.rear=sq.front，队列中的元素个数为(sq.rear-sq.front+MAXSIZE)%MAXSIZE。
2) 在类型中增设表示元素个数的数据成员size；这样，队空条件为：sq.size=0，队满条件为sq.size=MAXSIZE，这两种情况时都有sq.front=sq.rear。
3）在类型中增设tag数据成员；默认tag=0时为出队 *** 作，tag=1时为入队 *** 作，这样当sq.front ==sq.rear时，如果tag=0，即为因出队而导致的，因此此时队空；若tag=1,则为因入队而导致的，因此此时队满。
下面代码的循环队列采用第一种处理方式，即牺牲一个单元来区分队空和队满。
typedef int ElemType;
typedef struct{
ElemType data[MAXSIZE];
int front,rear; //定义队头、队尾指针
}SqQueue;
void Init(SqQueue *sq){
sq->front=0;
sq->rear=0;
}
队满条件：(sq.rear+1)%MAXSIZE== sq.front;
队空条件：sq.front ==sq.rear;
bool IsFull(SqQueue sq){
return (sq.rear+1)%MAXSIZE==sq.front;
}
bool IsEmpty(SqQueue sq){
return sq.front==sq.rear;
}
bool EnQueue(SqQueue *sq,ElemType e){
if(IsFull(*sq)){
return false;
}
sq->data[sq->rear]=e;
sq->rear=(sq->rear+1)%MAXSIZE;
return true;
}
bool DeQueue(SqQueue *sq,ElemType *e){
if(IsEmpty(*sq)){
return false;
}
*e=sq->data[sq->front];
sq->front=(sq->front+1)%MAXSIZE;
return true;
}
#include二、链式队列（不带头结点） 1.结构
typedef int ElemType;
typedef struct Node{
ElemType data; //数据域
struct Node *next; //指针域
}Node; //构造结点
typedef struct {
Node *rear,*front; //定义队尾、队头指针
}LinkQueue; //构造链队
/**
* @brief 链队初始化（不带头结点）
*/
void Init(LinkQueue *lq){
lq->front=lq->rear=NULL;
}
链式存储无需判断队满情况
/**
* @brief 链队判空
*/
bool IsEmpty(LinkQueue lq){
return lq.front==NULL;
}
/**
* @brief 入队 *** 作
*/
bool EnQueue(LinkQueue *lq,ElemType e){
Node *node=(Node *)malloc(sizeof(Node)); //申请新结点node
if(node==NULL)
return false;
node->data=e;
node->next=NULL;
if(lq->front==NULL){ //由于不带头结点，在第一次进行入队 *** 作时需对队头进行特殊处理
lq->front=node;
lq->rear=node; //队头为空时，将队头队尾指针都指向新结点node
}else{
lq->rear->next=node;
lq->rear=node; //队头不为空时，将新结点入队，并修改队尾指针指向node
}
return true;
}
/**
* @brief 出队 *** 作
*/
bool DeQueue(LinkQueue *lq,ElemType *e){
if(IsEmpty(*lq)){ //链队出队前进行判空
return false;
}
*e=lq->front->data; //返回出队元素
Node *node=lq->front;
lq->front=lq->front->next; //队头指针指向下一个结点（最一个元素的下一个为NULL）
free(node); //释放结点
return true;
}
#include三、链式队列（ 带头结点） 1.结构
同上
2.初始化void Init(LinkQueue *lq){
lq->rear=lq->front=(Node *)malloc(sizeof(Node)); //申请头结点
lq->rear->next=NULL;
}
链式存储无需判断队满情况
bool IsEmpty(LinkQueue lq){
return lq.front->next==NULL;
}
bool EnQueue(LinkQueue *lq,ElemType e){
Node *node=(Node*)malloc(sizeof(Node));
if(node==NULL){
return false;
}
node->data=e;
node->next=NULL;
lq->rear->next=node; //将新结点加入队尾
lq->rear=node; //修改队尾指针指向node
return true;
}
bool DeQueue(LinkQueue *lq,ElemType *e){
if(IsEmpty(*lq)){
return false;
}
Node *node=lq->front->next;
*e=node->data;
lq->front->next=node->next;
if(node==lq->rear){ //当删除的结点为最后一个结点时将队尾指针指向头结点
lq->rear=lq->front;
}
free(node);
return true;
}
#include四、总结
不难看出，不带头结点的链式队列在 *** 作上往往比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，这样插入和删除 *** 作就统一了。
循环队列适用于数据元素数量稳定的情况；用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）