使用 ArrayQueue 的循环队列表示

Question

先前的问题已修复并更新 ARRAYQUEUE.CPP 当前版本

                                 ***CURRENT PROBLEM***

我已经得到我正在排队的项目，可以在我的程序中正确弹出，但由于某种原因，我的队列只输出后面的内容。

输出：

 Item #0: 1


 Item #1: 2

  Here is the queue: 2

resize函数用于ArrayQueue超出容量时加倍大小，当元素出队时容量减半导致元素数量减少容量的一半或更少

ArrayQueue.h:

#ifndef ARRAY_QUEUE_H
#define ARRAY_QUEUE_H

#include "QueueInterface.h"
#include "PrecondViolatedExcep.h"

template<class ItemType>
class ArrayQueue : public QueueInterface<ItemType>
{
public:
    ArrayQueue();
    ArrayQueue(const ArrayQueue& right);
    ArrayQueue operator =(const ArrayQueue& right);
    ~ArrayQueue();
    bool isEmpty() const;
    void enqueue(const ItemType& newEntry);
    void dequeue();
    ItemType peekFront() const;
    void print() const;
    int getSize();
private:
    static const int DEFAULT_CAPACITY = 1;
    ItemType* items;
    int front;
    int back;
    int numItems;
    int capacity;
    void resize(int);
};

#include "ArrayQueue.cpp"
#endif

ArrayQueue.cpp:

#include <iostream>

using namespace std;

template<class ItemType>
ArrayQueue<ItemType>::ArrayQueue() {
    front = 0;
    back = DEFAULT_CAPACITY - 1;
    numItems = 0;
    capacity = DEFAULT_CAPACITY;
    items = new ItemType[capacity];
}





template<class ItemType>
ArrayQueue<ItemType>::ArrayQueue(const ArrayQueue<ItemType>& right)
{
    numItems = right.numItems;
    items = new ItemType[strlen(right.items) + 1];
    strcpy(items, right.items);
}





template<class ItemType>
ArrayQueue<ItemType> ArrayQueue<ItemType>::operator =(const ArrayQueue& right)
{

    if (this != right)
    {
        numItems = right.numItems;
        delete[] items;
        items = new ItemType[right.capacity];
        strcpy(items, right.items);
    }
    return *this;
}






template<class ItemType>
ArrayQueue<ItemType>::~ArrayQueue()
{
    delete[] items;
}




template<class ItemType>
bool ArrayQueue<ItemType>::isEmpty() const {
    return numItems == 0;
}





template<class ItemType>
void ArrayQueue<ItemType>::enqueue(const ItemType& newEntry)
{
    //ItemType* temp = new ItemType;
    if (isEmpty()) {
        //front = back = 0;
        back = (back + 1) % capacity;
        items[back] = newEntry; //Problem *SOLVED FOR NOW*
        //items = temp;
        numItems++;
    }
    else
    {
        if (numItems == capacity)
        {
            resize(2 * capacity);

        }

        back = (back + 1) % capacity;
        //back = (back + 1) % capacity;

        if (back == capacity - 1)
            back = 0;

        items[back] = newEntry;
        //items = temp;
        numItems++;

    }
    std::cout << std::endl;

    std::cout << "Item #" << numItems - 1 << ": " << items[(numItems - 1) % capacity] << std::endl;
    std::cout << endl;

}


template<class ItemType>
int ArrayQueue<ItemType>::getSize()
{
    return capacity;
}


template<class ItemType>
void ArrayQueue<ItemType>::dequeue()
{
    std::cout << std::endl;
    std::cout << "Item Being removed: " << items[front] << std::endl;
    if (isEmpty())
    {
        throw PrecondViolatedExcep();
    }
    else
    {
        if (numItems == capacity / 2)
        {
            resize(capacity / 2);
        }
        if (back == front)
            back = front = 0;
        else
        {
            front = (front + 1) % capacity;
            numItems--;
        }
        std::cout << std::endl;
    }

    std::cout << "New item at front: " << items[front] << std::endl;
    std::cout << std::endl;
}




template<class ItemType>
ItemType ArrayQueue<ItemType>::peekFront() const
{
    if (isEmpty()) {
        throw PrecondViolatedExcep("peekFront() called with empty queue");
    }

    return items[front];
}





template<class ItemType>
void ArrayQueue<ItemType>::print() const {
    std::cout << "Here is the queue: ";
    if (isEmpty()) {
        std::cout << "empty";
    }
    else {
        for (int i = front; i != back; i = (i + 1) % capacity) {
            std::cout << items[i] << " ";
        }
        std::cout << items[back];
    }
}




template<class ItemType>
void ArrayQueue<ItemType>::resize(int newCapacity)
{

    ItemType* temp = new ItemType[newCapacity];
    for (int i = 0; i < capacity; i++)
    {
        int index = (front + i) % capacity;
        temp[i] = items[index];

    }
    front = 0;
    back = numItems - 1;
    delete[] items;
    items = temp;
    capacity = newCapacity;
}

QueueInterface.h:

#ifndef QUEUE_INTERFACE_
#define QUEUE_INTERFACE_

template<class ItemType>
class QueueInterface

{
public:
   /** Sees whether this queue is empty.
    @return True if the queue is empty, or false if not. */
   virtual bool isEmpty() const = 0;

   /** Adds a new entry to the back of this queue.
    @post If the operation was successful, newEntry is at the 
       back of the queue.
    @param newEntry  The object to be added as a new entry.
    @return True if the addition is successful or false if not. */
   virtual void enqueue(const ItemType& newEntry) = 0;

   /** Removes the front of this queue.
    @post If the operation was successful, the front of the queue 
       has been removed.
    @return True if the removal is successful or false if not. */
   virtual void dequeue() = 0;

   /** Returns the front of this queue.
    @pre The queue is not empty.
    @post The front of the queue has been returned, and the
       queue is unchanged.
    @return The front of the queue. */
   virtual ItemType peekFront() const = 0;

   /** Destroys object and frees memory allocated by object. */
   virtual ~QueueInterface() { }
}; // end QueueInterface
#endif

PrecondViolatedExcep.cpp:

#include "PrecondViolatedExcep.h"  

PrecondViolatedExcep::PrecondViolatedExcep(const std::string& message)
         : std::logic_error("Precondition Violated Exception: " + message)
{
}

PrecondViolatedExcep.h:

#ifndef PRECOND_VIOLATED_EXCEP_H
#define PRECOND_VIOLATED_EXCEP_H

#include <stdexcept>
#include <string>


class PrecondViolatedExcep : public std::logic_error
{
    public:
       PrecondViolatedExcep(const std::string& message = "");
};
#endif

用于测试功能的客户端文件：

#include <iostream>
#include "ArrayQueue.h"
#include "PrecondViolatedExcep.h"
#include "QueueInterface.h"

using namespace std;

int main()
{   
    ArrayQueue<int> attempt;

    /*attempt.enqueue(6);
    attempt.enqueue(5);
    attempt.enqueue(4);
    attempt.enqueue(3);
    attempt.enqueue(2);  */

    attempt.enqueue(1);
    attempt.enqueue(2);
    attempt.enqueue(3);


    attempt.print();

    cout << "The capacity is " << attempt.getSize();
}

Answer 1

在这种情况下，我相信您对 Modulo operator (%) 有疑问。

您在许多地方使用了 DEFAULT_CAPACITY，我认为您打算使用 capacity。对任何数字取模 1 应该导致到处都是 0，这意味着您只是 copying/setting/keeping/saving 第一个也是唯一的值，因此只有一个输出。

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

int index = (front + i) % DEFAULT_CAPACITY
temp[i] = items[index];

使用 ArrayQueue 的循环队列表示

Circular Queue Representation using an ArrayQueue

c++

arrays

queue

adt

dynamic-arrays