C++中队列的实现

Question

我在学校学习DataStructure的时候，实现了Queue。

学校的DataStructureclass流程如下。

学生实施了 DS
学生在 Domjudge 提交
Domjudge 根据测试用例对代码进行评分。

我的朋友实现了如下所示的队列。

#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();
        }
    }
    
}

我是这样实现的（Node class 和 main 是一样的，所以我通过了代码）

#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() {}
};

测试用例刚刚入队

但是朋友说的没错，我的代码出现了内存溢出错误

所以我在Domjudge中查看内存使用情况，我的朋友代码和我的代码在内存使用上有很大差距。

为什么这两个代码内存占用差距大？

P.S我英语说得不好。如果有什么不明白的，请告诉我。

Answer 1

首先，rear是不正确的。它检查 head 和 return 尾部。当您第一次设置 head=tail=v 时它恰好正确，但稍后可能会出错。

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

检查下面的 if 语句：

v 如果在您的实现中 enqueue 中的队列已满，则会泄漏。
不要在 C++ 中使用 NULL。你可以参考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;
        }
    }

C++中队列的实现

Implementation of Queue in C++

c++

queue