引入

我们学习了什么是队列，也了解了队列的一些基本特性，以及如何初始化一个队列，今天我们来看看如何创建和删除以及销毁一个队列。

创建一个队列

创建一个队列要注意以下两点

  • 创建一个头结点
  • 队列的头指针、尾指针都指向该结点
  • 因为队列是空的，这样就创建完成了
#include <stdio.h>
#include <stdlib.h>
#define sizeof(struct Queue)

struct Queue{
int data;
struct Queue *next;
};

struct Queue_link{
struct Queue *front;
struct Queue *rear;
}

void init(Queue_link *q){
q->frout=q->rear=(struct Queue *)malloc(LEN);
if(!q->front){
exit(0);
}
q->frount->next=NULL;
}

代码注意

  • 结点开辟的内存是结点结构体，所以头尾指针内存储的，都是结点结构体的内存地址。
  • 因为一开始头部指针指向的结点没有指向，所以为 NULL

插入队列

void init(Queue_link *q , int e){
struct Queue *temp;
temp=(struct Queue *)malloc(LEN);
temp->data=e;
temp->next=NULL;
q->rear->next=temp;
q->rear=temp;
}

代码注意，其实思路是这样的

  • 先创建一个新结点，把要插入的内容先赋值
  • 新节点因为在队尾嘛，所以 next 为 NULL
  • 然后把老尾巴的 next 指向新结点
  • 尾指针指向新节点

注意
front 和 rear 指向的相同，并且 next 都是 NULL 了
rear 指向的结点的下一个指向了新结点
表示 front 的 next 也指向了插入的第一个结点

出队列

int out(struct Queue_link *q){
struct Queue *temp;
//判断队列是否为空
if(q->front==q->rear){
printf("队列为空！");
return 0;
}
//出队操作，先把要出队的指向一个 temp 临时结点
temp=q->front->next;
int i=temp->data;
//p 的头指针存储的头部的指向，指向为出队结点的下一个
q->front->next=temp->next;
//判断出队后队列是否为空，尾部指向的是不是刚才出队的那个
if(q->rear==temp){
q->rear=q->front;
}
free(temp);  //释放已经出队的内存空间
return i;
}

代码思路是

  • 先判断队列是不是空的，空的就直接报错
  • 然后设置一个临时结点，把排在一个位的结点取得
  • 然后把刚才出队结点的下一个结点位置赋值给头部
  • 判断一下尾指针指向的是不是这个出队的结点，如果是那证明队列空了
  • 队列空了，则需要将头尾指针划等号，即指都向头部。
  • 然后把刚才出队的结点的内存空间释放掉。

销毁队列

因为队列是建立在内存的动态存储区中，所以当队列不再使用时，要及时的进行释放，其实不仅仅是队列，只要不用，尽量都及时释放。

void Destroy(struct Queue_link *q){
while(q->front){
q->rear=q->front->next;  //让 rear 指针先存储头部的结点
free(q->front);  //释放 front
q->front = q->rear;  //让头部再次指向下一个，直到遇到 NULL
}
}

思路很简单

  • 先让尾指针存着第 n +1 个结点的地址
  • 然后释放头指针存储的第 n 个结点
  • 然后让头指针再次指向这个 n+1的地址
  • 循环往复即可

全部代码

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct Queue)

struct Queue{
    int data;
    struct Queue *next;
};

struct Queue_link{
    struct Queue *front;
    struct Queue *rear;
};

void init(struct Queue_link *q){
    q->front=q->rear=(struct Queue *)malloc(LEN);
    q->front->next=NULL;
}

void insert(struct Queue_link *q , int e){
    struct Queue *temp;
    temp=(struct Queue *)malloc(LEN);
    temp->next=NULL;
    temp->data=e;
    q->rear->next=temp;
    q->rear=temp;
}

int out(struct Queue_link *q){
    if(q->front==q->rear){
        printf("错误！\n");
        return 0;
    }
    struct Queue *temp;
    temp=q->front->next;
    int i=temp->data;
    q->front->next=temp->next;
    if(temp==q->rear){
        q->front=q->rear;
    }
    free(temp);
    return i;
}

int main(){
    struct Queue_link *p;
    p=(struct Queue_link *)malloc(LEN);
    init(p);
    insert(p, 1);
    insert(p, 2);
    insert(p, 3);
    printf("%d\n",out(p));
    printf("%d\n",out(p));
    printf("%d\n",out(p));
}

输出结果
1
2
3

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。