C++ creating Queue using Dynamic Memory

Question

I am trying to create Queue using standard library for some part of my code. For abstract idea my Queue will have Front, Back pointers which points Front and Back elements in the Queue. So when I push something Back ptr will point to new value that has been pushed. And When I pop something front ptr will point the next front value.

For example: First we declare and it is empty, Front Back both points to nullptr,

[] - Front = nullptr, Back = nullptr

push(5)

[5] - Front = 5, Back = 5

push(7)

[7 , 5] - Front = 5, Back = 7

push(4)

[4, 7, 5] - Front = 5, Back = 4

pop()

[4, 7] - Front = 7, Back = 4

pop()

[4] - Front = 4, Back = 4

pop()

[] - Front = nullptr, Back = nullptr

class Queue
{
private:
    struct node
    {
        int value;
        node* next;

        node(int value, node* next = nullptr)
        {
            this->value = value;
            this->next = next;
        }
    };

    node* front, * back;

public:
    //Constructor
    Queue()
    {
        front = nullptr;
        back = nullptr;
    }

    //Class methods:
    void push(int num);
    int pop();
    bool isEmpty();
};

Methods definitions:

void Queue::push(int num)
{
    back = new node(num, back);
}

int Queue::pop()
{
    int num = front->value;
    node * temp = front;
    front = front->next;
    delete temp;
    return num;
}

bool Queue::isEmpty()
{
    if (front == nullptr)
    {
        return true;
    }
    else
    {
        return false;
    }
}

For now I am getting runtime error from the pop() and pop() is not removing the front value.

Answer 1

I rewrite your code:

#include <iostream>
using namespace std;

class Queue
{
private:
    struct node
    {
        int value;
        node* next;

        node(int value, node* next = nullptr)
        {
            this->value = value;
            this->next = next;
        }
    };

    node* front, * back;

public:
    //Constructor
    Queue()
    {
        front = nullptr;
        back = nullptr;
    }

    //Class methods:
    void push(int num);
    int pop();
    bool isEmpty() { return (front == nullptr); }

    void print();
};

void Queue::print()
{
    node* tmp = this->front;
    cout << "[ ";
    while(tmp != nullptr) {
        cout << tmp->value << " ";
        tmp = tmp->next;
    }
    cout << "]";
}

void Queue::push(int num)
{
    node* tmp = new node(num, nullptr);
    if(!isEmpty()) { // if not empty
        back->next = tmp;
        back = tmp;
        return;
    }

    // if list is empty
    front = tmp;
    back = tmp;
}

int Queue::pop()
{
    if (isEmpty()) return 0;
    int num = front->value;
    if (front->next == nullptr) { // if list have only one element
        delete front;
        front = nullptr;
        back = nullptr;
        return num;
    }
    node * temp = front;
    front = front->next;
    delete temp;
    return num;
}

int main() {

    Queue q;
    q.push(5);
    q.push(2);
    q.push(2);
    q.push(5);

    q.print();

    q.pop();
    q.print();

    q.pop();
    q.print();

    q.push(5);
    q.print();

    q.pop();
    q.print();

    q.pop();
    q.print();

    q.pop();
    q.print();

    q.pop();
    q.print();

    q.push(5);
    q.print();

    return 0;
}

I added a print() method because of testing, made isEmpty() cleaner, and added a few conditions to check special cases.

If list is empty and pop() is called nothing needs to be done.

If list is empty and push() is called back and front needs to point to same object.

If list have only one element and pop() is called list need to be cleared, front and back needs to be nullptr