使用C ++实现队列实现和数组大小调整

Question

代码应该做我正确的队列功能。

我唯一的问题是：一旦数组完全填满，我应该将数组大小加倍到原始大小的两倍。

我编写了它，但当我尝试输入比原始数组大小更多的值时仍然获得垃圾值。所以问题似乎在下面的inc（）函数中：

#ifndef Q_H_
#define Q_H_

#include <iostream>
using namespace std;



template <class elemType>
class arrayQueue
{
    int size;
    int *array;
    int front;
    int back;
    int count;

public:
    arrayQueue(elemType size)
{
        this->size = size;
        array = new int[size];
        front = 0;
        back = -1;
        count=0;
}

    bool isEmpty()
    {
        return (max()==0);
    }

    bool isFull() {
        return (max()==size);
    }

    void enqueue(elemType entry)
    {
        cout << "enqueue " << entry;

        if(isEmpty())
        {
            front = back = 0;
            array[back] = entry;
            count++;
        }
        else
        {
            back = (back+1) % size;
            array[back] = entry;
            count++;
        }
        cout << endl;
    }

    int maxsize()
    {
        return count;
    }

    void dequeue() {
        cout << "dequeue : " << Front();
        if(isEmpty())
        {
            cout << " error : empty";
        }
        else if(back == front)
        {
            back = front = -1;
        }
        else
        {
            front = (front+1) % size;
            count--;
        }
        cout << endl;
    }

    void print()
    {
        if(isEmpty())
        {
            cout << "Queue is empty";
        }
        else
        {
            for(int i = front; i<count; i++)
            {
                cout << array[i] << " ";
            }
            cout << array[back];

        }
        //cout<<"count is:" <<count<<endl;
        cout << endl;
    }

    int Front()
    {

        if(front == -1)
        {
            cout<<"Queue is empty\n";
            return -1;
        }
        return array[front];

    }

    int Back()
    {
        if(back==-1)
        {
            cout<<"Queue is full";
        }
        return array[back];
    }

    int max()
    {
        return count;
        cout <<"count: " <<count;

    }

    void inc()
    {
        int newsize = this->size*2;

        elemType *temp = new elemType[newsize];



        for (int i=0; i<this->count;i++)
        {
            temp[i]=this->array[(front+i) % size];
        }

        delete [] this->array;
        this->array=temp;
        this->count=newsize;

//      front=array[front];  //0
        //front = 0;
        //back=count;


    }


};



#endif /* Q_H_ */

我真的很感激这方面的帮助。

Answer 1

三个小变化：

1. enqueue方法：当isFull时为inc

   if (isFull())
   {
       inc();
   }

2. print方法：从前到后打印每个元素
3. inc方法：从前到后复制每个元素，并重置前后索引

   void inc()
   {
       int newsize = this->size*2;
   
       elemType *temp = new elemType[newsize];
   
       // ******* IMPORTANT ******
       // copy count elements
       for (int i = 0; i < count; ++i) {
           int index = (front + i) % size;
           temp[i] = array[index];
       }
       front = 0;
       back = count - 1;
       delete []array;
       array=temp;
       count=newsize;
   }

---

  template <class elemType>
  class arrayQueue
  {
    int size;
    int *array;
    int front;
    int back;
    int count;
    public:
    arrayQueue(elemType size)
    {
        this->size = size;
        array = new int[size];
        front = 0;
        back = -1;
        count=0;
    }

    bool isEmpty()
    {
        return (max()==0);
    }

    bool isFull() {
        return (max()==size);
    }

    void enqueue(elemType entry)
    {
        cout << "enqueue " << entry;

        if(isEmpty())
        {
            front = back = 0;
            array[back] = entry;
            count++;
        }
        else
        {
            if (isFull()) {
                inc();
            }
            back = (back+1) % size;
            array[back] = entry;
            count++;
        }
        cout << endl;
    }

    int maxsize()
    {
        return count;
    }

    void dequeue() {
        cout << "dequeue : " << Front();
        if(isEmpty())
        {
            cout << " error : empty";
        }
        else if(back == front)
        {
            back = front = -1;
        }
        else
        {
            front = (front+1) % size;
            count--;
        }
        cout << endl;
    }

    void print()
    {
        if(isEmpty())
        {
            cout << "Queue is empty";
        }
        else
        {
            // ******* IMPORTANT ******
            for (int i = 0; i < count; ++i) {
                int index = (front + i) % size;
                cout << array[index] << " ";
            }
        }
        //cout<<"count is:" <<count<<endl;
        cout << endl;
    }

    int Front()
    {

        if(front == -1)
        {
            cout<<"Queue is empty\n";
            return -1;
        }
        return array[front];

    }

    int Back()
    {
        if(back==-1)
        {
            cout<<"Queue is full";
        }
        return array[back];
    }

    int max()
    {
        return count;
        cout <<"count: " <<count;

    }

    void inc()
    {
        int newsize = this->size*2;

        elemType *temp = new elemType[newsize];

        // ******* IMPORTANT ******
        // copy count elements
        for (int i = 0; i < count; ++i) {
            int index = (front + i) % size;
            temp[i] = array[index];
        }

        front = 0;
        back = count - 1;
        delete []array;
        array = temp;
        count = newsize;
    }
    };

Answer 2

由于您将元素移动到新分配的数组的开头，因此inc需要更新front和back以引用它们各自的新位置。

此外，您将count更新为新的大小而不是size。