如何用C语言实现链表结构的队列数据？

本文共计1308个文字，预计阅读时间需要6分钟。

C语言实现链表的数据结构

1.写在前言

队列是一种先进先出（FIFO）的数据结构，与栈类似，也是线性表的一种。队列的操作包括入队和出队，其中，元素总是从队列的一端加入，从另一端退出。本文将介绍如何使用C语言实现队列，并遵循先入先出的原则。

2. 代码实现c#include #include

// 定义队列的结构体typedef struct Queue { int *array; int front; int rear; int maxSize;} Queue;

// 初始化队列void initQueue(Queue *q, int size) { q->array=(int *)malloc(size * sizeof(int)); q->front=0; q->rear=0; q->maxSize=size;}

// 判断队列是否为空int isEmpty(Queue *q) { return q->front==q->rear;}

// 判断队列是否已满int isFull(Queue *q) { return (q->rear + 1) % q->maxSize==q->front;}

// 入队操作void enqueue(Queue *q, int data) { if (isFull(q)) { printf(Queue is full!\n); return; } q->array[q->rear]=data; q->rear=(q->rear + 1) % q->maxSize;}

// 出队操作int dequeue(Queue *q) { if (isEmpty(q)) { printf(Queue is empty!\n); return -1; } int data=q->array[q->front]; q->front=(q->front + 1) % q->maxSize; return data;}

// 遍历队列void traverseQueue(Queue *q) { if (isEmpty(q)) { printf(Queue is empty!\n); return; } for (int i=q->front; i !=q->rear; i=(i + 1) % q->maxSize) { printf(%d , q->array[i]); } printf(\n);}

// 释放队列内存void freeQueue(Queue *q) { free(q->array);}

// 主函数int main() { Queue q; initQueue(&q, 5); enqueue(&q, 1); enqueue(&q, 2); enqueue(&q, 3); enqueue(&q, 4); enqueue(&q, 5); enqueue(&q, 6); // 队列已满，无法继续入队

traverseQueue(&q); printf(Dequeue: %d\n, dequeue(&q)); printf(Dequeue: %d\n, dequeue(&q));

traverseQueue(&q);

freeQueue(&q); return 0;}

C语言数据结构链表队列的实现

1.写在前面

　　队列是一种和栈相反的，遵循先进先出原则的线性表。

　　本代码是严蔚敏教授的数据结构书上面的伪代码的C语言实现代码。

　　分解代码没有包含在内的代码如下：

#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 typedef int QElemtype; typedef int status;

2.代码分解

2.1对队列和节点的结构定义

typedef struct QNode //对节点的结构定义 { QElemtype data; struct QNode *next; }QNode,*QueuePtr; typedef struct{ //对队列的结构定义 QueuePtr head; QueuePtr rear; }LinkQueue;

　　|说明：

　　　　1.队列的节点首先要保存元素，其次要指引下一个元素的位置，这是实现线性存储的基础也是关键。

　　　　2.队列中定义了两个节点指针，第一个 head 用来表示 队头，允许移除元素。与之相反的是 rear 用来表示 队尾，允许插入元素。

　　　　3.为什么这么定义？

2.2 初始化和回收队列

status initQueue(LinkQueue* que) //初始化队列 { que->head=que->rear=(QueuePtr)malloc(sizeof(QNode)); if(!que->head) //这段代码对队列里面的用户自定义数据类型进行了初始化 return ERROR; return OK; } status destoryQueue(LinkQueue* que) //回收队列 { while(que->head) { que->rear = que->head->next; free(que->head); que->head=que->rear; } return OK; }

　　|说明：

　　　　1.初始化很简单，就是为队列内的两个重要节点分配空间。

　　　　2.队列的回收，思路很巧妙

　循环条件是 队列的队头节点 head 存在 　　　　{ 　　　　　　此处rear起到临时变量的作用，不断指向head->next的同时，释放head。这样处理可以干净的把包含头节点在内的队列清理干净。 　　 　}

2.3 添加和删除元素

status enQueue(LinkQueue* que,QElemtype e) { QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); if(!p) //若未能申请到空间，便退出 return ERROR; p->data=e; p->next=NULL; que->rear->next = p; que->rear=p; return OK; } status delQueue(LinkQueue* que,QElemtype *t) { if(que->rear==que->head) return ERROR; //队列为空 QueuePtr p = que->head->next; *t=p->data; que->head->next=p->next; if(que->rear==p) //这个判断是 确保在清空队列的时候，让rear指针归位。 que->rear=que->head; free(p); return OK; }

　　|说明：

　　　　1.添加元素的思路：新建一个节点，并给其赋值（data，next）。让队列的尾部相接此节点，同时更新尾部节点。

　　　　2.删除元素的思路：首先判断节点是否为空？然后用临时节点从队头获取到第一个节点，即head->next，（我们的head节点并不保存元素），获取其地址后，更新队头节点所指的第一个节点获取值后释放该地址空间。

2.4 遍历队列和测试方法

status viewQueue(LinkQueue* que) { if(que->rear == que->head) return ERROR; QueuePtr p =que->head->next; while(p) { printf("val:%d",p->data); p=p->next; } return OK; } int main(int argc, char **argv) { LinkQueue myQueue; initQueue(&myQueue); for(int i=1;i<=5;i++) enQueue(&myQueue,i); viewQueue(&myQueue); QElemtype a; for(int i=0;i<5;i++) { delQueue(&myQueue,&a); printf("%d\n",a); } destoryQueue(&myQueue); printf("fuck !"); return 0; }