阅读:0       作者:解学武

链队列的基本操作及C语言实现

队列,可以理解为遵循“先进先出”原则的线性表,即数据元素依次从表的一端进,从表的另一端出。

链队列,即用链式的存储结构(链表)实现的队列,其实现思想是:用链表的表头一端表示队列的队头,另一端表示队列的队尾(实现代码更加简单)。

反过来的话,当队列增加元素时,要采用头插法,在删除数据元素的时候,需通过遍历的方式摘除链表的最后一个结点。

需要注意的是,在实现链队列时要合理地控制队列两端指针的指向,避免“野指针”的出现。例如,当链队列中只剩有一个数据元素时,队尾指针指向的就是这个数据元素,被删除后,队尾指针指向的内存空间被释放,还有可能给别的程序使用。这时候,队尾指针如果不进行重定义,就会变成“野指针”。

链队列的实现代码如下:
#include <stdio.h>
#include <stdlib.h>
typedef struct QNode{
    int data;
    struct QNode * next;
}QNode;
QNode * initQueue(){
    QNode * queue=(QNode*)malloc(sizeof(QNode));
    queue->next=NULL;
    return queue;
}
QNode* enQueue(QNode * rear,int data){
    QNode * enElem=(QNode*)malloc(sizeof(QNode));
    enElem->data=data;
    enElem->next=NULL;
    //使用尾插法向链队列中添加数据元素
    rear->next=enElem;
    rear=enElem;
    return rear;
}
void DeQueue(QNode * front,QNode * rear){
    if (front->next==NULL) {
        printf("队列为空");
        return ;
    }
    QNode * p=front->next;
    printf("%d",p->data);
    front->next=p->next;
    if (rear==p) {
        rear=front;
    }
    free(p);
}
int main() {
    QNode * queue,*front,*rear;
    queue=front=rear=initQueue();//创建头结点
    //向链队列中添加结点,使用尾插法添加的同时,队尾指针需要指向链表的最后一个元素
    rear=enQueue(rear, 1);
    rear=enQueue(rear, 2);
    rear=enQueue(rear, 3);
    rear=enQueue(rear, 4);
    //入队完成,所有数据元素开始出队列
    DeQueue(front, rear);
    DeQueue(front, rear);
    DeQueue(front, rear);
    DeQueue(front, rear);
    DeQueue(front, rear);
    return 0;
}
运行结果:
1234队列为空