How to implement a Queue using Linked List in C++ by classes only

0

I have a Linked List class, implemented like this (and tested too):

template <class T>
class LList {
    LNode<T>* head;
    LNode<T>* tail;
    int size; // proporciona muitas vantagens
    LNode<T>* rCopy(LNode<T>* right);
public:
    LList() : head(nullptr), tail(nullptr), size(0) {}
    LList(const LList& other) :
            head(nullptr), tail(nullptr), size(0) {
        *this = other;
    }
    ~LList() { clear(); }

...
    // O(1)
    void insertAtBack(T newvalue) {
        LNode<T>* tmp = new LNode<T>(newvalue, nullptr);
        tail->next = tmp;
        tail = tmp;
        if (head == nullptr)
            head = tmp;
        this->size++;
    }
...
};

Then, I created a Queue class:

template <class T>
class Queue {
private:
    LList<T> lista;
public:
//    Queue() : lista() {} ??? don't know how to do it
    void enqueue(T element);
    T peek();
    void dequeue();
    int size();
    bool isEmpty();
    void sizeLog();
};

template<class T>
void Queue<T>::enqueue(T element) {
    lista.insertAtBack(element);
}

But I can't use it on main, any attempt to enqueue causes crashing in the for loop, that returns error code -1073741819. The function isEmpty() works and displays true.

Queue<int> f;
std::cout << "created" << endl;
std::cout << f.isEmpty() << endl;

for (int i=0; i<10; i++) {
    f.enqueue(i*5);
}

Output:

created
1

Process finished with exit code -1073741819 (0xC0000005)

I've tried to write a constructor for Queue class to initialize the LList class, but can't find the right way to do it. If I write a main function to test only the LList class, I have no need for initialization, because its construtor already carries on with the job.

c++
queue
singly-linked-list
asked on Stack Overflow Apr 24, 2021 by EduardoGM • edited Apr 24, 2021 by EduardoGM

1 Answer

0

Initially the tail, head are nullptr so when the first element is inserted, you attempt to access tail->next in insertAtBack where tail is nullptr causing the error (probably an uncaught exception), if the tail is nullptr, simply assign it the tmp value. place a nullptr check for the expression like so..


// O(1)
    void insertAtBack(T newvalue) {
        LNode<T>* tmp = new LNode<T>(newvalue, nullptr);

        // if it is nullptr, 
        // it is the first and only element
        // so head = tail = tmp
        if(tail != nullptr) 
            tail->next = tmp;
        tail = tmp;
        if (head == nullptr)
            head = tmp;
        this->size++;
    }

``
answered on Stack Overflow Apr 24, 2021 by WARhead

User contributions licensed under CC BY-SA 3.0