队列
1 什么是队列？
只允许在两端进行插入和删除操作的线性表，在队尾插入，在队头删除 插入的一端，被称为"队尾"，删除的一端被称为"队头"
在队列操作过程中，为了提高效率，以调整指针代替队列元素的移动，并将数组作为循环队列的操作空间。
2 队列的特点
先进先出 FIFO first in first out
后进后出 LILO last
循环队列（顺序队列）
1）逻辑结构：线性结构
2）存储结构：顺序存储
3）操作：入队、出队
#define N 5
typedef int datatype;
typedef struct
{
datatype data[N];
int rear; //后面，队尾
int front; //前面，队头
}sequeue_t；//sequence 顺序 queue队列
1）创建一个空的队列
2）入列
3）求长度
sequeue.c
#include <stdio.h>
#include <stdlib.h>
#define N 5
typedef int datatype;
typedef struct
{
datatype data[N]; // 循环队列的数组
int rear; // 存数据端 rear 后面
int front; // 取数据端 front 前面
} sequeue_t;
// 1.创建一个空的队列
sequeue_t *CreateEmptySequeue()
{
// 1.开辟一个结构体大小的空间
sequeue_t *p = (sequeue_t *)malloc(sizeof(sequeue_t));
if (p == NULL)
{
perror("CreateEmptySequeue err");
return NULL;
}
// 2.初始化
p->front = 0;
p->rear = 0;
return p;
}
// 3.判断队列是否为满
int IsFullSequeue(sequeue_t *p)
{
// 判断尾巴的下一个位置是不是头
return (p->rear + 1) % N == p->front;
}
// 2.入列 data代表入列的数据
int InSequeue(sequeue_t *p, datatype data)
{
// 1.判满
if (IsFullSequeue(p))
{
perror("IsFullSequeue");
return -1;
}
// 2.数据入队
p->data[p->rear] = data;
// 3.移动尾下标
p->rear = (p->rear + 1) % N;
return 0;
}
// 4.判断队列是否为空
int IsEmptySequeue(sequeue_t *p)
{
return p->rear == p->front;
}
// 5.出列
datatype OutSequeue(sequeue_t *p)
{
// 1.判空
if (IsEmptySequeue(p))
{
perror("IsEmptySequeue");
return -1;
}
// 2.取数据
datatype temp = p->data[p->front];
// 3.移动队头
p->front = (p->front + 1) % N;
return temp;
}
// 6.求队列的长度
int LengthSequeue(sequeue_t *p)
{
// if(p->rear >= p->front)
// return p->rear - p->front;
// else
// return p->rear - p->front + N;
return (p->rear - p->front + N)%N;
}
// 7.清空队列函数
void ClearSequeue(sequeue_t *p)
{
p->front = p->rear;
}
int main(int argc, char const *argv[])
{
sequeue_t * p = CreateEmptySequeue();
for(int i=1;i<5;i++)
InSequeue(p,i);
printf("len is %d\n",LengthSequeue(p));
while (!IsEmptySequeue(p))
printf("%d ",OutSequeue(p));
printf("\n");
free(p);
p=NULL;
return 0;
}
链式队列
1）逻辑结构：线性结构
- 存储结构：链式存储
- 操作：入队、出队
typedef int datatype;
typedef struct node
{
datatype data;//数据域
struct node *next;//指针域
}linkqueue_node_t,*linkqueue_list_t;
typedef struct//将队列头指针和尾指针封装到一个结构体里
{
linkqueue_list_t front;//相当于队列的头指针
linkqueue_list_t rear;//相当于队列的尾指针
//有了链表的头指针和尾指针，那么我们就可以操作这个链表
}linkqueue_t;
(1)创建一个空的队列
(2)入列
(3)出列
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{
datatype data; // 数据域
struct node *next; // 指针域
} linkqueue_node_t, *linkqueue_list_t;
// linkqueue_list_t p === linkqueue_node_t *
typedef struct // 将队列头指针和尾指针封装到一个结构体里
{
linkqueue_list_t front; // 相当于队列的头指针
linkqueue_list_t rear; // 相当于队列的尾指针
// 有了链表的头指针和尾指针，那么我们就可以操作这个链表
} linkqueue_t;
// 1.创建一个空的队列
linkqueue_t *CreateEmptyLinkQueue()
{
// 1.开辟存放头尾指针的结构体的空间
linkqueue_t *p = (linkqueue_t *)malloc(sizeof(linkqueue_t));
if (p == NULL)
{
perror("CreateEmptyLinkQueue err");
return NULL;
}
// 2.初始化：头尾指针都指向头节点
p->front = p->rear = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));
if (p->front == NULL)
{
perror("p->front malloc err");
return NULL;
}
p->front->next = NULL; // 头节点的指针域为NULL,表示空
return p;
}
// 2.入列 data代表入列的数据
int InLinkQueue(linkqueue_t *p, datatype data)
{
// 1.开辟一个节点大小的空间存放数据
linkqueue_list_t pnew = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));
if (pnew == NULL)
{
perror("pnew malloc err");
return -1;
}
pnew->data = data;
pnew->next = NULL;
// 2.将节点入队（尾插）
p->rear->next = pnew;// 新节点链接到链表的尾
// 3.移动队尾
p->rear = pnew;// rear移动，始终指向当前链表的尾巴
return 0;
}
// 4.判断队列是否为空
int IsEmptyLinkQueue(linkqueue_t *p)
{
return p->front == p->rear;
}
// 3.出列
datatype OutLinkQueue(linkqueue_t *p)
{
//1.判空
if(IsEmptyLinkQueue(p))
{
perror("IsEmptyLinkQueue");
return -1;
}
//2.定义pdel指向被删除节点（头节点）
linkqueue_list_t pdel = p->front;
//3.移动头指针
p->front = pdel->next;
//4.释放头节点
free(pdel);
pdel=NULL;
//5.出队数据
return p->front->data;
}
// 5.求队列长度的函数
int LengthLinkQueue(linkqueue_t *p);
// 6.清空队列
void ClearLinkQueue(linkqueue_t *p);
int main(int argc, char const *argv[])
{
linkqueue_t *p=CreateEmptyLinkQueue();
for(int i=1;i<=5;i++)
InLinkQueue(p,i);
for(int i=1;i<=5;i++)
printf("%d ",OutLinkQueue(p));
printf("\n");
free(p->front);
p->front =NULL;
free(p);
p=NULL;
return 0;
}