链式队列的入队与出队操作（C语言）_链队列的入队和出队

1.链队列入队

链式队列的实现思想同顺序队列类似，只需创建两个指针分别指向链表中队列的队头元素和队尾元素。

图所示为链式队列的初始状态，此时队列中没有存储任何数据元素，因此 top 和 rear 指针都同时指向头节点。
链队队列中，当有新的数据元素入队，只需进行以下 3 步操作：

1. 将该数据元素用节点包裹，例如新节点名称为 elem；
2. 与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；
3. 最后移动 rear 指针指向该新节点，即 rear=elem；

由此，新节点就入队成功了。
例如，在上图的基础上，我们依次将 {1,2,3} 依次入队，各个数据元素入队的过程如下图所示:

 2.链队列出队

 当链式队列中，有数据元素需要出队时，按照 “先进先出” 的原则，只需将存储该数据的节点以及它之前入队的元素节点按照原则依次出队即可。这里，我们先学习如何将队头元素出队。
  链式队列中队头元素出队，需要做以下 3 步操作：

1. 通过 top 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；
2. 将 p 节点（即要出队的队头节点）从链表中摘除；
3. 释放节点 p，回收其所占的内存空间；

  例如，在上图的基础上，我们将元素 1 和 2 出队，则操作过程如下图所示：

 总体代码：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef struct LinkNode{
    int data;
    struct LinkNode *next;
}LinkNode;
typedef struct LinkQueue{
    LinkNode *fronts,*rear;
}LinkQueue;
//初始化
int Init_LinkQueue(LinkQueue &Q)
{
    Q.fronts=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.fronts->next==NULL;
}
//入队
int EnQueue(LinkQueue &Q,int x)
{
    LinkNode *s;
    s=(LinkNode*)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}
//出队
int DeQueue(LinkQueue &Q,int &x)
{
    if(Q.fronts==Q.rear)
        return 0;
    LinkNode *q=Q.fronts->next;
    x=q->data;
    Q.fronts->next=q->next;
    if(Q.rear==q)
    {
        Q.rear=Q.fronts; //若原队列中仅有一个节点，删除后变空
    }
    free(q);
    return 1;
}
int show_Queue(LinkQueue Q)
{
    Q.fronts=Q.fronts->next;
    while(Q.fronts!=NULL)
    {
        printf("%d ",Q.fronts->data);
        Q.fronts=Q.fronts->next;
    }
}
int main()
{
    LinkQueue Q;
    Init_LinkQueue(Q);
    EnQueue(Q,1);
    EnQueue(Q,2);
    EnQueue(Q,3);
    show_Queue(Q);
    int a;
    DeQueue(Q,a);
    printf("%d\n",a);
    show_Queue(Q);
    cout << "Hello world!" << endl;
    return 0;
}