c语言实现队列

1、队列的定义
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

队头（head）：允许删除的一端，又称队首。
队尾（tail）：允许插入的一端。

2.c语言实现队列

创建结构体QueueNode这个结构体是创建节点的，节点由数据和指向下一个节点的指针构成的

第二个结构体是创建指向节点的两个指针，对头指针head和队尾指针tail
typedef int QueueDataType; typedef struct QueueNode { struct QueueNode* next;
QueueDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail;
}Queue;
队列的接口
void QueueInit(Queue* pq); //初始化队列 void QueueDestory(Queue* pq); //销毁队列 void
QueuePush(Queue* pq, QueueDataType x); //插入元素 void QueuePop(Queue* pq); //出队列
QueueDataType QueueFront(Queue* pq); //查看队头元素 QueueDataType QueueBack(Queue*
pq); //查看队尾元素 bool QueueEmpty(Queue* pq); //检查队列是否为空 int QueueSize(Queue* pq);
//查看队列的长度

1.初始化队列
void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; }
2.销毁队列

当队列不为空时，用一个代替对头往后访问的指针cur ，当cur不为空时，用一个新的节点del
接收cur指向的节点。将del节点释放并置为空，cur在往后走完成对队列的遍历，最后将对头指针和队尾指针都置为空指针
void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur)
{ QNode* del = cur; cur = cur->next; free(del); del = NULL; } pq->head =
pq->tail = NULL; }
3.插入元素

队列的性质插入元素只能是尾插，分为两种情况来看：1.队列为空 2.队列不为空

1. 队列为空时，先去malloc一个新节点，让对头和队尾都指向这个新节点

2. 当队列不为空时，malloc一个新节点，将新节点插入到tail指针的下一个位置，新的队尾指向新节点的下一个位置
void QueuePush(Queue* pq, QueueDataType x) { assert(pq); QNode* newnode =
(QNode*)malloc(sizeof(QNode)); //malloc一个新节点 if (newnode == NULL)
//判断节点是否malloc成功 { perror("malloc fail!!!"); exit(-1); //不成功直接退出程序 } else {
newnode->data = x; //新节点的数据为x newnode->next = NULL; //新节点指向空 } //如果队列为空 if
(pq->head ==NULL&& pq->tail==NULL)//说明队列空 { pq->head = pq->tail = newnode;
//都指向新节点 } else { pq->tail->next = newnode; pq->tail = pq->tail->next; } }

4.出队列（头删）

出队列也分为两种情况：1.队列有一个节点 2.队列有多个节点

1.一个节点：因为队列的节点是malloc出来的所以要将节点释放并置为空

2.多个节点：将队列的头指针赋值给del指针，头指针向后移动，释放掉del ,并置del为空，
void QueuePop(Queue* pq)//队列特性 头删 { assert(pq); assert(!QueueEmpty(pq));
//一个节点 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail =
NULL; } else//很多节点 { QNode* del = pq->head; pq->head = pq->head->next;
free(del); del = NULL; } }
5.访问对头

访问得有元素，需要判断队列是否为空
QueueDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq));
return pq->head->data; }
6.访问队尾

访问得保证队列有元素，需要判断队列是否为空
QueueDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty); return
pq->tail->data; }
7.判断队列是否为空
bool QueueEmpty(Queue* pq) { return pq->head == NULL; //空返回1 有元素0 }
8.查看队列的元素个数

查看队列元素的个数得保证队列有元素，生成一个新的指针接受队头指针，代替头指针往后访问队列,返回n 的数值就是队列的元素个数。

int QueueSize(Queue* pq) { assert(pq); assert(!QueueEmpty); int n = 0; QNode*
cur = pq->head; while (cur) { ++n; cur = cur->next; } return n; }
整体代码：

Queue.h
#include<stdio.h> #include<stdbool.h> #include<assert.h> #include<stdlib.h>
typedef int QueueDataType; typedef struct QueueNode { struct QueueNode* next;
QueueDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail;
}Queue; void QueueInit(Queue* pq); void QueueDestory(Queue* pq); void
QueuePush(Queue* pq, QueueDataType x); void QueuePop(Queue* pq); QueueDataType
QueueFront(Queue* pq); QueueDataType QueueBack(Queue* pq); bool
QueueEmpty(Queue* pq); int QueueSize(Queue* pq);
Queue.c
#include "Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail
= NULL; } void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head;
while (cur) { QNode* del = cur; cur = cur->next; free(del); del = NULL; }
pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, QueueDataType x) {
assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode ==
NULL) { perror("malloc fail!!!"); exit(-1); } else { newnode->data = x;
newnode->next = NULL; } //如果队列为空 if (pq->head ==NULL&& pq->tail==NULL)//说明队列空 {
pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail =
pq->tail->next; } } void QueuePop(Queue* pq)//队列特性 头删 { assert(pq);
assert(!QueueEmpty(pq)); //一个节点 if (pq->head->next == NULL) { free(pq->head);
pq->head = pq->tail = NULL; } else//很多节点 { QNode* del = pq->head; pq->head =
pq->head->next; free(del); del = NULL; } } QueueDataType QueueFront(Queue* pq)
{ assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QueueDataType
QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty); return pq->tail->data;
} bool QueueEmpty(Queue* pq) { return pq->head == NULL; //空返回1 有元素0 } int
QueueSize(Queue* pq) { assert(pq); assert(!QueueEmpty); int n = 0; QNode* cur =
pq->head; while (cur) { ++n; cur = cur->next; } return n; }
test.c
#include"Queue.h" void testqueue() { Queue q; QueueInit(&q); QueuePush(&q,
555); QueuePush(&q, 666); QueuePush(&q, 777); QueuePush(&q, 1); while
(!QueueEmpty(&q)) { printf("%d", QueueFront(&q)); QueuePop(&q); printf("\n"); }
QueueDestory(&q); } int main() { testqueue(); return 0; }

• « 上一篇：Linux查看端口占用情况
• » 下一篇：html常见面试题