【数据结构——队列的实现（单链表）】

一.队列

1.1队列的概念及结构

二.队列的实现

2.1 头文件的实现——（Queue.h）

Queue.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化/销毁
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);//出队/入队
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
//获取队头元素/队尾元素
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
//判空/统计队列元素个数
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

2.2 源文件的实现—— （Queue.c）

Queue.c

#include"Queue.h"//初始化/销毁
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* Next = cur->next;free(cur);cur = Next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}//队尾入队/队首出队
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* Newnode = (QNode*)malloc(sizeof(QNode));if (Newnode == NULL){perror("malloc fail");return;}Newnode->val = x;Newnode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = Newnode;}else{pq->ptail->next = Newnode;pq->ptail = pq->ptail->next;}pq->size++;
}
void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);QNode* del = pq->phead;pq->phead = pq->phead->next;free(del);del = NULL;if (pq->phead == NULL)pq->ptail = NULL;pq->size--;}//获取队头元素/队尾元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;}
//判空/统计队列元素个数
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

2.3 源文件的实现—— （test.c）

test.c

#include"Queue.h"int main()
{Queue S;QueueInit(&S);QueuePush(&S, 1);QueuePush(&S, 2);printf("%d ", QueueFront(&S));QueuePop(&S);QueuePush(&S, 3);QueuePush(&S, 4);printf("%d ", QueueFront(&S));QueuePop(&S);QueuePush(&S, 5);while (!QueueEmpty(&S)){printf("%d ", QueueFront(&S));QueuePop(&S);}QueueDestroy(&S);
}

三.队列的实际数据测试展示

1.出入队列的方式：队尾进入，对首出队列。
2.出队列和入队列的关系是：一对一的。

3.1正常出队列入队列

3.2 入队列的同时存在出队列