474 字
1 分钟
通过链表实现队列
利用链表实现队列
一、回顾
之前俺们用数组实现了队列，但是存在几个问题。
万一数组申请的内存太小，用完了咋办？万一数组申请的内存太大，队列用不了那么多，浪费了咋办？
二、痛点
对于队列来说，他的操作的时间复杂度都是O（1）
而链表在头部插入是O（1），在尾部却是O（n）
因此我们选择链表的一端做队头，一端做队尾的话，时间复杂度就不一样了。
这看上去有些冲突。🤔
三、解决痛点
既然我们无法做到尾插法的时间复杂度变成O（1），那么我们必须采取一些手段。
如果我们在尾部有个rear指针，就类似于头部有个head指针那样。那时间复杂度就能被轻松压到O（1）
要插入这个新节点，只需让300地址链接上350地址，改变rear指针指向即可。
四、c语言实现
#include<stdio.h>#include<stdlib.h>
struct Node{ int data; struct Node *next;};struct Node* front=NULL;struct Node* rear=NULL;void Enqueue(int x){ struct Node* temp=(struct Node*)malloc(sizeof(struct Node)); temp->data=x; temp->next=NULL; //针对空队列的情况 if(front==NULL&&rear==NULL){ front=rear=temp; return; } rear->next=temp; rear=temp;}
首先我们创建一个节点，走if分支，front和rear都指向它。
我们再链接一个节点，此时rear指针就会开始移动了！
rear->next=temp;你可能好奇为什么不写成front->next=temp;。确实，对于只有一个节点的时候来说可以这样，但是你再看上图，如果再增加一个节点，那肯定得用rear来关联了。
实现出队
void Dequeue(){ struct Node* temp=front; //处理空的情况 if(front==NULL)return; //只有一个节点的情况 if(front==rear){ front=rear=NULL; } else{ front=front->next; } free(temp);}这里不同于数组的是，要free我们申请的内存，要不然就会像茫茫大海里有依托漂浮的粑粑，你不知道它在哪，但是你能从海水里喝出味道来😡
部分信息可能已经过时