数据结构——链式队列

数据结构——链式队列

目录

一、概念

1.1 结构组成

二、基本操作

2.1 结构体定义

2.2 初始化

2.3 入队

2.4 出队

2.5 获取队头元素值

2.6 查找

2.7 判空

2.8 获取有效值个数

2.9 清空

2.10 销毁

2.11 打印

2.12 主函数测试 

三 总代码 

.cpp代码

.h代码

---

一、概念

链式队列，通常也被称为链表队列或者简单链表，是一种使用链表实现的队列数据结构。队列是一种先进先出（FIFO）的数据结构，即最先添加到队列中的元素将是最先被移除的元素。链式队列通过链接一系列节点来实现队列的功能，每个节点包含数据部分和指向下一个节点的指针。

1.1 结构组成

链式队列通常由两个主要部分组成：

1. 节点（Node）：链式队列中的每个元素都是一个节点，包含两个主要部分：

   • 数据域（Data Field）：用于存储队列中的实际数据。

   • 指针域（Pointer Field）：通常是一个指针，指向链表中的下一个节点。

2. 头尾指针：链式队列使用两个指针来分别指向队列的头部（front）和尾部（rear）：

   • 头指针（Front）：指向队列中的第一个节点，即最先进入队列的元素。

   • 尾指针（Rear）：指向队列中的最后一个节点，即最后进入队列的元素。

二、基本操作

2.1 结构体定义

typedef int ELEM_TYPE;//链式队列有效结点结构体设计
typedef struct LQ_Node
{ELEM_TYPE data;//数据域struct LQ_Node* next;//指针域
}LQ_Node;//链式队列的辅助结点结构体设计
typedef struct
{struct LQ_Node* front;//对头指针LQ_Node* rear;//队尾指针
}List_Queue;

2.2 初始化

void Init_List_Queue(List_Queue* plq)
{assert(plq != NULL);plq->front = plq->rear = NULL;
}

2.3 入队

bool Push(List_Queue* plq, ELEM_TYPE val)
{//0.assertassert(plq != NULL);//1.购买新节点struct LQ_Node* pnewnode = (LQ_Node*)malloc(sizeof(LQ_Node));if (pnewnode == NULL){return false;}pnewnode->data = val;//2.分情况，看链式队列空不空//3.1.空，则修改对应3个指针if (IsEmpty(plq)){pnewnode->next = NULL;//3plq->front = plq->rear = pnewnode;//12return true;}//3.2.不空，则修改对应3个指针else{pnewnode->next = plq->rear->next;//3plq->rear->next = pnewnode;//1plq->rear = pnewnode;return true;}
}

2.4 出队

bool Pop(List_Queue* plq)
{//0.assert assert(plq != NULL);//1.确保有节点if (IsEmpty(plq))return false;//2.分情况处理(看此时的有效元素个数是=1还是大于1)//2.1 若当前仅有唯一一个有效元素struct LQ_Node* q = plq->front;if (q->next == NULL){plq->front = plq->rear = NULL;free(q);q = NULL;return true;}//2.2 若当前有多个有效元素else{plq->front = q->next;free(q);q = NULL;return true;}
}

首先获取队头指针plq->front并赋值给q。当q->next为NULL时，说明队列中只有一个元素。此时将队列的头指针plq->front和尾指针plq->rear都设为NULL，然后释放该节点的内存，并将q设为NULL，最后返回true表示出队操作成功。

当队列中有多个元素时，将队列的头指针plq->front更新为原队头节点的下一个节点（即q->next），然后释放原队头节点的内存，并将q设为NULL，返回true表示出队操作成功。 

2.5 获取队头元素值

ELEM_TYPE Front(List_Queue* plq)
{//0.assert(plq != NULL);//1.if (IsEmpty(plq)){exit(1);}return plq->front->data;
}

2.6 查找

LQ_Node* Search(List_Queue* plq, ELEM_TYPE val)
{//0.assert(plq != NULL);LQ_Node* p = plq->front;for (; p != NULL; p = p->next){if (p->data == val)return p;}return NULL;
}

2.7 判空

bool IsEmpty(List_Queue* plq)
{return plq->front == NULL;//return plq->rear == NULL;}

2.8 获取有效值个数

int Get_Size(List_Queue* plq)
{assert(plq != NULL);int count = 0;LQ_Node* p = plq->front;for (; p != NULL; p = p->next){count++;}return count;
}

2.9 清空

void Clear(List_Queue* plq)
{Destroy(plq);
}

2.10 销毁

void Destroy(List_Queue* plq)
{//assertLQ_Node* p = plq->front;LQ_Node* q = NULL;while (p != NULL){q = p->next;free(p);p = q;}plq->front = plq->rear = NULL;
}

2.11 打印

void Show(List_Queue* plq)
{assert(plq != NULL);LQ_Node* p = plq->front;for (; p != NULL; p = p->next){printf("%d ", p->data);}printf("\n");
}

2.12 主函数测试 

int main()
{srand((unsigned int)time(NULL));int tmp = rand() % 30;printf("%d\n", tmp);List_Queue head;Init_List_Queue(&head);Push(&head, 1);Push(&head, 2);Push(&head, 3);printf("Front = %d\n", Front(&head));Show(&head);Pop(&head);printf("Front = %d\n", Front(&head));Show(&head);Destroy(&head);Show(&head);return 0;
}

三 总代码 

.cpp代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
#include "list_queue.h"//可实现的函数操作：
//1.初始化
void Init_List_Queue(List_Queue* plq)
{assert(plq != NULL);plq->front = plq->rear = NULL;
}//2.入队
bool Push(List_Queue* plq, ELEM_TYPE val)
{//0.assertassert(plq != NULL);//1.购买新节点struct LQ_Node* pnewnode = (LQ_Node*)malloc(sizeof(LQ_Node));if (pnewnode == NULL){return false;}pnewnode->data = val;//2.分情况，看链式队列空不空//3.1.空，则修改对应3个指针if (IsEmpty(plq)){pnewnode->next = NULL;//3plq->front = plq->rear = pnewnode;//12return true;}//3.2.不空，则修改对应3个指针else{pnewnode->next = plq->rear->next;//3plq->rear->next = pnewnode;//1plq->rear = pnewnode;return true;}
}//3.出队
bool Pop(List_Queue* plq)
{//0.assert assert(plq != NULL);//1.确保有节点if (IsEmpty(plq))return false;//2.分情况处理(看此时的有效元素个数是=1还是大于1)//2.1 若当前仅有唯一一个有效元素struct LQ_Node* q = plq->front;//if (plq->rear == plq->front)if (q->next == NULL){plq->front = plq->rear = NULL;free(q);q = NULL;return true;}//2.2 若当前有多个有效元素else{plq->front = q->next;free(q);q = NULL;return true;}
}//4.获取队头元素值
ELEM_TYPE Front(List_Queue* plq)
{//0.assert(plq != NULL);//1.if (IsEmpty(plq)){exit(1);}return plq->front->data;
}//4.5查找
LQ_Node* Search(List_Queue* plq, ELEM_TYPE val)
{//0.assert(plq != NULL);LQ_Node* p = plq->front;for (; p != NULL; p = p->next){if (p->data == val)return p;}return NULL;
}//5.判空
bool IsEmpty(List_Queue* plq)
{return plq->front == NULL;//return plq->rear == NULL;}//7.获取有效值个数 Size
int Get_Size(List_Queue* plq)
{assert(plq != NULL);int count = 0;LQ_Node* p = plq->front;for (; p != NULL; p = p->next){count++;}return count;
}//8.清空
void Clear(List_Queue* plq)
{Destroy(plq);
}//9.销毁
void Destroy(List_Queue* plq)
{//assertLQ_Node* p = plq->front;LQ_Node* q = NULL;while (p != NULL){q = p->next;free(p);p = q;}plq->front = plq->rear = NULL;
}//10.打印
void Show(List_Queue* plq)
{assert(plq != NULL);LQ_Node* p = plq->front;for (; p != NULL; p = p->next){printf("%d ", p->data);}printf("\n");
}int main()
{srand((unsigned int)time(NULL));int tmp = rand() % 30;printf("%d\n", tmp);List_Queue head;Init_List_Queue(&head);Push(&head, 1);Push(&head, 2);Push(&head, 3);printf("Front = %d\n", Front(&head));Show(&head);Pop(&head);printf("Front = %d\n", Front(&head));Show(&head);Destroy(&head);Show(&head);return 0;
}

.h代码

#pragma once
typedef int ELEM_TYPE;//链式队列有效结点结构体设计
typedef struct LQ_Node
{ELEM_TYPE data;//数据域struct LQ_Node* next;//指针域
}LQ_Node;//链式队列的辅助结点结构体设计
typedef struct
{struct LQ_Node* front;//对头指针LQ_Node* rear;//队尾指针
}List_Queue;//可实现的函数
//1.初始化
void Init_List_Queue(List_Queue* plq);//2.入队
bool Push(List_Queue* plq, ELEM_TYPE val);//3.出队
bool Pop(List_Queue* plq);//4.获取队头元素值
ELEM_TYPE Front(List_Queue* plq);//4.5查找
LQ_Node* Search(List_Queue* plq, ELEM_TYPE val);//5.判空
bool IsEmpty(List_Queue* plq);//7.获取有效值个数 Size
int Get_Size(List_Queue* plq);//8.清空
void Clear(List_Queue* plq);//9.销毁
void Destroy(List_Queue* plq);//10.打印
void Show(List_Queue* plq);