首页 > 其他分享 >【数据结构】队列:链表实现

【数据结构】队列:链表实现

时间:2024-07-18 14:45:37浏览次数:15  
标签:Node 队列 QueueLinked 链表 DataType Front NewNode 数据结构 Rear

队列:链表实现

结构描述:

typedef int DataType;
typedef struct QueueNode {
    DataType A;
    struct QueueNode * Next;
}Node;
class QueueLinked {
public:
    //队头、队尾指针
    Node * Front;
    Node * Next;

    //队列操作
    //把元素X入队
    void Push(DataType X);
    //把队头元素出队
    void Pop();
    //销毁队列
    void MakeEmpty();
    //判断队列是否为空,为空返回true
    bool IsEmpty();
    //初始化(创建空队)
    void Init();
    //获取队头,队尾元素
    DataType GetFront();
    DataType GetRear();
    //创建节点
    Node * BuyNode(DataType X);
};

初始化:(创建空队)

FrontRear 指向空。

void QueueLinked::Init() {
    Front = Rear = nullptr;
}

判空

Front 指向空时,即队列为空

bool QueueLinked::IsEmpty() {
    return Front == nullptr;
}

创建节点

把数据 X 传到 BuyNode() 方法中,用 malloc() 函数动态分配一个节点:

  • 分配成功:返回节点指针;
  • 分配失败:报错退出;
Node * QueueLinked::BuyNode(DataType X) {
    Node * NewNode = (Node *)malloc(sizeof(Node));
    // Node * NewNode = (Node *)malloc(sizeof(DataType));

    if (NewNode == nullptr) {
        cout << "Malloc Failed!" << endl;
        exit(-1);
    }
    else {
        NewNode->A = X;
        NewNode->Next = nullptr;
    }

    return NewNode;
}

入队:

  • 若队为空,则创建新节点 NewNode,把 NewNode 同时赋值给 FrontRear
  • 若队非空,则把 NewNode 接在 Rear 指针之后,即 Rear->Next = NewNode
void QueueLinked::Push(DataType X) {
    if (IsEmpty()) {
        Node * NewNode = BuyNode(X);
        Front = Rear = NewNode;
    }
    else {
        Node * NewNode = BuyNode(X);
        Rear->Next = NewNode;
        Rear = Rear->Next;
    }
}

出队

  • 若队为空:报错
  • 若队非空:操作 Front 指针,进行出队操作
    • 用临时变量 Tmp 保存当前 Front 指针所指向的位置;
    • Front 指针向后移动一位 Front = Front->Next
    • 释放 Tmp ,并将其置空
void QueueLinked::Pop() {
    if (IsEmpty()) {
        cout << "Queue Is Empty!" << endl;
        exit(-1);
    }
    else {
        Node * Tmp = Front;
        Front = Front->Next;
        free(Tmp);
        Tmp = nullptr;
    }
}

获取队头、队尾元素

直接返回 FrontRear 的数据域即可,若表为空,则不可获取。

DataType QueueLinked::GetFront() {
    if (IsEmpty()) {
        cout << "Queue Is Empty!" << endl;
        exit(-1);
    }
    return Front->A;
}
DataType QueueLinked::GetRear() {
       if (IsEmpty()) {
        cout << "Queue Is Empty!" << endl;
        exit(-1);
    }
    return Rear->A;
}

摧毁队列

只要队列不为空,即 IsEmpty() 为假时,就一直出队,直到队空为止。

void QueueLinked::MakeEmpty() {
    while (!IsEmpty()) {
        Pop();
    }
}

踩坑记录

报错:

warning: HEAP[a.exe]: 
warning: Heap block at 0000000000A93BA0 modified at 0000000000A93BB8 past requested size of 4

Thread 1 received signal SIGTRAP, Trace/breakpoint trap.
0x00007ffe6fb8a503 in ntdll!RtlRegisterSecureMemoryCacheCallback () from C:\Windows\SYSTEM32\ntdll.dll

原因:

在动态内存分配时,都将 DataType 类型大小分配给了 Node 类型的指针,导致的错误。

Node * NewNode = (Node *)malloc(sizeof(DataType));

修正

Node * NewNode = (Node *)malloc(sizeof(Node));

标签:Node,队列,QueueLinked,链表,DataType,Front,NewNode,数据结构,Rear
From: https://www.cnblogs.com/codels/p/18309459

相关文章

  • 【数据结构】循环队列:链表实现
    循环队列:链表实现结构描述typedefintDataType;typedefstructQueueNode{DataTypeA;structQueueNode*Next;}Node;classQueueCycLinked{public://队头、队尾指针Node*Front;Node*Next;//队列操作//把元素X入队voidPu......
  • 单链表
    单链表结构描述#include<iostream>#include<cstdlib>usingnamespacestd;typedefintDataType;//链表节点typedefstructNode{DataTypeA;structNode*Next;}Node;classSingleLinkedList{private:Node*Head;public://尾插......
  • 栈:链表实现
    栈:链表实现结构描述#include<iostream>#include<cstdlib>typedefintDataType;usingnamespacestd;typedefstructNode{DataTypeA;structNode*Next;}Node;classStackLinked{private:Node*Top;public:voidPush(DataTy......
  • 【数据结构】树和二叉树——Lesson1
    Hi~!这里是奋斗的小羊,很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎~~......
  • RabbitMQ——死信队列介绍和应用
    死信和死信队列的概念什么是死信?简单来说就是无法被消费和处理的消息。一般生产者将消息投递到broker或者queue,消费者直接从中取出消息进行消费。但有时因为某些原因导致消息不能被消费,导致消息积压在队列中,这样的消息如果没有后续的处理就会变成死信,那么专门存放死信的队列就是......
  • 一个故事理解消息队列-上
    前段时间,知识星球里一位同学给我分享了他对消息队列的理解,并且用一个故事形象的表述了消息队列的作用。看完他的表述,我觉得用故事来描述技术组件作用的方式很有意思,也更容易让人理解。这篇文章,借用他的故事,为大家简单介绍一下消息队列。 消息队列的故事假设现在有一本技术......
  • 旋转链表-灵活运用取模
    题目描述:个人题解:        记给定链表的长度为n,注意到当向右移动的次数k≥n时,我们仅需要向右移动k%n次即可。因为每n次移动都会让链表变为原状。这样我们可以知道,新链表的最后一个节点为原链表的第(n−1)−(k%n)个节点(从0开始计数)。这样,我们可以先将给定......
  • 用数组模拟环形队列——2
    在上一篇的文章中我们介绍了队列的使用,但是普通的队列存在资源浪费的问题,为了解决这个问题,又提出了环形队列,今天,我们就详细介绍一下环形队列的使用方法。环形队列的特点:1.队列的存储结构是一个环形结构,即队列的头尾相连,形成一个环形。2.队列有固定的大小,通常用数组来实现。......
  • 数据结构之细说链表
    1.1顺序表的问题以及思考经过上一篇顺序表的学习,我们知道顺序表还是有很多缺点顺序表的缺点:1.中间/头部的插入删除,实际复杂度为O(N)2.增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗3.扩容一般是呈两倍增长,势必会有一定的空间浪费。例如当前空间的容量是100,满了......
  • 数据结构——双链表与静态链表
    一、双链表1、定义 双链表:上一篇提到单链表,其实有一个弊端,就是只能单向读取,很笨重并且只能从头指针开始读取,而双链表是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点......