©2020-2024 ioDraw All rights reserved
一、队列的定义
线性表：是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，当n=0时，线性表是一个空表。若用L命名线性表，则其一般表示为L=（a1,a2,...,ai,ai+1,...,an）。
栈：是只允许在一段进行插入或删除操作的线性表。
队列：是只允许在一端进行插入，在另一端删除的线性表。
队头、队尾、空队列
特点：先进先出（FIFO） First in first out
二、队列的基本操作
2.1 队列的定义
#define MaxSize 10//定义队列中元素的最大个数 typedef struct{ ElemType
data[MaxSize];//用静态数组存放队列元素 int front,rear;//队头指针和队尾指针 }SqQuene; void
testQueue(){ SqQueue Q;//声明一个队列（顺序存储） }//后续操作...
2.2 初始化操作
void InitQueue(SqQueue &Q){ //初始时，队头、队尾指针指向0 Q.rear=Q.front=0; } void
testQueue(){ //声明一个队列（顺序存储） SqQueue Q; InitQueue(Q); //后续操作... }
判断队列是否为空
bool QueueEmpty(SqQueue Q){ if(Q.rear==Q.front)//队空条件 return true; else return
false; }
2.3 入队操作
bool EnQueue(SqQueue &Q,ElemType x){ if(队列以满) return false;//队满则报错
Q.data[Q.rear]=x;//将x插入队尾 Q.rear=Q.rear+1;//队尾指针后移 return true; }
Q.data[Q.rear]=x——将 x放入队尾指针所指的位置
Q.rear=Q.rear+1——队尾指针加一，后移
静态数组存满后，队尾指针是10
所以队列已满的条件是：rear==MaxSize？？？？
答案不是
当取出元素时，rear还是等于10，不会变，但这时候队列有空
所以更改代码，采用取余操作Q.rear=(Q.rear+1)%MaxSize，将存储空间从逻辑上变成了“环状”
bool EnQueue(SqQueue &Q,ElemType x){ if(队列以满) return false;//队满则报错
Q.data[Q.rear]=x;//将x插入队尾 Q.rear=(Q.rear+1)%MaxSize;//队尾指针+1取模 return true; }
因为判断队满的条件是判断rear==front，因此必须牺牲一个单元
队列已满的条件：队尾指针的在下一个位置是队头，即（Q.rear+1）%MaxSize==Q.front;
bool EnQueue(SqQueue &Q,ElemType x){ if((Q,rear+1)%MaxSize==Q.front)//判断队满条件
return false;//队满则报错 Q.data[Q.rear]=x;//将x插入队尾
Q.rear=(Q.rear+1)%MaxSize;//队尾指针+1取模 return true; }
队列元素个数：
（rear+MaxSize-front）%MaxSize
2.4 出队操作
只能让队头元素出队
//出队（删除一个队头元素，并用x返回） bool DeQueue(SeQueue &Q,ElemType &x){ if(Q.rear==Q.front)
return false;//队空则报错 x=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; return
ture; }
2.5 队列查找
获得队头元素，用x返回
bool GetHead(SqQueue Q,ElemType &x){ if(Q.rear==Q.front) return false;//队空则报错
x=Q.data[Q.front]; return true; }
其他元素呢？？？
2.6 不浪费内存条件下判断队列已满/已空
方法二：
#define MaxSize 10 typedef struct{ ElemType data[MaxSize]; int front,rear; int
size;//队列当前长度 }SqQuene;
初始化时rear==front==0;size=0;
插入成功：size++
删除成功：size--；
队满条件：size==MaxSize;
队空条件：size==0；
方法三：
#define MaxSize 10 typedef struct{ ElemType data[MaxSize]; int front,rear; int
tag;//最近进行的是删除（0）/插入（1） }SqQuene;
初始化时，rear=front=0;tag=0;
每次删除操作成功时，都令tag=0；
每次插入操作成功时，都令tag=1；
只有删除操作才可能导致队空，因此队空条件为：front==rear&&tag==0；
同理，队满条件为：front==rear&&tag==1；
2.7 rear指针指向队尾元素情况
判空：
（Q.rear+1）%MaxSize==Q,front
判满：
（Q.rear+1）%MaxSize==Q,front
两种方法：
1.牺牲一个存储单元：
rear与front隔了两个单元，队满、隔了 一个单元，队空
2.增加辅助变量
size、tag
三、链式存储实现队列
3.1 队列的链式实现
typedef struct LinNode{//链式队列结点 ElemType data; struct LinkNode *next;
}LinkNode; typedef struct{//链式队列 LinkNode *front,*rear;//队列的队头和队尾指针 }LinkQueue;
3.2 初始化
带头结点
typedef struct LinkNode{ ELEMtype data; struct LinkNode *next; }LinkNode;
typedef struct{ LinkNode *front,*rear; }LinkQueue; //初始化队列 void
InitQueue(LinkQueue &Q){ //初始时 front、rer都指向头结点
Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); Q.front->next=NULL;//判空操作 }
void testLinkQueue(){ LinkQueue Q;//声明一个队列 InitQueue(Q);//初始化一个队列 //后续操作.... }
其他判空操作：
bool IsEmpty(LinkQueue Q){ if(Q.front==Q.rear) return true; else return false;
}
不带头结点
3.3 入队操作
带头结点
void EnQueue(LinkQueue &Q,ElemType x){ LinkNode *s=(LinkNode
*)malloc(sizeof(LinkNode)); s->data=x; s->next=NULL;
Q.rear->next=s;//新结点插入rear之后 Q.rear=s;//修改表尾指针 }
元素都是队尾插入，所以s的next指针为空
不带头结点
3.4 出队操作
带头结点
bool DeQueue(LinkQueue &Q,ElemType &x){ if(Q.front==Q.rear) return false;//空队
LinkNode *p=Q.front->next; x=p->data;//用变量x返回队头元素
Q.front->next=p->next;//修改头结点的next指针 if(Q.rear==p)//此次是最后一个结点出队
Q.rear=Q.front;//修改rear指针 free(p);//释放结点空间 return true; }
不带头结点
四、双端队列
只允许从两端插入、两端删除的线性表
若只使用其中一端插入、删除操作，则效果等同于栈