顺序队列
概念
队列是一个先进先出的数据结构。
队列（queue）是限定在表的一端进行插入，表的另一端进行删除的数据结构，如同栈的学习，请联系前文所学链表，试想一个单链表，我们只能对他的链表表尾进行插入，而只能对链表的表头进行结点的删除，其余一切的操作均不允许，这样强限制性的“链表“，就是我们所说的队列。
说白了，顾名思义，数据出去的方式就像人排队核酸检测，先来的先检测，后来的后检测。
插入的数据排到后面，删除的数据紧着前面。
定义：队列是一个线性的数据结构，规定这个数据结构只允许在一端进行插入，另一端进行删除，禁止直接访问除这两端以外的一切数据。
结点的设计
//结点定义
typedef struct node{
int data;
struct node *next;
}node;
//队列定义，队首指针和队尾指针
typedef struct queue{
node *front; //头指针
node *rear; //尾指针
}queue;
//额外添加了一个结构体，其包括了两个分别永远指向队列的队尾和队头的指针，我们主要的操作只对这两个指针进行操作
初始化
有关初始化，稍微复杂一点的是，我们对于初始化需要初始化两个类型，一个是初始化结点，一个是初始化队列，初始化队列稍微有些不同，那就是当初始化队列的时候，需要将头尾两个结点指向的内容统统制空，表示是一个空队列。
结点的初始化
//初始化结点
node *init_node(){
node *n=(node*)malloc(sizeof(node));
if(n==NULL){ //建立失败，退出
exit(0);
}
return n;
}
队列的初始化
//初始化队列
queue *init_queue(){
queue *q=(queue*)malloc(sizeof(queue));
if(q==NULL){ //建立失败，退出
exit(0);
}
//头尾结点均赋值NULL
q->front=NULL;
q->rear=NULL;
return q;
}
//开辟空间，让front和rear指针都指向NULL。
判断队列是否为空。
直接看front指针是否为空。
//方法一：
int empty(queue *q){
if(q->front==NULL){
return 1; //1--表示真，说明队列非空
}else{
return 0; //0--表示假，说明队列为空
}
}
//方法二：
int empty(queue *q){
return q->front==NULL;
}
操作---入队
- 操作在尾指针
//入队操作
void push(queue *q,int data){
node *n =init_node();
n->data=data;
n->next=NULL; //采用尾插入法
//if(q->rear==NULL){ //使用此方法也可以
if(empty(q)){
q->front=n;
q->rear=n;
}else{
q->rear->next=n; //n成为当前尾结点的下一结点
q->rear=n; //让尾指针指向n
}
}
//执行入队操作前先要判断一下队列是否为空，如果为空，则要让头指针和尾指针指向同一个结点。
//简述核心操作：让老尾结点指向新尾结点，尾指针也指向新尾结点。
操作---出队
- 操作在头指针
//出队操作
void pop(queue *q){
node *n=q->front;
if(empty(q)){
return ; //此时队列为空，直接返回函数结束
}
if(q->front==q->rear){
q->front=NULL; //只有一个元素时直接将两端指向制空即可
q->rear=NULL;
free(n); //记得归还内存空间
}else{
q->front=q->front->next;
free(n);
}
}
//需要注意，要事先判断队列元素数，如果队列只有一个元素，需要将头指针和尾指针都指向NULL。
//常规操作：头指针指向头结点的下一个结点，释放头结点。
操作---遍历
//打印队列元素
void print_queue(queue *q){
node *n = init_node();
n=q->front;
if(empty(q)){
return ; //此时队列为空，直接返回函数结束
}
while (n!=NULL){
printf("%d\t",n->data);
n=n->next;
}
printf("\n"); //记得换行
}
//从队列头遍历到队列尾。
完整代码
#include<stdio.h>
#include<stdlib.h>
//结点定义
typedef struct node{
int data;
struct node *next;
}node;
//队列定义，队首指针和队尾指针
typedef struct queue{
node *front;
node *rear;
}queue;
//初始化结点
node *init_node(){
node *n=(node*)malloc(sizeof(node));
if(n==NULL){ //建立失败，退出
exit(0);
}
return n;
}
//初始化队列
queue *init_queue(){
queue *q=(queue*)malloc(sizeof(queue));
if(q==NULL){ //建立失败，退出
exit(0);
}
//头尾结点均赋值NULL
q->front=NULL;
q->rear=NULL;
return q;
}
//队列判空
int empty(queue *q){
if(q->front==NULL){
return 1; //1--表示真，说明队列非空
}else{
return 0; //0--表示假，说明队列为空
}
}
//入队操作
void push(queue *q,int data){
node *n =init_node();
n->data=data;
n->next=NULL; //采用尾插入法
//if(q->rear==NULL){
if(empty(q)){
q->front=n;
q->rear=n;
}else{
q->rear->next=n; //n成为当前尾结点的下一结点
q->rear=n; //让尾指针指向n
}
}
//出队操作
void pop(queue *q){
node *n=q->front;
if(empty(q)){
return ; //此时队列为空，直接返回函数结束
}
if(q->front==q->rear){
q->front=NULL; //只有一个元素时直接将两端指向制空即可
q->rear=NULL;
free(n); //记得归还内存空间
}else{
q->front=q->front->next;
free(n);
}
}
//打印队列元素
void print_queue(queue *q){
node *n = init_node();
n=q->front;
if(empty(q)){
return ; //此时队列为空，直接返回函数结束
}
while (n!=NULL)
{
printf("%d\t",n->data);
n=n->next;
}
printf("\n"); //记得换行
}
//主函数调用，这里只是简单介绍用法
int main(){
queue *q=init_queue();
///////////////入队操作/////////////////
printf("入队\n");
for(int i=1;i<=5;i++){
push(q,i);
print_queue(q);
}
///////////////出队操作/////////////////
printf("出队\n");
for(int i=1;i<=5;i++){
pop(q);
print_queue(q);
}
return 0;
}