實現使用數組

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++代碼是不言自明的。另請參閱隊列的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; 
} 

相同的視頻教程可以在這裏看到：Data structures: Array implementation of Queue