【数据结构】队列（C语言实现）

数据结构】队列（C语言实现）"/>

【数据结构】队列（C语言实现）

📙 作者简介 ：RO-BERRY
📗 学习方向：致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识
📒 日后方向 : 偏向于CPP开发以及大数据方向，欢迎各位关注，谢谢各位的支持

队列

• 1. 队列的概念及结构
• 2. 队列的实现
• • 2.1 Queue.h
  • 2. Queue.c
  • • 队列初始化
    • 队列销毁
    • 队列入队列
    • 队列出队列
    • 获取队列头元素
    • 获取队列尾元素
    • 队列判空
    • 获取队列大小
• 3.源码
• • Queue.h
  • Queue.c

1. 队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

不方便理解可以想一下抽号机：每一个人都有一个号码，我们会按照来的顺序依次给号码，然后再抽号机里依次召唤号码，就是说先来的号码先被抽到，和医院患者挂号系统是一样的，也就是先进先出。

2. 队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

2.1 Queue.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;                //数据类型用QDataType，方便后期实现全局修改
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//队列进在队尾，出在队头，我们每次都需要知道队头和队尾，我们就可以再定义一个结构体
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;void QueueInit(Que* pq);   //队列初始化
void QueueDestory(Que* pq);    //队列销毁
void QueuePush(Que* pq, QDataType x);   //队列入队列
void QueuePop(Que* pq);    //队列出队列
QDataType QueueFront(Que* pq);   //获取队列头元素
QDataType QueueBack(Que* pq);    //获取队列尾元素
bool QueueEmpty(Que* pq);    //队列判空
void QueueSize(Que* pq);    //队列大小

2. Queue.c

队列初始化

void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}

队列销毁

void QueueDestory(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;      //将每一个结点都进行释放free(cur);cur = next;}pq->head = pq->tail = NULL;        //置空pq->size = 0;
}

队列入队列

void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));   //开辟if (newnode == NULL)       {perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}

队列出队列

void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}

获取队列头元素

QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}

获取队列尾元素

QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

队列判空

bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}

获取队列大小

void QueueSize(Que* pq)
{assert(pq);return pq->size;
}

3.源码

Queue.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;                //数据类型用QDataType，方便后期实现全局修改
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//队列进在队尾，出在队头，我们每次都需要知道队头和队尾，我们就可以再定义一个结构体
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;void QueueInit(Que* pq);   //队列初始化
void QueueDestory(Que* pq);    //队列销毁
void QueuePush(Que* pq, QDataType x);   //队列入队列
void QueuePop(Que* pq);    //队列出队列
QDataType QueueFront(Que* pq);   //获取队列头元素
QDataType QueueBack(Que* pq);    //获取队列尾元素
bool QueueEmpty(Que* pq);    //队列判空
void QueueSize(Que* pq);    //队列大小

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
void QueueDestory(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}
void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}
QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}
QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}
void QueueSize(Que* pq)
{assert(pq);return pq->size;
}