c++ - 使用 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. 入队方法:isFull 时包含

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

2. 打印方法:从前往后打印每个元素

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;
    }
    };