C creating Queue using Dynamic Memory-CodePudding

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.

CodePudding user response：

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

CodePudding user response：

I noticed that new nodes always have next == nullptr and they are always attached to the end of a list. So why not do that in the constructor? Using Node ** is a well know trick to avoid having separate code paths for the empty list and non-empty lists.

I changed the initialization of member variables to use the modern inline initialization with curly brackets Node* next{nullptr};. In case of Queue you don't even need a constructor anymore.

With the change to Node **back the push and pop method could be simplified a bit.

#include <iostream>

class Queue
{
private:
    struct Node
    {
        int value;
        Node* next{nullptr};

        // prev is the end of the list this Node should be attached to
        // specifically the address of the Node*, not the Node
        Node(Node **prev, int value_) : value(value_) {
            *prev = this;
         }
    };

    Node *front{nullptr};
    // back is the end of the list to attach new Nodes
    // specifically the address of the Node*, not the Node
    // this allows it to be eigther &front or &node.next
    Node **back{&front};

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

    void print();
};

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

void Queue::push(int num)
{
    // Nodes automatically attach to the back
    new Node(back, num);
    // just needs back to be advanced
    back = &((*back)->next);
}

int Queue::pop()
{
    if (isEmpty()) return 0;
    int num = front->value;
    Node * temp = front;
    // advance front
    front = front->next;
    delete temp;
    if (front == nullptr) {
        // empty list now so back has become invalid
        // reset it to point at front
        back = &front;
    }
    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;
}