速通回忆

有基础可以直接通过下面代码回忆一下即可😊（循环队列在后面）

#include "stdio.h"
#include "stdlib.h"

/* 数据结构体 */
typedef struct node{
    int data;
    struct node *next;
}node;

/* 队列结构体 */
typedef struct queue{
    node *front;
    node *rear;
}queue;

/* 队列初始化 */
queue *Queue_Init(){
    queue *queue_temp = (queue *)malloc(sizeof(queue));
    if(queue_temp == NULL){
        printf("ERROR\n");
        return NULL;
    }
    queue_temp->front = NULL;
    queue_temp->rear = NULL;
    return queue_temp;
}

/* 判断队列是否为空 */
int empty(queue *q){
    return q->front==NULL;
}

/* 入队操作 */
void Queue_Push(queue *q){
    /* 动态分配一个存储节点 */
    node *node_temp = (node *)malloc(sizeof(node));
    /* 输入数值 */
    printf("输入一个整数：");
    scanf("%d",&node_temp->data);
    node_temp->next = NULL;
    /* 判断是否为空 */
    if(empty(q)){
        q->front = node_temp;
        q->rear = node_temp;
    }else{
        q->rear->next = node_temp;
        q->rear = node_temp;
    }
}

/* 出队操作 */
int Queue_Pop(queue *q){
    int num;
    node *node_temp = (node *)malloc(sizeof(node));
    /* 判断栈是否为空 */
    if(empty(q)){
        printf("栈空\n");
        return -1;
    }else{
        /* 取值并释放空间 */
        node_temp = q->front;
        num = node_temp->data;
        q->front = q->front->next;
        if(q->front == NULL){
            q->rear = NULL;
        }
        free(node_temp);
    }
    return num;
}

void Queue_Show(queue *q){
    node *node_point = q->front;
    if(empty(q)){
        printf("队列为空\n");
        return ;
    }else{
        printf("队列内的数据：\t|");
        while(node_point != NULL){
            printf("  %d  |",node_point->data);
            node_point = node_point->next;
        }   
        printf("\n");
    }
}

int main(){
    queue *q = Queue_Init();
    if(q == NULL){
        return -1;
    }

    Queue_Push(q);
    Queue_Push(q);
    Queue_Push(q);

    printf("当前队列的内容：\n");
    Queue_Show(q);

    printf("出队元素：%d\n", Queue_Pop(q));
    printf("出队元素：%d\n", Queue_Pop(q));

    printf("当前队列的内容：\n");
    Queue_Show(q);

    Queue_Push(q);
    printf("当前队列的内容：\n");
    Queue_Show(q);

    printf("出队元素：%d\n", Queue_Pop(q));
    printf("出队元素：%d\n", Queue_Pop(q));
    printf("出队元素：%d\n", Queue_Pop(q)); // 尝试从空队列中出队

    free(q);
    return 0;
}

队列的概念

队列是一个先进先出的数据结构

队列是一个线性的数据结构，规定这个数据结构只允许在一端进行插入，另一端进行删除，禁止直接访问除这两端以外的一切数据。

队列的结点设计与初始化

以顺序队列的设计为例

设计出两个结构体，一个结构体Node表示结点，其中包含有一个data域和next指针，再次设计一个结构体进行限制性设计

//结点定义
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--表示假，说明队列为空
    }
}
//或者直接返回状态值
int empty(queue *q){
    return q->front==NULL;
}

入队操作

我们首先需要特判一下队列是否为空，如果队列为空的话，需要将头指针和尾指针一同指向第一个结点，即front=n;rear=n

当如果队列不为空的时候，我们只需要将尾结点向后移动，通过移动next指针指向新的结点构成队列

//入队操作
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
    }
}

出队操作

出队（pop）操作，是指在队列不为空的情况下（请注意一定要进行队列判空的操作），进行一个判断：

如果队列只有一个元素了（即头尾指针均指向了同一个结点），直接将头尾两指针制空

当队列含有二以上个元素时，我们需要将队列的头指针指向头指针当前指向的下一个元素并释放掉当前元素即可

//出队操作
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");   //记得换行
}

循环队列

#include "stdio.h"
#include "stdlib.h"

/* 设置循环队列最大值 */
#define MAXLEN 100

/* 循环队列 */
typedef struct queue{
    int nums[MAXLEN];
    int front;
    int rear;
} queue;

queue *QueueInit(){
    /* 动态分配存储空间 */
    queue *temp = (queue *)malloc(sizeof(queue));
    if(temp == NULL){
        printf("ERROR\n");
        return NULL;
    }

    /* 设置队首队尾相同 */
    temp->front = 0;
    temp->rear = 0;
    return temp;
}

/* 遍历输出 */
void QueueShow(queue *temp){
    int i = temp->front;
    int num;
    /* 判断队空 */
    if(temp->front == temp->rear){
        printf("ERROR\n");
        return ;
    }

    /* 遍历输出 */
    printf("当前队列中的元素：");
    while(i != temp->rear){
        num = temp->nums[++i];
        printf(" %d   |",num);
    }
    printf("\n");
}

/* 出队操作 */
int QueuePop(queue *temp){
    int num;
    /* 判断队空操作 */
    if(temp->rear == temp->front){
        printf("ERROR\n");
        return -1;
    }

    /* 从队首中提取出一个元素 */
    num = temp->nums[temp->front+1];
    temp->front = temp->front+1;
    printf("出队元素：%d\n", num);
    return num;
}

/* 入队操作 */
void QueuePush(queue *temp, int num){
    /* 判断队满操作 */
    if(temp->rear+1 == temp->front){
        printf("队满\n");
        return ;
    }

    /* 数据放入队尾 */
    temp->nums[temp->rear+1] = num;
    temp->rear = temp->rear+1;
    printf("%d元素入队\n", num);
}



int main(){
    int num;
    queue *data_queue = QueueInit();

    printf("入队操作\n\n");
    /* 插入数据元素10 */
    QueuePush(data_queue, 10);
    /* 插入数据元素11 */
    QueuePush(data_queue, 11);
    /* 插入数据元素12 */
    QueuePush(data_queue, 12);
    /* 插入数据元素13 */
    QueuePush(data_queue, 13);
    /* 插入数据元素14 */
    QueuePush(data_queue, 14);
    /* 遍历输出 */
    QueueShow(data_queue);

    printf("\n出栈队操作\n\n");
    /* 出队数据元素 */
    num = QueuePop(data_queue);
    /* 出队数据元素 */
    num = QueuePop(data_queue);
    /* 出队数据元素 */
    num = QueuePop(data_queue);
    /* 遍历输出 */
    QueueShow(data_queue);
    /* 出队数据元素 */
    num = QueuePop(data_queue);
    /* 出队数据元素 */
    num = QueuePop(data_queue);
    /* 出队数据元素 */
    num = QueuePop(data_queue);
    
    return 0;
}