Linux C语言高级编程数据结构队列之链式队列及其使用实例（2）

简 介

本章主要介绍队列中的链式队列这种数据结构，主要包括链式队列的概念、链式队列的操作及其代码实现。

链式队列概念

链式队列：是采用链式存储结构的队列，即使用一组不要求连续的存储空间来模拟队。每个队列元素为一个节点， 每个节点中包含两个域，一个是数据域，用于存储队列元素的数据；另一个是指针域，用于存储下一个队列元素的地址。

链式队列的基本操作

链式链队的基本操作包括：

1） 初始化队列，在初始化操作中将队头、队尾指针置空。

2） 判断队空，判断队首指针(front)是否为空。

3） 入队，在队中加入一个数据元素。

4） 出队，在队中删除一个数据元素。

5） 取队首元素，将队首元素取出，但并不在队中删除该元素。

链式队列使用实例

1、定义链式队列节点

typedef int Data;

struct Queue {

Data data;

//指向下一个队元素的位置

struct Queue *next;

};

2、链式队列操作使用实例

//链式队列定义及其使用演示

#include

#include

#include

//定义队列元素

typedef int Data;

struct Queue {

Data data;

struct Queue *next;

};

/*初始化链式队列,将队头、队尾指针初始化为NULL，表示为空栈。

函数有两个形参，都是队元素结构体指针的指针。使用指针的指针，因为队头、队尾指针在函数执行过程中会被置空，

而这种变化需要带回主函数。*/

void init(struct Queue** front, struct Queue** rear)

{

*front = NULL;

*rear = NULL;

}

//判断队列是否为空即判断队头或队尾是否为空

bool empty(struct Queue* node)

{

return node == NULL;

}

//入队，就是在队中加入一个结点

/*如果队尾指针不为空，则将新创建的队元素节点加入到队中原队尾元素的后面，成为新的队尾元素，

并将队尾指针指向新创建的队元素节点。如果队尾指针为空，则表示此时队中没有元素，

所以直接将队尾指针指向新创建的队元素节点即可。并且需要判断队头指针是否为空，如果为空，

则表示队中没有元素，此时入队的元素为队中的唯一一个元素，所以此时队头、队尾指针均指向它。*/

void push(struct Queue** front, struct Queue** rear, DataType d)

{

//动态分配一个队列节点

struct Queue *newNode = (struct Queue*)malloc(sizeof(struct Queue));

//将传入的数据赋值给新的节点

newNode->data = d;

newNode->next = NULL;

if (*rear != NULL)

(*rear)->next = newNode;

*rear = newNode;

if (*front == NULL)

*front = *rear;

}

//出队操作本质上就是在队中删除一个结点

/*用一个临时指针保存原队头指针指向的队元素地址，即出队元素的地址，然后将队头指针指向下一个元素，

这样队中就减少了一个元素。最后释放临时指针指向的元素，即释放出队元素所占的存储空间。*/

void pop(struct Queue** front, struct Queue** rear)

{

if (empty(*rear))

return;

struct Queue *tempNode = *front;

*front = (*front)->next;

free(tempNode);

/*判断删除一个队元素后队是否为空如果队列中没有元素了，也应该将队尾指针置为空，否则队尾指针将是野指针。*/

if (*front == NULL)

*rear = NULL;

}

/*取队首元素是将队头节点的数据返回。注意，在取队首元素时，首先要判断队是否为空，空队是没有数据元素的。*/

void topData(struct Queue* front, DataType* data)

{

if (empty(front))

return;

*data = front->data;

}

int main()

{

struct Queue *front, *rear;

init(&front, &rear);

push(&front, &rear,10);

push(&front, &rear,30);

push(&front, &rear,20);

while (!empty(front)) {

int data;

topData(front, &data);

printf("data=%d ", data);

pop(&front, &rear);

}

printf("\n");

return 0;

}