使用数组实现简单的队列

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 用于访问队列头并实际上从队列中“删除”元素队列。

Answer 2

注意：在将数组（线性数据存储）模拟为循环数据存储并保持队列属性时，总会有一个单元格未被使用。因此，对于具有 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;
}

可以在此处观看相同的视频教程：数据结构：队列的数组实现