数据结构之队列详解

1.队列的概念以及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFo(Frist in Frist out)的特性

入队列：进行插入才操作的一端称为队尾

出队列：进行删除操作的一端称为队头

2.队列的实现

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

队列常见的基本操作：

//初始化
void QueueInit(Queue* pq);
//清空队列成员
void QueueDestroy(Queue* pq);
//队尾插入元素
void QueuePush(Queue* pq, QDataType x);
//删除队队头元素，队列先进先出
void QueuePop(Queue* pq);
//获取队头元素
int QueueFront(Queue * pq);
//获取队尾元素
int QueueBack(Queue* pq);
//获取队列中有效与元素个数
int QueueSize(Queue* pq);
//查看队列是否为空
bool QueueEmpty(Queue* pq);

每个功能的实现以及解释

实现队列这里我们使用的是动态顺序表

->1.初始化队列

//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}

->2.清空队列成员

//清空队列成员
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;//QNode* cur = pq->head->next;while (cur){/*free(pq->head);pq->head = cur;cur = cur->next;*/QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}

->3.队尾插入元素

//队尾插入元素
void QueuePush(Queue* pq, QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (NULL == newnode){perror("QueuePsuh::malloc");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}

->4.删除队队头元素，队列先进先出

//删除队列成员，队列先进先出
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);//第一种方法//Queue* cur = pq->head;//if (cur->next == NULL)//{//	free(cur);//	pq->head = pq->tail = NULL;//}/*else{pq->head = cur->next;free(cur);cur = NULL;}*///第二种方法QNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL){pq->tail = NULL;}pq->size--;
}

->5.获取队头元素

//获取队头成员
int QueueFront(Queue* pq)
{assert(pq);assert(pq->head);return pq->head->data;
}

->6.获取队尾元素

//获取队尾成员
int QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

->7.获取队列中有效元素个数

//获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

->8.查看队列是否为空

//查看队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0; //pq->head == NULL && pq->tail == NULL
}

3.完整代码

Queue.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>typedef int QDataType;typedef struct QListNode 
{struct QListNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;QDataType size;
}Queue;//初始化
void QueueInit(Queue* pq);
//清空队列成员
void QueueDestroy(Queue* pq);
//队尾插入队列
void QueuePush(Queue* pq, QDataType x);
//删除队队头元素，队列先进先出
void QueuePop(Queue* pq);
//获取队头元素
int QueueFront(Queue * pq);
//获取队尾元素
int QueueBack(Queue* pq);
//获取队列中有效与元素个数
int QueueSize(Queue* pq);
//查看队列是否为空
bool QueueEmpty(Queue* pq);

Queue.c

#include "queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;//QNode* cur = pq->head->next;while (cur){/*free(pq->head);pq->head = cur;cur = cur->next;*/QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}//插入队列成员
void QueuePush(Queue* pq, QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (NULL == newnode){perror("QueuePsuh::malloc");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}//删除队列成员，队列先进先出
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);//Queue* cur = pq->head;//if (cur->next == NULL)//{//	free(cur);//	pq->head = pq->tail = NULL;//}/*else{pq->head = cur->next;free(cur);cur = NULL;}*/QNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL){pq->tail = NULL;}pq->size--;
}//获取队头成员
int QueueFront(Queue* pq)
{assert(pq);assert(pq->head);return pq->head->data;
}//获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}//获取队尾成员
int QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}//查看队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0; //pq->head == NULL && pq->tail == NULL
}

test.c

#include "queue.h"int main()
{Queue st;QueueInit(&st);QueuePush(&st, 1);QueuePush(&st, 2);QueuePush(&st, 3);QueuePush(&st, 4);QueuePush(&st, 5);while (!QueueEmpty(&st)){printf("%d ", QueueFront(&st));QueuePop(&st);}printf("\n");return 0;
}

测试结果: