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

数据结构——链式队列

article 2025/3/26 2:55:12

数据结构——链式队列

目录

一、概念

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.assert
    assert(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;//3
        plq->front = plq->rear = pnewnode;//12
        return true;
    }
    //3.2.不空，则修改对应3个指针
    else
    {
        pnewnode->next = plq->rear->next;//3
        plq->rear->next = pnewnode;//1
        plq->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)
{
    //assert

    LQ_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.assert
    assert(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;//3
        plq->front = plq->rear = pnewnode;//12
        return true;
    }
    //3.2.不空，则修改对应3个指针
    else
    {
        pnewnode->next = plq->rear->next;//3
        plq->rear->next = pnewnode;//1
        plq->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)
{
    //assert

    LQ_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);


http://www.kler.cn/a/600386.html

相关文章：

  • Spring Security核心源码和功能实现
  • M芯片mac安装Linux虚拟机
  • HTML和CSS基础
  • 数据结构初阶-二叉树的应用
  • 1688关键字API接口解析：（实战案例）
  • Day110 若依-基础
  • mysql数据实时全量+增量迁移
  • 【论文笔记】生成对抗网络 GAN
  • 统一开放世界与开放词汇检测：YOLO-UniOW无需增量学习的高效通用开放世界目标检测框架
  • 开源视觉语言模型MiniMax-VL-01：动态分辨率+4M超长文本，性能比肩GPT-4o
  • 基础算法01——二分查找（Binary Search）
  • 蓝桥云客 数字接龙
  • Flink 流处理框架的核心特性
  • Linux第零节：Linux命令速查图表（按功能分类）
  • 使用BootStrap 3的原创的模态框组件，没法弹出！估计是原创的bug
  • C# 线程介绍
  • 调用百度api实现语音识别（python）
  • python如何获取html中附件链接，并下载保存附件
  • 珍珠港海军造船厂的“水魔法”：PcVue赋能造船心脏
  • 特征工程自动化（FeatureTools实战）