内容发布更新时间 : 2024/10/20 7:53:41星期一 下面是文章的全部内容请认真阅读。

C语言实现队列

定义 实现

定义结构 定义操作 创建队列

判断队列是否为空 访问队首元素 出队 入队 定义

在栈中提到，队列是操作受限制的特殊的线性表。 在队列的一端只能插入元素，这一端叫做队尾。 在队列的另一端只能删除元素，这一端叫做队首。

同样举个栗子：

在食堂排队打饭，跑的快的同学排在队列的前面，最先打到饭菜。后续到的同学只能依次排列在队尾。买到饭菜的同学离开队列叫做出队，进入队列等候叫做入队。食堂阿姨给队列中第一个同学打饭叫做访问队首元素。

总结：队列有先进先出的特性，FIFO（First In First Out）。每次只能在线性表的两端操作元素。 实现

考虑到每次出队和入队都要移动队首和队尾指针。若采用顺序存储，将会有可能造成顺序表前段部分存储单元的浪费。虽说可以采用循环队列的方式复用存储单元，若遇到队列满的情况，将队列扩容比较麻烦。因此建议用链表的方式实现队列。

定义结构

typedef int QueueType; struct LinkQueue {

QueueType key;

struct LinkQueue *next; };

typedef struct queueNode{

struct LinkQueue *head;//队列的头指针 struct LinkQueue *end; //队列的尾指针 }Queue;

这里定义了连个结构体，链表和队列。队列中只保存两个指针——队首、队尾。后面的入队、出队的操作，只需要操作这两个指针就好。

定义操作

创建队列

Queue createQueue() { Queue queue; queue.head = 0; queue.end = 0; return queue; }

采用静态方式分配队列存储单元。初始化队首和队尾指针。 判断队列是否为空

int isEmpty(Queue queue) {

if (queue.head == 0) return 0; else

return 1; }

队首指针指向空结点，表示队列为空。 访问队首元素-获取队列第一个元素

int getFirst(Queue queue, QueueType& elem) {

if (queue.head == 0) return 0;

elem = queue.head->key; return 1; }

队首指针可作为链表的头结点。通过头结点访问链表的第一个结点。 出队-退出队列

int exitQueue(Queue& queue, QueueType& val) { if (isEmpty(queue) == 0) //空队列 return 0;

struct LinkQueue* node = queue.head; queue.head = node->next; node->next = 0; val = node->key; free(node);

if (queue.head == 0) queue.end = 0; return 1; }

通过队首指针，删除队列第一个结点。如果删除后队列为空，将队尾指针置空，否则队尾指针仍然指向最后一个元素。队列为空，删除失败，返回0 。删除成功返回1。 入队-进入队列

int enterQueue(Queue& queue, QueueType key) {

struct LinkQueue* node = (struct LinkQueue*) malloc( sizeof(struct LinkQueue)); if (node == NULL) return 0; node->key = key; node->next = 0;

if (queue.end == 0) { queue.end = node; } else {//修改队尾指针

queue.end->next = node; queue.end = node; }

if (queue.head == 0) { queue.head = node; }

return 1; }

队列为空时，队首和队尾指针指向同一个结点就好。队列不为空时，修改队尾指针指向新插入的结点。入队成功返回1，入队失败返回0。 最后附上头文件的定义

#ifndef QUEUE_H_ #define QUEUE_H_

typedef int QueueType; struct LinkQueue { QueueType key;

struct LinkQueue *next; };

typedef struct queueNode {

struct LinkQueue *head; //队列的头指针 struct LinkQueue *end; //队列的尾指针 } Queue;

创建队列

Queue createQueue();

判断队列是否是空 int isEmpty(Queue);