[数据结构与算法]数据结构--不设头指针的循环链队列

本次数据结构的作业是设计一个只有尾指针的循环链队列，要求实现构造(有参 && 无参)、析构、出入列、获取头结点等功能。在完成过程中踩了很多坑(特别是在实现析构时qwq)

template <class DataType>
struct Node {
    DataType data;
    Node<DataType>* next;
};

template <class DataType>
class LinkQueue {
    public:
     LinkQueue();
     LinkQueue(int [], int);
     ~LinkQueue();
     void EnQueue(DataType x);
     DataType DeQueue();
     DataType GetQueue();
    
    private:
     Node<DataType>* rear;
};

有参构造&&无参构造

template <class DataType>
LinkQueue<DataType>::LinkQueue(int arr[], int n) {
    rear = new Node<DataType>;
    Node<DataType>* p = rear;
    //储存首地址，最后把尾巴连上
	for(int i = 0; i < n; i++) {
        rear->next = new Node<DataType>;
        rear = rear->next;
        rear->data = arr[i];
    }
    rear->next = p;
    // 把尾巴连到首部
}

template <class DataType>
LinkQueue<DataTpye>::LinkQueue() {
    rear = NULL;
}

进队 && 出队

template <class DataType>
void LinkQueue<DataType>::EnQueue(DataType x) {
    Node<DataType>* p = new Node<DataType>;    
    p->data = x;
    if (rear == NULL) {
        rear = p;
        rear->next = p;
    } else {
        p->next = rear->next;  // 新建节点连接头指针
        rear->next = p; // 尾指针连接新节点
        rear = p; // 尾指针后移
    }
}

template <class DataType>
DataType LinkQueue<DataType>::DeQueue() {
    Node<DataType>* p = NULL;
    DataType x;
    if (rear == NULL) 
        throw "dive dowm";
    p = rear->next;
    x = p->data;
    if (rear == p)
        rear = NULL;
    else 
        rear->next = p->next;
    delete p;
    return x;
}

获取头结点

template <class DataType>
DataType LinkQueue<DataType>::GetQueue() {
    if (rear != NULL)
        return rear->next->data;
    	// return rear->data;
	    // 这里rear已经指向队末，按照上一行代码，返回的是队末元素
    else
        throw "empty queue";
}

清空循环链队列(也可写成析构)

template <class DataType>
LinkQueue<DataType>::~LinkQueue() {
    Node<DataType>* p;
    while (rear != NULL) {
        // the wrong version:
        
        // p = rear;
        // rear = rear->next;
        // delete p;

        p = rear->next;
        if (rear == p) {
            delete rear;
            break;
        } else 
            rear->next = p->next;
        delete p;
    }
}

关于这个析构函数，我在网上找了很多个版本，很多代码都是写成注释里的那样，包括老师给的答案也是，有些编译器直接运行可能看不出什么问题，但是放在debug模式里，就会报错

如上图，在这里我已将循环链队列所有元素delete，当我查看变量的值时，发现，没那么简单，rear指针不为null，它指向的data值也是不规则的，也就不难说明为什么跳不出第46行的while循环了

跳不出循环后，继续delete，就会报错，虽然提示unKnown signal，实际上是队列为空，无法继续delete

那么怎么解决呢，我将出列函数改写，放到析构函数里，这样子在删除最后一个节点时就能跳出循环，结束析构

完整代码

#include <bits/stdc++.h>
using namespace std;

template <class DataType>
struct Node {
    DataType data;
    Node<DataType>* next;
};

template <class DataType>
class LinkQueue {
   public:
    LinkQueue();
    LinkQueue(int[], int);
    ~LinkQueue();
    void EnQueue(DataType x);
    DataType DeQueue();
    DataType GetQueue();

   private:
    Node<DataType>* rear;
};

template <class DataType>
LinkQueue<DataType>::LinkQueue(int arr[], int n) {
    rear = new Node<DataType>;
    // rear->data = arr[0];
    Node<DataType>* p = rear;  // 储存首地址，最后把尾巴连接到首部
    for (int i = 0; i < n; i++) {
        rear->next = new Node<DataType>;  // 不断开辟空间
        rear = rear->next;                // rear后移
        rear->data = arr[i];
    }
    rear->next = p;  //把尾巴连到首部
}

template <class DataType>
LinkQueue<DataType>::LinkQueue() {
    rear = NULL;
}

template <class DataType>
LinkQueue<DataType>::~LinkQueue() {
    Node<DataType>* p;
    while (rear != NULL) {        
        p = rear->next;
        if (rear == p) {
            delete rear;
            break;
        } else {
            rear->next = p->next;
        }
        delete p;
    }
}

template <class DataType>
void LinkQueue<DataType>::EnQueue(DataType x) {
    Node<DataType>* p = NULL;
    p = new Node<DataType>;
    p->data = x;
    if (rear == NULL) {
        rear = p;
        rear->next = p;
    } else {
        p->next = rear->next;  // 新建节点连接头指针
        rear->next = p;        // 尾指针连接新节点
        rear = p;              // 尾指针后移
    }
}

template <class DataType>
DataType LinkQueue<DataType>::DeQueue() {
    Node<DataType>* p = NULL;
    DataType x;
    if (rear == NULL)
        throw "dive down";
    p = rear->next;
    x = p->data;
    if (rear == p)
        rear = NULL;
    else
        rear->next = p->next;
    delete p;
    return x;
}

template <class DataType>
DataType LinkQueue<DataType>::GetQueue() {
    if (rear != NULL)
        return rear->next->data;
    // return rear->data;
    // 这里rear已指向队末，返回的是队末元素
    else
        throw "empty queue";
}

int main() {
    LinkQueue<int> Queue;
    try {
        Queue.EnQueue(5);
        Queue.EnQueue(10);
        Queue.EnQueue(15);
        // Queue.EnQueue(20);
    } catch (char* wrong) {
        cout << wrong << endl;
    }
    cout << "get head element" << endl;
    cout << Queue.GetQueue() << endl;
    try {
        Queue.DeQueue();
    } catch (char* wrong) {
        cout << wrong << endl;
    }
    cout << "get head element" << endl;
    cout << Queue.GetQueue() << endl;
}