c++ - 使用数组实现一个简单的队列

Question

我对数组、队列和堆栈了解不多。我知道如何实现一个简单的队列。

#include <iostream>
#include <queue>

using namespace std;

void main()
{
    queue<char> queue1;
    queue1.push('a');
    queue1.push('b');
    queue1.push('c');
    queue1.push('d');

    while(!queue1.empty())
    {
        cout << queue1.front();
        queue1.pop();
        cout << endl;
    }

    system("pause");
}

如何使用数组实现简单的队列？

Answer 1

如果您的队列基于数组，那么为了效率起见，我建议创建一个有界或“循环”队列，其中队列的最大大小是固定的，并且您基本上有一个头指针和尾指针指向队列数组中的“第一个”和“最后一个”位置，当尾指针(或索引值)移动到“超过”数组末尾的位置时，它实际上移回了队列的开头大批。基于数组的无界队列效率极低，因为每次填满数组的最大大小时都需要重新分配内存，和/或在删除第一个元素时尝试重新排列数组中的元素队列的元素。

为 head 和 tail 使用整型数组索引而不是实际的指针类型，以及用于确定队列中项目总数的计数器，您的入队和出队函数看起来很简单:

template<typename T>
bool queue<T>::enqueue(const T& item)
{
    if (count == array_size)
        return false;

    array[tail] = item;

    tail = (tail + 1) % array_size;
    count++;

    return true;
}

template<typename T>
bool queue<T>::dequeue(T& item)
{
    if (!count)
        return false;

    item = array[head];

    head = (head + 1) % array_size;
    count--;

    return true;
}

您可以将此概念扩展到您喜欢的任何其他函数，即，如果您更愿意使用像 STL 那样的单独函数来访问队列的头部并实际从队列中“删除”一个元素。