Implementation of Queue in C++

Question

When I study the DataStructrue in my school, I implemented the Queue.

School's DataStructure class process is below.

student implemnted the DS
student submit in Domjudge
Domjudge score the code based by test cases.

My freind implemented the Queue like below.

#include <iostream>
#include <string>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    
    Node() {}
    Node(int e) {
        this->data = e;
        this->next = NULL;
    }
    ~Node(){}
};

class SLinkedList {
public:
    Node* head;
    Node* tail;
    
    SLinkedList() {
        head = NULL;
        tail = NULL;
    }
    
    void addFront(int X) {
        Node* v = new Node(X); // new Node
        
        if (head == NULL) {
            // list is empty
            head = tail = v;
        }else {
            v->next = head;
            head = v;
        }
    }
    
    int removeFront() {
        if (head == NULL) {
            return -1;
        }else{
            Node* tmp = head;
            int result = head->data;
            
            head = head->next;
            delete tmp;
            return result;
        }
    }
    
    int front() {
        if (head == NULL) {
            return -1;
        }else {
            return head->data;
        }
    }
    
    int rear() {
        if (head == NULL) {
            return -1;
        }else {
            return tail->data;
        }
    }
    
    int empty() {
        if (head == NULL) {
            return 1;
        }else {
            return 0;
        }
    }
    
    void addBack(int X) {
        Node* v = new Node(X);
        
        if (head == NULL) {
            head = tail = v;
        }else {
            tail->next = v;
            tail = v;
        }
    }
    
    ~SLinkedList() {}
};


class LinkedQ {
public:
    int n = 0;
    int capacity;
    Node* f;
    Node* r;
    SLinkedList Q;
    
    LinkedQ(int size) {
        capacity = size;
        f = NULL;
        r = NULL;
    }
    
    bool isEmpty() {
        return n == 0;
    }
    
    int size() {
        return n;
    }
    
    int front() {
        return Q.front();
    }
    
    int rear() {
        return Q.rear();
    }
    
    void enqueue(int data) {
        if (n == capacity) {
            cout << "Full\n";
        }else {
            Q.addBack(data);
            n++;
        }
    }
};

int main() {
    int s, n;
    string cmd;
    
    cin >> s >> n;
    
    listQueue q(s);
    
    for (int i = 0; i < n; i++) {
        cin >> cmd;
        
        if (cmd == "enqueue") {
            int x;
            cin >> x;
            
            q.enqueue(x);
        }else if (cmd == "size") {
            cout << q.size() << "\n";
        }else if (cmd == "isEmpty") {
            cout << q.isEmpty() << "\n";
        }else if (cmd == "front") {
            q.front();
        }else if (cmd == "rear") {
            q.rear();
        }
    }
    
}

And I implmented like this (Node class and main are same, So I pass the code)

#include <iostream>
#include <string>
using namespace std;

class Node{...};

class listQueue {
public:
    Node* head;
    Node* tail;
    int capacity;
    int n = 0;
    
    listQueue() {
        head = NULL;
        tail = NULL;
    }
    
    void enqueue(int X) {
        Node* v = new Node(X); // new Node

        if (n==capacity) {
           cout << "Full\n";
           return;
        }
        
        if (head == NULL) {
            // Queue is empty
            head = tail = v;
        }else {
            v->next = head;
            head = v;
        }
    }
    
    int front() {
        if (head == NULL) {
            return -1;
        }else {
            return head->data;
        }
    }
    
    int rear() {
        if (head == NULL) {
            return -1;
        }else {
            return tail->data;
        }
    }
    
    int empty() {
        if (head == NULL) {
            return 1;
        }else {
            return 0;
        }
    }
    
    ~listQueue() {}
};

test cases are just enqueue

but my friend is correct, and my code has occured memory over error.

So I check the usage of memory in Domjudge, My friend code and My code has very big gap in memory usage.

Why these two codes have memory usage gap big?

P.S I can't speak English well. If there is something you don't understand, please tell me.

My first glance is both of you never release `new`ed resources in destructor. So both implementations are leaking. — Louis Go, Sep 14 '20 at 06:26

Louis Go · Accepted Answer · 2020-09-14T08:22:45.727

0

First, rear is incorrect. It checks head and return tail. It happens to correct when you first set head=tail=v but it might get wrong later.

    int rear() {
        if (head == NULL) {
            return -1;
        }else {
            return tail->data;
        }
    }

Check the if statement below:

v is leaked if queue is full in enqueue in your implementation.
Don't use NULL in C++. You may refer to NULL vs nullptr (Why was it replaced?).

    void enqueue(int X) {
        Node* v = new Node(X); // new Node 

        if (n==capacity) {     // You're leaking v;
           cout << "Full\n";
           return;
        }
        
        if (head == NULL) {
            // Queue is empty
            head = tail = v;
        }else {
            v->next = head;
            head = v;
        }
    }

edited Sep 14 '20 at 08:22

answered Sep 14 '20 at 06:32

Louis Go

2,213
2
16
29

`head = tail = v` is not same `head = v` and `tail=v`? – coder mate Sep 14 '20 at 08:15
@codermate Sorry I might misread something. It seems the only leakage occurs when queue is full. I edit my post. – Louis Go Sep 14 '20 at 08:24
@codermate I'm not sure how Domjudge to check the memory, but the leakage seems to be the different between two snippet. I'll assume the system try to enqueue multiple times when full to check the leakage. – Louis Go Sep 14 '20 at 08:29

Implementation of Queue in C++

1 Answers1