C++数据结构——链队列

主页有其他数据结构内容（持续更新中）

#include
using namespace std;


template 
struct Node
{
    T data;        //数据域
    Node* next;      //指针域

    Node()
    {
        next = nullptr;
    }

    Node(T item, Node* ptr = nullptr)
    {
        data = item;
        next = ptr;
    }
};


template 
class LinkQueue
{
public:
    LinkQueue();                        //构造和析构
    ~LinkQueue();
    LinkQueue(const LinkQueue& item);  //拷贝构造函数
    LinkQueue& operator=(const LinkQueue& item);  //重载赋值运算符
    void push(const T& item);    //入队操作
    void pop();                     //出队操作
    bool empty()const;                     //判断队列是否为空
    T top();  //返回队列头部元素
    int size()const;    //  返回队列长度

private:
    Node* front;        //队头指针
    Node* rear;         //队尾指针
    int count;
};


template
LinkQueue::LinkQueue()  //构造函数
{
    rear = front = nullptr;
    this->count = 0;
}


template
LinkQueue::~LinkQueue()  //析构函数
{
    while (!empty())
    {
        pop();
    }
}


//入队操作
template
void LinkQueue::push(const T& item)
{
    Node* temp = new Node(item);   //手动开辟空间
    if (temp == nullptr)
    {
        cout << "Overflow!" << endl;
        return;
    }
    if (rear == nullptr)
    {
        front = rear = temp;
    }
    else
    {
        rear->next = temp;
        rear = temp;
    }
    this->count++;
}


//出队操作
template
void LinkQueue::pop()
{
    if (empty())
    {
        cout << "Underflow!" << endl;
        return;
    }
    Node* ptr = front;
    front = front->next;
    ptr = nullptr;
    delete ptr;
    if (this->count == 1){  //  这是最后一个结点出队
        rear = nullptr;
    }
    this->count--;
}


//判断队列是否为空
template
bool LinkQueue::empty()const
{
    return count == 0;
}


template
T LinkQueue::top() {
    if (empty()) {
        cout << "Underflow!" << endl;
    }
    else {
        return front->data;
    }
}


template
LinkQueue::LinkQueue(const LinkQueue& item)  //拷贝构造函数
{
    Node* original_front = item.front;
    Node* original_rear = item.rear;
    Node* new_copy;
    if (original_front == nullptr && original_rear == nullptr)
    {
        front = rear = nullptr;
    }
    else
    {
        front = new_copy = new Node(original_front->data);
        rear = new Node(original_rear->data);
        while (original_front->next != nullptr)
        {
            original_front = original_front->next;
            new_copy->next = new Node(original_front->data);
            new_copy = new_copy->next;
        }
    }
    this->count = item.count;
}


template
LinkQueue& LinkQueue::operator=(const LinkQueue& item)  //重载赋值运算符
{
    Node* original_front = item.front;
    Node* original_rear = item.rear;
    Node* new_copy;
    if (original_front == nullptr && original_rear == nullptr)
    {
        front = rear = nullptr;
    }
    else
    {
        front = new_copy = new Node(original_front->data);
        rear = new Node(original_rear->data);
        while (original_front->next != nullptr)
        {
            original_front = original_front->next;
            new_copy->next = new Node(original_front->data);
            new_copy = new_copy->next;
        }
    }
    this->count = item.count;
    return *this;
}

template
int LinkQueue::size() const {
    return this->count;
}


int main(){
    LinkQueue lq;
    for (int i = 0; i < 10; ++i) {
        lq.push(i);
    }
    cout << "队列的长度为：" << lq.size() << endl;

    LinkQueue copy_1 = lq;
    while (!copy_1.empty()){
        cout << copy_1.top() << "t";
        copy_1.pop();
    }
    cout << endl;

    LinkQueue copy_2 = lq;
    while (!copy_2.empty()){
        cout << copy_2.top() << "t";
        copy_2.pop();
    }


    return 0;
}