使用循环数组实现队列

Question

我必须使用循环数组实现队列，但遇到了困难。 这是应该发生的事情： enqueue() 函数返回一个 bool 值：如果在将值入队之前队列未满，则返回 true；如果队列已满，则返回 false，在这种情况下，值不会入队。如果队列非空，则 dequeue() 函数返回出列值；如果队列为空，则返回 0。

这里是 IntegerArrayQueue.h（不要更改）：

`#pragma once

#include <iostream>

using namespace std;

class IntegerArrayQueue
{
    private:
        int* array; //pointer to array of integers
        int front; //index of item to dequeue
        int back; //index of item to enqueue
        int size;

    public:
        IntegerArrayQueue() :
            array(new int[10]), front(0), back(9), size(10)
            {
                for (int i = 0; i<10; i++) array[i]=0;
            }
        IntegerArrayQueue(int size) :
            array(new int[size]), front(0), back(size-1), size(size)
            {
                for (int i = 0; i<size; i++) array[i]=0;
            }
        ~IntegerArrayQueue() { delete [] array;}
        void printArrayQueue()
        {
            for (int i = 0; i<size; i++) cout << array[i] << " ";
            cout << endl;
            cout << "front: " << front << endl;
            cout << "back: " << back << endl;
            cout << "size: " << size << endl;
        }
        //Implement the enqueue and dequeue functions
        //enqueue: if there is space available enqueue value and
        //return true, otherwise return false
        bool enqueue(int value);
        
        //dequeue: if there is a value at the front of the queue
        //return the value and remove from the queue,
        //otherwise return 0
        int dequeue();

};`

IntegerArrayQueue.cpp：

`#include "IntegerArrayQueue.h"


bool IntegerArrayQueue::enqueue(int value)
{
    if ((back + 1) % size == front) {
      return false;
    }

    else {
        back = (back + 1) % size;
        array[back] = value;
        return true;
    }
}

int IntegerArrayQueue::dequeue()
{
    if (front == 0) {
        return 0;
    }
    else {
        int val = array[front];
        if (front == back) {
            front = 0;
            back = 0;
        }
        else {
        front = (front) % size;
        }
        return val;
    }
}`

任何人都可以指导我在 IntegerArrayQueue.cpp 中做错了什么：

对我做错了什么感到困惑

Answer 1

除了原始指针（假设您出于某种原因需要它）之外，您的实现还有几个问题。

IntegerArrayQueue(int size) {
...
    for (int i = 0; i<10; i++) array[i]=0;

出列空队列将返回一个固定值，因此您不需要用它初始化整个数组。

bool IntegerArrayQueue::enqueue(int value)
{
    if ((back + 1) % size == front) {
      return false;
    }
...

一般来说，您不能使用整个数组，也不能仅使用两个变量（

front

和

back

）来区分空队列和满队列。在这两种情况下

front == back

，因此您要么浪费数组的 1 个元素，要么需要布尔标志来区分空队列和满队列。

    }
    else {

如果函数在前一个块中返回，则

else

是多余的。

int IntegerArrayQueue::dequeue()
{
    if (front == 0) {
        return 0;
    }

即使队列不为空，

front

也可以是

0

。

front = (front) % size;

这不会改变

front

。

简单直接的实现可能如下：

template <typename T>
class ring
{
    T *data;
    std::size_t size;
    std::size_t front { 0 };
    std::size_t back  { 0 };
    bool full { false };
public:
    ring(std::size_t _size) : data{new T[_size]}, size{ _size } {}

    ~ring() {
        delete [](data);
    }

    bool enqueue(T value) {
        if (full) {
            return false;
        }
        data[back] = value;
        back = (back + 1) % size;
        if (back == front) {
            full = true;
        }
        return true;
    }

    T dequeue() {
        if ((front == back) && !full) {
            return {};
        }
        full = false;
        size_t old_front = front;
        front = (front + 1) % size;
        return data[old_front];
    }
};

使用示例：

ring<int> ring { 3 };

std::cout << "Dequeue empty: " << ring.dequeue() << '\n';
std::cout << std::boolalpha;

for (int i = 1; i <= 5; ++i) {
    std::cout << "Enqueue " << i << ": " << ring.enqueue(i) << '\n';
}

for (int i = 1; i <= 5; ++i) {
    std::cout << "Dequeue " << i << ": " << ring.dequeue() << '\n';
}

输出：

Dequeue empty: 0
Enqueue 1: true
Enqueue 2: true
Enqueue 3: true
Enqueue 4: false
Enqueue 5: false
Dequeue 1: 1
Dequeue 2: 2
Dequeue 3: 3
Dequeue 4: 0
Dequeue 5: 0