使用数组实现简单队列

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用来访问队列的头,实际上是"删除"从队列中的元素.