数据结构中的链式队列
链式队列是一种基于链表实现的队列数据结构，采用先进先出（FIFO）的原则。与顺序队列不同，链式队列通过动态分配内存存储元素，避免了固定容量限制。
链式队列的特点
- 动态扩容：无需预先分配固定内存空间，适合元素数量变化大的场景。
- 避免假溢出：顺序队列可能因数组空间不足导致假溢出，链式队列无此问题。
- 操作效率：入队和出队操作的时间复杂度均为O(1)。
链式队列的实现代码
/*队列(线性结构)是数据结构中的一种逻辑结构,属于操作受限的线性表， 其存储结构(物理结构)使其表现为"循环队列"和"链式队列"， 以下为链式队列的 C++ 代码实现*/ #include<iostream> using namespace std; #define ElemType int #define MaxSize 50//定义队列中元素的最大个数 typedef struct LinkNode{ //链式队列结点 ElemType data; struct LinkNode *next; }LinkNode; typedef struct{ //链式队列 LinkNode *front,*rear; //队列的队头和队尾指针 }LinkQueue; void InitQueue(LinkQueue &Q) { //初始化带头结点的链式队列 // Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); Q.front=Q.rear=new LinkNode;//建立头结点 Q.front->next=NULL; //初始为空 } bool QueueEmpty(LinkQueue Q) { if(Q.front==Q.rear) //判空条件 return true; else return false; } void EnQueue(LinkQueue &Q,ElemType x) {//入队 //C: LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode)); LinkNode *s=new LinkNode;//创建新结点 s->data=x; s->next=NULL; Q.rear->next=s; //插入链尾 Q.rear=s; //修改尾指针 } bool DeQueue(LinkQueue &Q,ElemType &x) {//出队 if(Q.front==Q.rear) //空队 return false; LinkNode *p=Q.front->next; x=p->data; Q.front->next=p->next; if(Q.rear==p) //若原队列中只有一个结点，删除后变空 Q.rear=Q.front; //C: free(p); delete p; return true; } int main(){//测试代码合理即可 LinkQueue Q; ElemType x; InitQueue(Q); // 初始化 // 入队：1、2、3 cout<<"顺序入队1，2，3"<<endl; EnQueue(Q,1); EnQueue(Q,2); EnQueue(Q,3); // 出队（先进先出） cout<<"出队"<<endl; while(DeQueue(Q,x)){ cout<<x<<endl; } // 判空 cout<<"队列是否为空:"<<(QueueEmpty(Q) ? "是" : "否")<<endl; return 0; }
