队列
队列基本概念
队列( queue )是一种特殊的线性表结构，只从队尾插入新的元素，并且只从队首弹出元素。一般将队尾称为 rear，队首称为 front 。
队列基本操作
（1）入队：从队尾 rear 插入新元素；
（2）出队：从队首 front 弹出元素。
队列的特性
队列遵循 先进先出 的原则。比如元素 1、2、3、4、5 依次入队，且中途不存在出队过元素再次入队或其他元素入队，出队顺序为 1、2、3、4、5 。
循环顺序队列
循环顺序队列基本概念
顺序队列是用数组实现的队列，但是由于定义的数组的空间有限，可以想象一下，当队首 front 和 队尾 rear 经过一系列操作都往后移动时，之前所使用到的空间都不会再被使用了，这造成了空间上的浪费。
所以定义顺序队列往往采用更加高效的 循环顺序队列，其基本上就是在顺序队列的基础上加了一点小小的修改。
循环顺序队列的入队操作
循环顺序队列入队操作图解
初始状态下的循环顺序队列
元素1入队
元素2、3、4、5入队
循环顺序队列入队操作代码
//队列元素入队
void Enter_SqQueue(SqQueue *Q, int e){
if((Q->rear + 1) % MAXSIZE == Q->front){
printf("队列已满\n");
return;
}
Q->data[Q->rear] = e; //在队尾指向的地址赋值
Q->rear = (Q->rear + 1) % MAXSIZE; //队尾指针进1
}
循环顺序队列的出队操作
循环顺序队列出队操作图解
元素1出队
元素2、3、4、5出队
循环顺序队列出队操作代码
//队列元素出队
void Depart_SqQueue(SqQueue *Q, int *e){
if(IsEmpty(Q)){
printf("队列中无元素\n");
return;
}
*e = Q->data[Q->front]; //取出队首指针指向的地址元素
Q->front = (Q->front + 1) % MAXSIZE;//队首指针进1
}
循环顺序队列中的循环示例
入队
此时队列rear虽然指向数组的最后，但循环操作可以使其重复利用之前使用的空间。
出队
类似的此时队列front指向数组的最后
循环顺序队列完整程序
源代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 1000
typedef int Elemtype;
typedef struct SqQueue{
Elemtype data[MAXSIZE];
int front; //队列前指针
int rear; //队列后指针
}SqQueue;
//初始化
void Create_SqQueue(SqQueue *Q){
Q->front = Q->rear = 0;
}
//判断队列是否为空
bool IsEmpty(SqQueue *Q){
return Q->front == Q->rear;
}
//求得队列长度
int SqQueue_Length(SqQueue *Q){
return (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
}
//队列元素入队
void Enter_SqQueue(SqQueue *Q, int e){
if((Q->rear + 1) % MAXSIZE == Q->front){
printf("队列已满\n");
return;
}
Q->data[Q->rear] = e; //在队尾指向的地址赋值
Q->rear = (Q->rear + 1) % MAXSIZE; //队尾指针进1
}
//队列元素出队
void Depart_SqQueue(SqQueue *Q, int *e){
if(IsEmpty(Q)){
printf("队列中无元素\n");
return;
}
*e = Q->data[Q->front]; //取出队首指针指向的地址元素
Q->front = (Q->front + 1) % MAXSIZE;//队首指针进1
}
//取队首
int Get_front(SqQueue *Q){
if(IsEmpty(Q)){
printf("队列为空\n");
return -1;
}
return Q->data[Q->front];
}
int main(){
SqQueue myQueue;
Elemtype a[5] = {35, 30, 11, 23, 9};
Create_SqQueue(&myQueue);
for(int i = 0; i < 5; i++)
Enter_SqQueue(&myQueue, a[i]);
Elemtype e;
Depart_SqQueue(&myQueue, &e);
printf("出队元素: %d\n", e);
printf("元素22入队并将所有元素出队: \n");
Enter_SqQueue(&myQueue, 22);
while(!IsEmpty(&myQueue)){
printf("%d ", Get_front(&myQueue));
Depart_SqQueue(&myQueue, &e);
}
return 0;
}
程序运行结果
链队列
链队列基本概念
链队列是链式的队列结构，其拥有一个 front 指针作为队首，一般队首 front 是不带数据的；还有一个 rear 指针作为队尾，队尾 rear 指向队列的最后一个元素。链队列的操作和链表也有一些相似之处。
链队列的入队操作
链队列入队操作图解
初始状态下的链队列
元素1入队
元素2、3入队
链队列入队操作代码
//链队列元素入队
void Enter_LinkQueue(LinkQueue *Q, int e){
Linknode *node = (Linknode*)malloc(sizeof(Linknode));
node->data = e;
node->next = NULL;
Q->rear->next = node; //原先队列尾指针后继next指向新节点node
Q->rear = node; //尾指针重新指向新节点node
}
链队列的出队操作
链队列出队操作图解
元素1出队
链队列出队操作代码
当链队列只有一个元素并且将其出队时，需要特判一下，将链队列置于空队列的状态。
//链队列元素出队
void Depart_LinkQueue(LinkQueue *Q, int *e){
if(Q->rear == Q->front) return;
Linknode *p;
p = Q->front->next; //要删除的节点暂存给p
*e = p->data; //取出删除队头节点的数据
Q->front->next = p->next; //队头节点的后继next直接跨过删除的节点指向其下一个节点
if(Q->rear == p) //当队列只有一个元素的情况
Q->rear = Q->front;
free(p);
}
链队列完整程序
源代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int Elemtype;
//队列节点结构
typedef struct Linknode{
Elemtype data; //队列节点数据域
struct Linknode *next; //队列next指针域
}Linknode;
//链队列整体结构
typedef struct LinkQueue{
Linknode *front; //链队列首指针 队首指针不带数据
Linknode *rear; //链队列尾指针
}LinkQueue;
//初始化创建链队列
void Create_LinkQueue(LinkQueue *Q){
Q->front = Q->rear = (Linknode*)malloc(sizeof(Linknode));
Q->front->next == NULL;
}
//链队列元素入队
void Enter_LinkQueue(LinkQueue *Q, int e){
Linknode *node = (Linknode*)malloc(sizeof(Linknode));
node->data = e;
node->next = NULL;
Q->rear->next = node; //原先队列尾指针后继next指向新节点node
Q->rear = node; //尾指针重新指向新节点node
}
//链队列元素出队
void Depart_LinkQueue(LinkQueue *Q, int *e){
if(Q->rear == Q->front) return;
Linknode *p;
p = Q->front->next; //要删除的节点暂存给p
*e = p->data; //取出删除队头节点的数据
Q->front->next = p->next; //队头节点的后继next直接跨过删除的节点指向其下一个节点
if(Q->rear == p) //当队列只有一个元素的情况
Q->rear = Q->front;
free(p);
}
//判断是否为空
bool IsEmpty(LinkQueue *Q){
return Q->front == Q->rear;
}
//取队首
int Front_LinkQueue(LinkQueue *Q){
if(IsEmpty(Q)){
printf("队列为空\n");
return -1;
}
return Q->front->next->data;
}
int main(){
LinkQueue myQueue;
Create_LinkQueue(&myQueue);
Enter_LinkQueue(&myQueue, 1);
Enter_LinkQueue(&myQueue, 2);
Enter_LinkQueue(&myQueue, 3);
printf("当前队首元素为 %d \n", Front_LinkQueue(&myQueue));
Elemtype e;
Depart_LinkQueue(&myQueue, &e);
printf("出队的元素为 %d \n", e);
printf("当前队首元素为 %d \n", Front_LinkQueue(&myQueue));
printf("\n所有元素出队：\n");
while(!IsEmpty(&myQueue)){
printf("%d ", Front_LinkQueue(&myQueue));
Depart_LinkQueue(&myQueue, &e);
}
return 0;
}
程序运行结果
