当前位置：首页 > article >正文

数据结构——栈和队列（2）

article 2024/12/23 23:28:07

作者：几冬雪来

时间：2023年3月22日

内容：数据结构栈和队列知识讲解

前言：

1.队列的概念及构成：

2.队列的插入和删除操作：

3.队列的实现：

1.创建文件：

2.定义结构体：

3.初始化队列：

4.删除链表：

5.尾插：

6.头插：

7.取size个数：

8.判断链表是否为空：

9.取队头与队尾的数据：

10.打印数据：

11.代码：

结尾：

前言：

在上一篇博客中我们学习了栈和队列中的栈那部分知识，并且也上手写代码操作了一番。但是既然这个板块的标题为栈和队列，那么这里肯定不止栈这一块的内容，这一篇博客我们就来讲解一下——队列。

1.队列的概念及构成：

首先对比起这块知识的栈的后入先出原理不一样并且只有一端初入的构造也不一样。队列是两端都可以进行使用，并且不是后入先出而是先入先出。

2.队列的插入和删除操作：

既然我们在这里说了队列对比栈，它的插入元素和删除元素的方法是不一样的，那么具体是在哪里不一样？我们画一个图来对其进行讲解和说明。

在队列中，我们虽然表明是两端都能使用，但是它并不能给我们随心所欲的使用，它只允许在一端进行插入数据的操作，在另一端进行删除数据的操作。入队列的进行插入操作的一端被我们称为队尾，相同的进行删除操作的一端则被我们称为队头。

在这里，删除操作又被我们称为出队，插入操作则称为入队。

3.队列的实现：

那么我们的队列又是怎么实现的？回想起在实现栈的开头，我们有数组或者链表两种形式来实现，在栈那里选择了数组形式，而在这里实现队列中，因为我们要进行出队和入队两种操作，很明显数组是不太合适的，因此在这我们选择用链表的形式来实现。

1.创建文件：

在这里我们依旧开始的时候创建3个文件，一个.h文件和两个.c文件。

2.定义结构体：

文件创建好了之后因为这里我们选择使用的是单向链表，要存放多个元素，因此这里要运用到结构体。

这里定义两个结构体，第一个结构体存放一个指针和一个整形结构，因为是单链表在队列中要进行出队和入队两个操作，这里就还要定义一个头结点和一个尾结点，每一个节点的类型是QNode类型，也就是头和尾结点都存放查找下一个位置的指针和该点的数据。接下来我们就将书写队列所要用到的操作都写出来讲解一下。

3.初始化队列：

实现队列我们用链表来书写它，那么和链表的形式相同，开始的时候要将链表进行初始化定义的操作。

因为要对链表插入元素，它的里面才有数据，因此链表一开始就为空。所以这里头结点和尾结点都初始化为空，size的个数也为空。

4.删除链表：

接下来我们要书写代码运行结束后所需要的操作了，那就是删除代码中的数据。

这里创建一个新指针，指向的是我们的头结点的位置，接下来循环如果头结点不为空的话，在循环中再创建一个指针来保存头结点后的下一个结点的位置，然后将cur进行释放，最后将cur指向next，也就是原头结点下一个结点的位置。如果cur为空了，这里头结点和尾结点都置空，size改为0就行了。

5.尾插：

在队列中有出队和入队两种操作，相等于我们的头删和尾插操作，这里我们就来书写一下尾插操作的代码。

尾删操作，开始我们要对要插入的新结点申请空间。如果申请失败的话要进行判断，下来就是我们要插入的值放入结点中，因为是尾插，所以结点的next定义为空，接下来因为一开始我们的链表为空，所以第一个数据直接放进去就行了，然后将头结点和尾结点的位置都定义为这个指针，如果头结点不为空这里说明里面有数据了，我们就需要进行尾插操作了。

6.头插：

讲解完了尾插操作，那这里就把头插的操作一起讲解了。

头删操作在断言方面我们还需要对头是否为空进行断言。接下来就是判断，如果头结点指向的next为空的话，这里就说明我们的链表中只有一个数据，在这里将它释放，头尾结点置空就行，如果next不是空的话就依次删除，创建一个指针保存下一个结点，将原头结点置空，再让头结点指向我们创建的next。

7.取size个数：

这里要求我们去链表中元素的个数，这里很简单。

我们进行断言后直接返回size即可。

8.判断链表是否为空：

在我们进行某些操作的时候，头结点可能或者尾结点可能出现越界访问的操作也可能会出现为空的情况，这里我们要对其进行一个判断。

实现这个操作有两种方法，一种就是判断头和尾结点是否为空，另一种则是判断我们的size个数是否为0。

9.取队头与队尾的数据：

在写队列的时候，有时候我们需要取队头或者队尾的数据。

在这里我们的代码也是简单明了，进行两次断言后直接取数据即可。

10.打印数据：

在书写完了我们上边的一系列代码操作的代码之后，下面我们就要来输入几个数据验证我们的代码是否正确。

在这里我们先创建一个结构体，结构体需要进行初始化。接下来就是我们的尾插操作，尾插过后进入循环来打印数据，如果头和尾结点都不为0的话，进入循环。然后取出队头的数据，接下来就将原队头的数据删除后打印下一个数据。

程序结束后我们要将其进行释放。

从结果上来看，我们的代码并没有什么错误。

11.代码：

Queue.h文件

#pragma once


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int QDatatype;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDatatype data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq,QDatatype x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
QDatatype QueueFront(Queue* pq);
QDatatype QueueBack(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;
	while (cur)
	{
		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 (newnode == NULL)
	{
		perror("malloc fail");
		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;
	}
}

//头删
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)
	{
		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;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	//return pq->size == 0;
	return pq->head == NULL && pq->tail == NULL;
}
//取队头数据
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);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
	QueueDestroy(&q);
	return 0;
}