使用数组实现一个简单的队列 [英] Implementing a simple queue using arrays

问题描述

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

I don't know much about arrays and queues and stacks. I know how to implement a simple queue.

#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");
}

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

How can I implement a simple queue using an array?

推荐答案

如果您的队列基于数组，那么为了效率，我建议创建一个有界或循环队列，队列的大小是固定的，你基本上有一个头和尾的指针指向队列的数组中的第一和最后位置，当尾指（或一个索引值）移动到一个位置过去数组的末尾，它实际上移回到数组的开头。基于数组的无界队列将非常低效，因为您需要在每次填充数组的最大大小时重新分配内存，并且/或尝试在元素下移时重新将元素重新洗牌。

If your queue is based on an array, then for efficiency's sake, I would recommend creating a bounded or "circular" queue, where the max-size of the queue is fixed, and you basically have a head and tail pointer that point to the "first" and "last" positions in the queue's array, and when the tail-pointer (or an index value) moves to a position "past" the end of the array, it actually moves back to the beginning of the array. An unbounded queue based on an array would be horribly inefficient, as you would need to keep reallocating memory each time you fill up the max-size of the array, and/or attempt to re-shuffle elements down the array when you remove the first element of the queue.

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

Using integral-type array indexes for head and tail rather than actual pointer types, along with a counter for determining the overall number of items in your queue, your enqueue and dequeue functions could look as simple as:

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用于访问队列的头部，实际上从队列中删除一个元素。

You can extend this concept to whatever other functions you'd like, i.e., if you'd rather have a separate functions like the STL uses for accessing the head of the queue and actually "removing" an element from the queue.

这篇关于使用数组实现一个简单的队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！