我的队列数据结构实现错误

Question

我正在尝试使用链表实现队列，但是当我将整数传递给 main

中的 enqueue 函数时出现此错误

Exception thrown: write access violation.

this->tail was nullptr.

这是我的 Queue.h

 #include <iostream>
using namespace std;

template <class T >
class Node
{
public:
    T data;
    Node* next;
    Node();
    Node(T _data);
};

template <class T>
class Queue
{

public:
    Node<T> *head, *tail;
    int elemsCnt;
    Queue();
    ~Queue();
    int count();
    void clear();
    void enqueue(T);
    T dequeue();
    T front();
    T back();
    bool empty();
};

这是我的Queue.cpp，我写了函数.. #include "Queue.h"

template <class T>
Node<T>::Node()
{
    next = NULL;
}

template <class T>
Node<T>::Node(T _data)
{
    data = _data;
    next = NULL;
}

template <class T>
Queue<T>::Queue()
{
    head = tail = NULL;
    elemsCnt = 0;
}

template <class T>
Queue<T>::~Queue()
{
    clear();
}

template <class T>
int Queue<T>::count()
{
    return elemsCnt;
}

template <class T>
bool Queue<T>::empty()
{
    return(elemsCnt == 0);
}

template <class T>
void Queue<T>::enqueue(T val)
{
    Node<T>* inserted = new Node<T>(val);
    tail->next = inserted;
    tail = inserted;
    ++elemsCnt;
}

template <class T>
T Queue<T>::dequeue()
{
    Node<T>* deleted = head;
    T val = head->data;
    head = head->next;
    delete deleted;
    --elemsCnt;

    if (empty())
        tail = NULL;

    return val;
}

template <class T>
T Queue<T>::front()
{
    return head->data;
}

template <class T>
T Queue<T>::back()
{
    return tail->data;
}

template <class T>
void Queue<T>::clear()
{
    while (!empty())
    {
        Node<T>* deleted = head;
        head = head->next;
        delete deleted;
        --elemsCnt;
    }
    tail = NULL;
}

Answer 1

因为最初您的队列是空的。当你有：

void Queue<T>::enqueue(T val)
{
    Node<T>* inserted = new Node<T>(val);
    tail->next = inserted; //at this point tail is still NULL
    //it is illegal to try to access * and . on NULL

    tail = inserted;
    ++elemsCnt;
}

如果你想修复它试试这个：

void Queue<T>::enqueue(T val)
{
    Node<T>* inserted = new Node<T>(val);

    if(this->elemsCnt==0)
    {
        //empty Queue
        this->head=inserted;
        this->tail=inserted;
    }
    else
    {
        //non empty
        inserted->next=this->head; //make sure the new head can point to older head
        this->head=inserted; update the pointer for head.

    }
    ++elemsCnt;
}

Answer 2

正如异常所说，tail 为 NULL。您的入队方法不处理列表为空的情况（head == tail == null）。

template <class T>
void Queue<T>::enqueue(T val)
{
    Node<T>* inserted = new Node<T>(val);
    if (head == NULL)
    {
        head = tail = inserted;
    }
    else
    {
        tail->next = inserted;
        tail = inserted;
    }
    ++elemsCnt;
}

我的队列数据结构实现错误

Error in My Queue datastructres implementation

c++

queue

data-structures