c++ - 实现循环数组队列

Question

我要实现一个循环数组队列，但我有逻辑错误，我没有得到正确的结果。我需要帮助在 ArrayQueueP4.h 中实现 bool dequeue()。我怀疑它是否正确。

.

我尝试了不同的解决方案，并在堆栈溢出和在线上搜索了之前的问题，但它并没有给我任何关于我在寻找什么的想法

#ifndef ARRAY_QUEUE_P4_
#define ARRAY_QUEUE_P4_
#include "QueueInterface.h"
#include "PrecondViolatedExcept.h"

template<class ItemType>
class ArrayQueueP4 : public QueueInterface<ItemType>
{
private:
    static const int DEFAULT_CAPACITY = 50;
    ItemType items[DEFAULT_CAPACITY + 1]; // Array of queue items
    int front;                   // Index to front of queue
    int back;                    // Index to back of queue

public:
    ArrayQueueP4() : front(DEFAULT_CAPACITY),
        back(DEFAULT_CAPACITY) {};
    // Copy constructor and destructor supplied by compiler
    bool isEmpty() const;
    bool enqueue(const ItemType& newEntry);
    bool dequeue();

    /** @throw  PrecondViolatedExcept if queue is empty. */
    ItemType peekFront() const;
};

ArrayQueueP4.h is the header file for ArrayQueueP4.cpp
#include "ArrayQueueP4.h";

#include "PrecondViolatedExcept.h";

using namespace std;

template <class ItemType>
bool ArrayQueueP4 <ItemType>::isEmpty() const {
    return (front == back);
}

template <class ItemType>
bool ArrayQueueP4 <ItemType>::enqueue(const ItemType& newEntry) {

    if (!isEmpty())

    back = (back + 1) % DEFAULT_CAPACITY;
    items[back] = newEntry;
    back++;
    return true;


}

template<class ItemType>
bool ArrayQueueP4 <ItemType> ::dequeue() {
    bool result = false;
    if (!isEmpty()) {
        front = (front + 1) % DEFAULT_CAPACITY;
        front--;
        result = true;
    }
    return result;
}

template<class ItemType>
ItemType ArrayQueueP4<ItemType>::peekFront() const {

    if (isEmpty())
        throw PrecondViolatedExcept("peekFront() called with an empty queue.");
    else
        return items[front];

}

HERE is my main file main.cpp to test my code


#include <iostream>

#include "ArrayQueueP4.cpp";

using namespace std;

int main() {
    ArrayQueueP4<int> AP;
    AP.enqueue(1);
    AP.enqueue(2);
    AP.enqueue(3);

    /*LinkedQueueP1<int> LP;
    LP.enqueue(1);
    LP.enqueue(2);*/

    cout << "PEEK FRONT: " << AP.peekFront();
    //cout << "PEEK FRONT: " << LP.peekFront();

    system("pause");
    return 0;
}

根据我的主程序文件，当我调用入队函数时，输出现在应该为 1。但是，当我使用 dequeue() 删除第一个项目时，我得到的结果不是 2，而是 -858993460。我不知道这是否是队列的行为方式，但当我删除第一个数字时，第二个数字不应该是下一个行中的第一项吗？

Answer 1

根据您的描述，您的front 和back 定义了一个范围，这样front 是队列中第一个可用的元素，并且back 是“pass-the-end”索引。然后根据这些定义，代码应如下所示:

template <class ItemType>
bool ArrayQueueP4 <ItemType>::enqueue(const ItemType& newEntry) {
    // Check if queue is full
    if ((back + 1) % (DEFAULT_CAPACITY + 1) == front) return false;
    // Append element at one-pass-end position
    items[back] = newEntry;
    // Update the one-pass-end index (back)
    // All your modulo operation should be dealing with DEFAULT_CAPACITY + 1
    // because that is the size of your array
    back = (back + 1) % (DEFAULT_CAPACITY + 1);
    return true;
}

template<class ItemType>
bool ArrayQueueP4 <ItemType> ::dequeue() {
    // Dequeue fail if the queue is empty
    if (isEmpty()) return false;
    front = (front + 1) % (DEFAULT_CAPACITY + 1);
    return true;
}

---

另外，作为提醒，您的代码没有考虑资源管理(尽管它适用于大多数类型并且似乎没有出现任何错误)。当一个项目出队时，它对应的资源应该被释放。作为练习，考虑 ItemType 是 std::unique_ptr(或 std::shared_ptr)的场景。这可能不是您的老师想要的，但这是一种很好的做法。