系列文章目录

线性结构（一）顺序表及其代码实现
线性结构（二）单链表及其代码实现
线性结构（三）头结点的循环双链表
线性结构（四）栈及其代码实现及OJ题
线性结构（五）队列及代码实现

---

前言

---

1.前言

1.1 队列介绍

队列也是一种线性结构，队列要求，队尾插入元素，队头删除元素。所以队列元素是“First In First Out”，也即FIFO.
由于队列只能在队头删除，队尾插入，那么记录尾指针效率更高；因此要记录头指针、尾指针、数据元素个数，多个数据我们考虑存在结构体中，因此要定义新的结构体代表队列。这种情况下，求队列长度无需遍历，时间复杂度为O(1)，无独有偶，单链表也可以这样处理，记录头指针和size，存在数据结构中，代表单链表。求单链表长度无需遍历，时间复杂度为O(1).
还有双向带头循环链表，或许有的小伙伴考虑头结点存储链表长度，但是如果链表数据类型是char，链表长度>127就溢出（溢出不等于截断，打个比方，截断是int赋给char，char存不下）了。再者，如果类型是double呢，链表长度为浮点数？好生奇怪。

1.2 代码实现

Queue.h

#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;
typedef	struct QueueNode//代表队列的一个结点
{
	QDataType data;
	struct QueueNode* next;
}QNode;
typedef	struct Queue//代表队列
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
bool QueueEmpty(Queue* pq);
void QueuePush(Queue* pq,QDataType x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#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,*next=NULL;
	while (cur)
	{
		next= cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		assert(pq->tail==NULL);
		pq->tail = pq->head = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head!=NULL);
	/*QNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
	if (pq->head == NULL)
		pq->tail = NULL;*/
	if (pq->head->next == NULL)//只剩一个元素时，尾删要置尾指针为NULL.
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

Test.c

#include "Queue.h"
int main()
{
	Queue q;
	QueueInit(&q);
	for(int i=0;i<5;i++)
		QueuePush(&q, i + 1);
	printf("%d\n", QueueBack(&q));
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);//队列的性质，一边出队，一边访问队头元素
	}
	printf("%d\n", QueueSize(&q));
	
	QueueDestroy(&q);
	return 0;
}

---

总结

队列在队尾入队，队头出队。一个很新的点就是，除定义表示结点的结构体之外，还定义表示队列的结构体，这也能运用到单链表中，但用头结点存储链表元素个数不可取。