我对数组、队列和堆栈了解不多。我知道如何实现一个简单的队列。
#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");
}
如何使用数组实现简单的队列?
最佳答案
如果您的队列基于数组,那么为了效率起见,我建议创建一个有界或“循环”队列,其中队列的最大大小是固定的,并且您基本上有一个头指针和尾指针指向队列数组中的“第一个”和“最后一个”位置,当尾指针(或索引值)移动到“超过”数组末尾的位置时,它实际上移回了队列的开头大批。基于数组的无界队列效率极低,因为每次填满数组的最大大小时都需要重新分配内存,和/或在删除第一个元素时尝试重新排列数组中的元素队列的元素。
为 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 那样的单独函数来访问队列的头部并实际从队列中“删除”一个元素。
关于c++ - 使用数组实现一个简单的队列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8722216/