c++ - 将第一个元素移动到队列的后面

Question

我自己实现了队列。还有旋转方法，它必须将 n 个元素从队列的开头移动到结尾。但我错过了一些要点，不知道我到底应该做什么。您有什么建议吗？

我非常感谢您提供的任何帮助。

我的输出是:

3, 4, 5, 6, 7,
4, 5, 6, 0, 3,
6, 0, 0, 0, 5,

但是，它应该看起来像这样:

3, 4, 5, 6, 7,
4, 5, 6, 7, 3,
5, 6, 7, 3, 4,

struct Queue
{
private:
    int *data = nullptr;
    int capacity = 100;
    int counter = 0;
    int first = 0;
    int aftr = 0;

public:
    void push_back(int value)
    {
        if (aftr == capacity)
        {
            if (counter < capacity)
            {
                for (int i = 0; i < counter; i++)
                {
                    data[i] = data[first + i];
                }
                first = 0;
                aftr = counter;
            }
        }
        else
        {
            capacity = capacity * 2;
            int *tmp = new int[capacity];
            for (int i = 0; i < counter; i++)
                tmp[i] = data[i];
            delete[] data;
            data = tmp;
        }

        data[aftr] = value;
        aftr++;
        counter++;
    }
    bool empty()
    {
        return counter == 0;
    }
    int pop_front()
    {
        if (counter == 0)
        {
            std::cout << "Queue is empty" << std::endl;
        }
        int value = data[first];
        first++;
        counter--;
        return value;
    }

    void print()
    {
        if (counter == 0)
        {
            std::cout << "Empty queue" << std::endl;
        }
        else
        {
            for (int i = 0; i < counter; i++)
            {
                std::cout << data[first + i] << ", ";
            }

            std::cout << std::endl;
        }
    }
    int front()
    {
        if (counter == 0)
            std::cout << "Queue is empty" << std::endl;

        int firstElement = data[first];
        return firstElement;
    }
    int back()
    {
        if (counter == 0)
            std::cout << ("Queue is empty") << std::endl;
        int lastElement = data[aftr - 1];
        return lastElement;
    }

    void rotate(int n)
    {
        for (int i = 0; i < n; i++)
        {
            const int tmp = front();
            pop_front();
            push_back(tmp);
        }
    }
};

int main()
{
    Queue q;
    q.push_back(3);
    q.push_back(4);
    q.push_back(5);
    q.push_back(6);
    q.push_back(7);

    q.print();
    q.rotate(1);
    q.print();
    q.rotate(2);
    q.print();
}

Answer 1

调用 push_back 函数时，您的代码存在重复内存分配问题。条件检查 if(aftr ==capacity) 始终为 false。

最好在类构造函数期间分配预定义的内存。

这是修改后的代码片段。 DEMO

struct Queue
{
private:
    constexpr static int initialCapacity = 100;
    int capacity = 0;
    int *data = nullptr;
    int counter = 0;
    int first = 0;
    int aftr = 0;

public:

    Queue():data{new int[initialCapacity]},capacity{initialCapacity}{}

    void push_back(int value)
    {
        if ((aftr == capacity) && (counter < capacity))
        {
            for (int i = 0; i < counter; i++)
            {
                data[i] = data[first + i];
            }
            first = 0;
            aftr = counter;
        }
        else if(counter == capacity)
        //^^^ here memory allocation happens only when current queue memory exhausted
        {
            capacity = capacity * 2;
            int *tmp = new int[capacity];
            for (int i = 0; i < counter; i++)
                tmp[i] = data[i];
            delete[] data;
            data = tmp;
        }

        data[aftr] = value;
        aftr++;
        counter++;
    }
  //rest of the code follows here
};