数据结构-队列的实现（C语言版）

前言

        队列是一种特殊的线性表，它只允许在一端对数据进行插入操作，在另一端对数据进行删除操作的特殊线性表，队列具有先进先出的（FIFO）的 特性，进行插入操作的一端称为队尾，进行删除操作的一端称为队头。

1.队列的特性

        队尾：元素在队尾入队。插入操作。

        队头：元素在队头出对。删除操作。

如图：

2.队列的实现

         队列可以用 数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低，需要挪动数据，因此这里采用链表的方式来进行队列的实现。

//queue.h

#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* _next;QDataType _data;
}QueueNode;
typedef struct  Queue//队列的结构
{QueueNode* _head;//头指针QueueNode* _tail;//尾指针
}Queue;void QueueInit(Queue* qu);//初始化栈void QueueDestory(Queue* qu);//摧毁栈void QueuePush(Queue* qu,QDataType data);//入队void QueuePop(Queue* qu);//出队QDataType QueueFront(Queue* qu);//返回队头元素
QDataType QueueBack(Queue* qu);//返回队尾元素size_t QueueSize(Queue* qu);//队列长度bool QueueEmpty(Queue* qu);//判断队列是否为空

//queue.c

void QueueInit(Queue* qu)//初始化栈
{qu->_head = qu->_tail = NULL;
}
void QueueDestory(Queue* qu)//摧毁栈
{//确保指针有效assert(qu);QueueNode* cur = qu->_head;while (cur){QueueNode* next = cur->_next;free(cur);}
}
void QueuePush(Queue* qu,QDataType data)//入队
{if (qu->_head == NULL){qu->_head = (QueueNode*)malloc(sizeof(QueueNode));qu->_tail = qu->_head;qu->_head->_next = NULL;qu->_head->_data = data;}else{//尾部入数据QueueNode* cur = qu->_tail;QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));cur->_next = newNode;newNode->_next = NULL;qu->_tail = newNode;newNode->_data = data;}
}
void QueuePop(Queue* qu)//出队
{//队头出数据QueueNode* head = qu->_head;qu->_head = head->_next;free(head);
}
QDataType QueueFront(Queue* qu)//返回队头元素
{return qu->_head->_data;
}
QDataType QueueBack(Queue* qu)//返回队尾元素
{return qu->_tail->_data;
}
size_t QueueSize(Queue* qu)//队列长度
{assert(qu);//确保指针存在QueueNode* cur = qu->_head;size_t size = 0;while (cur){++size;cur = cur->_next;}return size;
}
bool QueueEmpty(Queue* qu)//判断队列是否为空
{return !qu->_head;
}

 

3.测试部分

        

void TestQueue()
{Queue qu;QueueInit(&qu);QueuePush(&qu, 1);QueuePush(&qu, 2);QueuePush(&qu, 3);QueuePush(&qu, 4);QueuePush(&qu, 5);QueuePush(&qu, 6);QueuePush(&qu, 7);QueuePush(&qu, 8);while (!QueueEmpty(&qu)){printf("%d ", QueueFront(&qu));QueuePop(&qu);}QueueDestory(&qu);
}