【算法与数据结构】 C语言实现单链表队列详解

文章目录

• 📝队列
• 🌠 数据结构设计
• • 🌉初始化队列函数
• 🌠销毁队列函数
• • 🌉入队函数
• 🌠出队函数
• • 🌉获取队首元素函数
• 🌠获取队尾元素函数
• • 🌉 判断队列是否为空函数
  • 🌉获取队列大小函数
• 🌠测试
• • 🌉 总源代码
• 🚩总结

📝队列

前面我们学习了队列的顺序表的实现，本节将用单链表实现队列。
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。下面我们先复习一下队列的基本概念：
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

🌠 数据结构设计

首先，我们需要定义队列节点的数据结构和队列的数据结构：

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

// 定义队列节点数据结构
typedef int QDataType;//定义了一个新的数据类型 QDataType

typedef struct QueueNode 
{
    QDataType* data;//数据指针
    struct QueueNode* next;//指向下一个节点的指针。
} QNode;

当我们去定义队列的出队和入队时需要用到二级指针，这样传递指针的指针操作起来会有些繁琐，也不能更符合队列的逻辑结构，二级指针代码如下：

//入队列
void QueuePush(QNode** pphead, QNode** pptail);
//出队列
void QueuePop(QNode** pphead, QNode** pptail);

虽然使用指向指针的指针也可以实现队列的功能，但是使用结构体封装的方式更符合常见的数据结构和面向对象编程的思想，能够提高代码的可读性、可维护性和易用性。

// 定义队列数据结构
typedef struct Queue 
{
    QNode* phead;//指向队列的头节点（队首）
    QNode* ptail;//指向队列的尾节点（队尾）。
    int size;//表示队列中元素的数量。
} Queue;

对于队列这种数据结构，使用指向队列头部和尾部的指针以及队列大小的方式进行封装有以下好处：

1. 封装性更好：

   • 使用 Queue 结构体将队列的头部指针、尾部指针和大小封装在一起，更符合面向对象编程的思想，提高了代码的封装性和可维护性。
   • 将队列的相关信息放在一个结构体中，使得对队列的操作更加直观和清晰，降低了出错的可能性。

2. 操作更加直观：

   • 在进行队列操作时，使用 Queue 结构体可以直接通过 phead 和 ptail 指针来操作队列的头部和尾部，而无需传递指向指针的指针。这样使得代码更加清晰，不易出错。

3. 提高代码的可读性和可维护性：

   • 使用 Queue 结构体可以将队列的相关信息集中在一起，使得代码更加清晰易读。
   • 在函数参数中传递 Queue* 类型的指针，比传递指向指针的指针更加直观和易懂，减少了理解代码的难度。

由于队列是先进先出，并且单向的，而头节点是哨兵位，要也可以不要也可以，本文没有用多出使用一个头节点。

🌉初始化队列函数

先确保传入的队列指针 pq 不为空，将队列的头指针、尾指针置为空，大小置为0。

void QueueInit(Queue* pq)
{
  assert(pq); // 断言队列指针是否为空
  pq->phead = NULL; // 初始化头节点指针为空
  pq->ptail = NULL; // 初始化尾节点指针为空  
  pq->size = 0; // 初始化队列大小为0
}

🌠销毁队列函数

首先断言队列指针是否为空，cur从头节点开始遍历队列，保存cur下一个节点的指针，释放cur节点内存，cur移到下一个节点，遍历完整个队列后,将头尾节点指针和大小都重置为初始状态

void QueueDestroy(Queue* pq) 
{

  assert(pq); // 断言队列指针是否为空
  QNode* cur = pq->phead; // cur指向队列头节点
  while (cur) 
  {  
    QNode* next = pq->phead->next; // 保存cur下一个节点的指针
    free(cur); // 释放cur节点内存
    cur = next; // cur指针移到下一个节点
  }
  pq->phead = pq->ptail = NULL; // 重置头尾节点指针为空
  pq->size = 0; // 重置队列大小为0

}

🌉入队函数

将新的数据 x 入队，要分配一个新的节点 newnode，将数据 x 存储在节点中。根据队列是否为空，将新节点连接到队列的尾部，并更新尾指针。如果队列为空，则同时更新头指针。
增加队列的大小。

void QueuePush(Queue* pq, QDataType* x) 
{
  assert(pq); // 断言队列指针是否为空
  QNode* newnode = (QNode*)malloc(sizeof(QNode)); // 申请新节点内存
  if (newnode == NULL) 
  { // 申请失败
    perror("malloc fail"); 
    return;
  }
  newnode->data = x; // 设置新节点数据
  newnode->next = NULL; // 设置新节点next指针为空

  if (pq->ptail)
  { // 如果队列不为空
    pq->ptail->next = newnode; // 尾节点指向新节点
    pq->ptail = newnode; // 更新尾节点指针
  } 
  else 
  { // 队列为空
    pq->phead = pq->ptail = newnode; // 头尾节点同时指向新节点
  }

  pq->size++; // 队列大小增加1

}

🌠出队函数

出队，即删除队列中的队首元素。首先检查队列是否为空，如果为空则直接返回。如果队列只有一个节点，则直接释放这个节点，同时将头尾指针置为空。如果队列有多个节点，则释放队首节点，并将头指针指向下一个节点。减小队列的大小。

void QueuePop(Queue* pq) 
{

  assert(pq); // 断言队列指针是否为空
  if (pq->phead == NULL) 
  			return; // 队列为空直接返回
  			
  assert(pq->phead != NULL); // 断言头节点不为空
  if (pq->phead->next == NULL)
   { // 队列只有一个节点
    free(pq->phead); // 释放头节点
    pq->phead = pq->ptail = NULL; // 头尾节点同时置空
  } 
  else 
  { // 队列有多个节点
    QNode* next = pq->phead->next; // 保存头节点的下一个节点
    free(pq->phead); // 释放头节点
    pq->phead = next; // 头节点指向下一个节点
  }

  pq->size--; // 队列大小减1

}

🌉获取队首元素函数

获取队列的队首元素，得首先确保队列不为空，然后返回队首节点中存储的数据。

QDataType QueueFront(Queue* pq)
 {
    assert(pq);
    assert(pq->phead != NULL);
    return pq->phead->data;
}

🌠获取队尾元素函数

获取队列的队尾元素，得首先确保队列不为空，然后返回队尾节点中存储的数据。

QDataType QueueBack(Queue* pq)
 {
    assert(pq);
    assert(pq->ptail != NULL);
    return pq->ptail->data;
}

🌉 判断队列是否为空函数

判断队列是否为空，通过检查队列的大小是否为0来确定队列是否为空。

bool QueueEmpty(Queue* pq) 
{
    assert(pq);
    return pq->size == 0;
}

🌉获取队列大小函数

获取队列的大小，即队列中元素的数量。

int QueueSize(Queue* pq) 
{
    assert(pq);
    return pq->size;
}

🌠测试

# define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "Queue.h" 

int main() 
{
    Queue queue;
    QueueInit(&queue);

    printf("Queue is empty: %s\n", QueueEmpty(&queue) ? "true" : "false");

    printf("Pushing elements into the queue...\n");
    for (int i = 1; i <= 5; ++i) 
    {
        printf("Pushing %d\n", i);
        QueuePush(&queue, i);
    }

    printf("Queue size: %d\n", QueueSize(&queue));
    printf("Queue front: %d\n", QueueFront(&queue));
    printf("Queue back: %d\n", QueueBack(&queue));

    printf("Popping elements from the queue...\n");
    while (!QueueEmpty(&queue)) 
    {
        printf("Front: %d\n", QueueFront(&queue));
        QueuePop(&queue);
    }

    printf("Queue is empty: %s\n", QueueEmpty(&queue) ? "true" : "false");

    QueueDestroy(&queue);

    return 0;
}

代码效果图：

🌉 总源代码

Queue.c

#include "Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq); // 断言队列指针是否为空
	pq->phead = NULL; // 初始化头节点指针为空
	pq->ptail = NULL; // 初始化尾节点指针为空  
	pq->size = 0; // 初始化队列大小为0
}

void QueueDestroy(Queue* pq)
{

	assert(pq); // 断言队列指针是否为空
	QNode* cur = pq->phead; // cur指向队列头节点
	while (cur)
	{
		QNode* next = pq->phead->next; // 保存cur下一个节点的指针
		free(cur); // 释放cur节点内存
		cur = next; // cur指针移到下一个节点
	}
	pq->phead = pq->ptail = NULL; // 重置头尾节点指针为空
	pq->size = 0; // 重置队列大小为0

}



void QueuePush(Queue* pq, QDataType* x)
{
	assert(pq); // 断言队列指针是否为空
	QNode* newnode = (QNode*)malloc(sizeof(QNode)); // 申请新节点内存
	if (newnode == NULL)
	{ // 申请失败
		perror("malloc fail");
		return;
	}
	newnode->data = x; // 设置新节点数据
	newnode->next = NULL; // 设置新节点next指针为空

	if (pq->ptail)
	{ // 如果队列不为空
		pq->ptail->next = newnode; // 尾节点指向新节点
		pq->ptail = newnode; // 更新尾节点指针
	}
	else
	{ // 队列为空
		pq->phead = pq->ptail = newnode; // 头尾节点同时指向新节点
	}

	pq->size++; // 队列大小增加1

}

//出队列
void QueuePop(Queue* pq)
{

	assert(pq); // 断言队列指针是否为空
	if (pq->phead == NULL)
		return; // 队列为空直接返回

	assert(pq->phead != NULL); // 断言头节点不为空
	if (pq->phead->next == NULL)
	{ // 队列只有一个节点
		free(pq->phead); // 释放头节点
		pq->phead = pq->ptail = NULL; // 头尾节点同时置空
	}
	else
	{ // 队列有多个节点
		QNode* next = pq->phead->next; // 保存头节点的下一个节点
		free(pq->phead); // 释放头节点
		pq->phead = next; // 头节点指向下一个节点
	}

	pq->size--; // 队列大小减1

}

QDataType QueueFront(Queue* pq)
{
	assert(pq);

	assert(pq->phead != NULL);

	return pq->phead->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);

	//暴力检查
	assert(pq->ptail != NULL);

	return pq->ptail->data;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	
	return pq->size == 0;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

🚩总结