【数据结构】线性表之《队列》超详细实现

一.队列的概念及结构

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

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

二.顺序队列与链队列

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

1.顺序队列

2.链队列

那是不是再用一个指针指向队尾就可以了呢？是的如下图：

这种链表结构完美的解决了尾插时效率低的问题。

三.链队列的实现

1.创建队列

先创建结构体（存放数据和先一个节点的地址）用来表示节点，再额外创建队列结构体（成员：队头指针和队尾指针），队头指针指向队列的队头，队尾指针指向队列的队尾。

typedef int qdatatype;

typedef struct queuenode
{
	qdatatype data;
	struct queuenode* next;
}qnode;

typedef struct queue
{
	qnode* head;
	qnode* tail;
}queue;

queue q;//q代表链队列

2.初始化队列

将队头指针和队尾指针初始化为null。

void queueinit(queue* pq)
{
	assert(pq);//断言
	pq->head = pq->tail = null;
}

3.入队

先是创建一个新的节点，存放数据和null指针，入队分两种情况：

1. 若队头和队尾指针都为null，则队头和队尾指针都指向新的节点。
2. 若队头和队尾指针不为null，则向队尾插入新的节点，再更新队尾指针。

void queuepush(queue* 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;
	}
}

4.出队

出队也有两种情况

1. 队列只有一个节点，先删除队头，再让队头和队尾指针指向null，防止队尾指针变成野指针。
2. 队列有多个节点，先保存队头的下一个节点指针，再删除队头，最后更新队头指针。

void queuepop(queue* pq)
{
	assert(pq);
	assert(pq->head != null);//队列不能为空

	//队列只有一个节点
	if (pq->tail->next == null)
	{
		free(pq->head);
		pq->head = pq->tail = null;
	}
	//队列有多个节点
	else
	{
		qnode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

5.获取队头元素

qdatatype queuefront(queue* pq)
{
	assert(pq);
	assert(pq->head != null);//队列不能为空
	return pq->head->data;
}

6.获取队尾元素

qdatatype queueback(queue* pq)
{
	assert(pq);
	assert(pq->tail != null);//队列不能为空
	return pq->tail->data;
}

7.队列的大小

定位队头节点，利用null这一条件遍历队列即可。

int queuesize(queue* pq)
{
	assert(pq);
	qnode* cur = pq->head;//定位队头节点
	int size = 0;
	while (cur != null)
	{
		size++;
		cur = cur->next;//更新cur
	}
	return size;
}

8.队列的判空

判断队头指针是否为null即可。

bool queueempty(queue* pq)
{
	assert(pq);
	return pq->head == null;
}

9.清空队列

定位队头节点，依次先后删除即可。

void queueclear(queue* pq)
{
	assert(pq);
	qnode* cur = pq->head;//定位队头节点
	while (cur != null)
	{
		qnode* next = cur->next;
		free(cur);//逐个删除
		cur = next;
	}
	pq->head = pq->tail = null;
}

10.销毁队列

void queuedestory(queue* pq)
{
	assert(pq);
	queueclear(pq);
	//注意不能释放pq，这不是动态开辟的地址，而是栈区的地址，所以清空与销毁没什么区别
}

四.队列的盲区

由于队列的特殊结构，只能遵循先进先出的原则，不允许随便遍历队列，否则就失去了队列的特点，只能用以下的代码得到数据：

while (!queueempty(&q))
{
	printf("%d ", queuefront(&q));
	queuepop(&q);
}

五.模块化源代码

1.queue.h

//#pragma once 防止头文件被重复包含
#ifndef __queue_h__
#define __queue_h__

#include<stdio.h>
#include<stdlib.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;
}queue;

void queueinit(queue* pq);//初始化队列

void queuepush(queue* pq, qdatatype x);//入队

void queuepop(queue* pq);//出队

qdatatype queuefront(queue* pq);//获取队头元素

qdatatype queueback(queue* pq);//获取队尾元素

int queuesize(queue* pq);//队列大小

bool queueempty(queue* pq);//队列判空

void queueclear(queue* pq);//清空队列

void queuedestory(queue* pq);//销毁队列
#endif

2.queue.c

#define _crt_secure_no_warnings 1

#include"queue.h"

void queueinit(queue* pq)
{
	assert(pq);//断言
	pq->head = pq->tail = null;
}

void queuepush(queue* 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;
	}
}

void queuepop(queue* pq)
{
	assert(pq);
	assert(pq->head != null);//队列不能为空

	//队列只有一个节点
	if (pq->tail->next == null)
	{
		free(pq->head);
		pq->head = pq->tail = null;
	}
	//队列有多个节点
	else
	{
		qnode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

qdatatype queuefront(queue* pq)
{
	assert(pq);
	assert(pq->head != null);//队列不能为空
	return pq->head->data;
}

qdatatype queueback(queue* pq)
{
	assert(pq);
	assert(pq->tail != null);//队列不能为空
	return pq->tail->data;
}

int queuesize(queue* pq)
{
	assert(pq);
	qnode* cur = pq->head;//定位队头节点
	int size = 0;
	while (cur != null)
	{
		size++;
		cur = cur->next;//更新cur
	}
	return size;
}

bool queueempty(queue* pq)
{
	assert(pq);
	return pq->head == null;
}

void queueclear(queue* pq)
{
	assert(pq);
	qnode* cur = pq->head;//定位队头节点
	while (cur != null)
	{
		qnode* next = cur->next;
		free(cur);//逐个删除
		cur = next;
	}
	pq->head = pq->tail = null;
}

void queuedestory(queue* pq)
{
	assert(pq);
	queueclear(pq);
	//注意不能释放pq，这不是动态开辟的地址，而是栈区的地址，所以清空与销毁没什么区别
}

3.test.c

#define _crt_secure_no_warnings 1

#include"queue.h"

enum //匿名枚举
{
	exit,
	push,
	pop,
	front,
	back,
	size,
	empty,
	clear
};

void menu()
{
	printf("*************队列*************\n");
	printf("****1.入队          2.出队****\n");
	printf("****3.队头          4.队尾****\n");
	printf("****5.大小          6.判空****\n");
	printf("****7.清空          0.退出****\n");
	printf("******************************\n");
}

int main()
{
	queue q;
	queueinit(&q);
	int select = 0;
	bool flag;
	qdatatype value;
	do
	{
		menu();
		printf("请选择您的操作：");
		scanf("%d", &select);
		switch (select)
		{
		case exit:
			printf("退出队列！\n");
			break;
		case push:
			printf("请输入您要入队的值：");
			scanf("%d", &value);
			queuepush(&q, value);
			break;
		case pop:
			queuepop(&q);
			break;
		case front:
			value = queuefront(&q);
			printf("队头元素值为：%d\n", value);
			break;
		case back:
			value = queueback(&q);
			printf("队尾元素值为：%d\n", value);
			break;
		case size:
			printf("队列的大小为：%d\n", queuesize(&q));
			break;
		case empty:
			flag = queueempty(&q);
			if (flag)
			{
				printf("队列为空！\n");
			}
			else
			{
				printf("队列不为空！\n");
			}
			break;
		case clear:
			queueclear(&q);
			break;
		default:
			printf("输入错误，请重新输入！\n");
			break;
		}
	} while (select);
	queuedestory(&q);
	return 0;
}

六.栈和队列必做oj题

1. 括号匹配问题
2. 用队列实现栈
3. 用栈实现队列

创作不易，如果能帮到你的话能赏个三连吗？感谢啦！！！