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

队列：链表实现

结构描述:

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

初始化：（创建空队）

把 Front 和 Rear 指向空。

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 同时赋值给 Front 与 Rear
• 若队非空，则把 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;
    }
}

获取队头、队尾元素

直接返回 Front 和 Rear 的数据域即可，若表为空，则不可获取。

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