C++ 使用数组实现一个简单的队列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/8722216/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Implementing a simple queue using arrays
提问by Lu Yas
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?
如何使用数组实现一个简单的队列？
回答by Jason
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.
如果您的队列基于数组，那么为了效率起见，我建议创建一个有界或“循环”队列，其中队列的最大大小是固定的，并且您基本上有一个指向队列数组中的“第一个”和“最后一个”位置，当尾指针（或索引值）移动到数组末尾“过去”的位置时，它实际上移回到数组的开头。基于数组的无界队列效率极低，因为每次填满数组的最大大小时都需要重新分配内存，和/或在删除第一个数组时尝试重新排列元素队列的元素。
Using integral-type array indexes for headand tailrather 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:
采用整体式数组索引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;
}
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.
您可以将此概念扩展到您想要的任何其他功能，即，如果您希望拥有一个单独的功能，例如 STL 用于访问队列头部并实际从队列中“删除”一个元素的功能。
回答by KNU
NOTE: While simulating an array(linear data storage) as a circular data storage and maintaining the properties of Queue, one cell will always be unused. Hence, the maximum capacity of array will be 5 for the array having 6 cells. The c++ code below is self explanatory. Also, see The Linked List Based Implementationof Queue.
注意：在将数组（线性数据存储）模拟为循环数据存储并维护队列的属性时，将始终未使用一个单元格。因此，对于具有 6 个单元的阵列，阵列的最大容量将为 5。下面的 C++ 代码是不言自明的。另请参阅队列的基于链表的实现。
/*Implementation of queue with basic operation using arrays */
#include<iostream>
using namespace std;
#define MAX 6 //to accomodate a maximum of 05 elements as 1 cell pointed by tail will always be vacant
void ENQUE(int key); // ~insertion
int DEQUEUE(); // ~deletion
void TRAVERSE();
bool isEmpty();
bool isFull ();
int Q[MAX], head=0, tail=0; /* Note: head is the side facing cashier and new person joins the queue at tail. So, from cashier point of view tail~rear and head~front.
Q -> [h ][][][][][][][][][][t]
Q -> [h,t][][][][][][][][][][] : initial configuration*/
int main(){
int choice,val,i;
char ch='y';
do{
cout<<"1. For Enqueue \n";
cout<<"2. For Dequeue \n";
cout<<"3. For Traverse \nYour Option : ";
cin>>choice;
switch(choice)
{
case 1 : // insertion
if( isFull() ){
cout<<"\nQueue Full !!!\n";
break;
}
cin>>val;
ENQUE(val);
TRAVERSE();
break;
case 2 : //deletion
if( isEmpty() ){
cout<<"\nQueue Empty !!!\n";
break;
}
cout<<"\nDeleted element from Queue : "<<DEQUEUE()<<endl;
TRAVERSE();
break;
case 3 : //traversal
if( isEmpty() ){
cout<<"\nQueue Empty !!!\n";
break;
}
TRAVERSE();
break;
default :
cout<<"Please choose 1/2/3 !!! \n";
}
cout<<"\nDo you want to continue(y/n):";
cin>>ch;
}while(ch=='y'||ch=='Y'); //end of do loop
return 0;
}
void ENQUE(int x){
Q[tail] = x;
tail =(tail+1)%MAX ; //OR tail = (tail==MAX) ? 0 : tail+1 ; */
}
int DEQUEUE(){
int temp =Q[head];
head =(head+1)%MAX ; //OR head = (head==MAX) ? 0 : head+1 ; */
return temp;
}
void TRAVERSE(){
int i; //simple case: Q -> [ ][ ][h7][8][9][5t][ ][ ][ ][ ][ ]
for(i=head; i!=tail; i=(i+1)% MAX) //complex case: Q -> [16][t][ ][ ][ ][h5][11][12][13][14][15]
cout<<Q[i]<<" ";
cout<<endl;
}
bool isEmpty(){
if(head == tail)
return true;
else
return false;
}
bool isFull(){
if( (tail == MAX-1 && head == 0) || (head == tail + 1) )
return true;
else
return false;
}
A video tutorial of the same can be seen here : Data structures: Array implementation of Queue
可以在这里看到相同的视频教程：数据结构：队列的数组实现
