使用数组实现简单队列

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

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

- Lu Yas

---

如果你不理解足够的话，无法从头开始实现它，那就继续使用你已经演示过的std版本。如果这是作业，只需记住队列是先进先出的。 - Mark Ransom

我对你声称“知道如何实现简单队列”的说法提出异议。到目前为止，你只是展示了你会使用一个名为“queue”的库类。 - Kerrek SB

你可以使用循环缓冲区/循环数组来实现队列。请查看此链接以获取一些想法 http://www.vias.org/cppcourse/chap20_05.html - Raghuram

Answer 1

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

使用整数类型的数组索引来代替实际的指针类型，并使用计数器来确定队列中所有项目的总数，您的入队和出队函数可能看起来很简单：

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用于访问队列头部和实际"删除"队列元素的单独函数。

- Jason

---

我可以在堆栈上应用相同的东西吗？ - Lu Yas

是的，当然，虽然堆栈不会像队列那样“绕回”（wrap-around），因为您只能添加和删除“顶部”元素。 - Jason

由于“尾部”溢出可能会导致问题。 - Sumit

请问您能否提供这些操作的一个可行的示例？ - Mohsin

@Sumit的建议似乎非常明智，也许应该编辑这个答案，因为它是被接受的。 - Patrick Trentin

Answer 2

注意:在将数组(线性数据存储)模拟为循环数据存储并保持队列的属性时，始终有一个单元格未使用。因此，对于具有6个单元格的数组，其最大容量为5。下面的C ++ 代码不言自明。另请参见基于链表的队列实现The Linked List Based Implementation。

/*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;
}

这里有一个相同内容的视频教程：数据结构：队列的数组实现

- KNU

---

你的 MAX 定义中的字面值应该只是 6。前导的 0 使它成为一个 八进制 字面值。在这种特定情况下不是问题，但它可能会成为错误的潜在来源。 - Blastfurnace