Dizileri kullanarak basit bir sıra uygulama

Question

Diziler ve sıralar ve yığınlar hakkında pek bir şey bilmiyorum. Basit bir kuyruğu nasıl uygulayacağımı biliyorum.

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

Diziyi kullanarak basit bir kuyruğu nasıl uygularım?

Answer 1

Sıranınız bir diziye dayanıyorsa, o zaman verimlilik için, sıranın maksimum boyutunun sabit olduğu sınırlı ve "dairesel" bir sıra oluşturulmasını öneririm ve temel olarak bir baş ve kuyruk işaretçisine sahip olursunuz Bu, kuyruğun dizisindeki "ilk" ve "son" konumlarına işaret eder ve kuyruk işaretçisi (veya bir indeks değeri) dizinin sonuna "geçmiş" bir konuma hareket ettiğinde, aslında geri başlangıcına gider. dizi. Bir diziyi temel alan sınırsız bir sıra, dizinin maksimum boyutunu her doldurduğunuzda hafızayı yeniden tutmaya ihtiyaç duyacağınız ve/veya ilkini kaldırdığınızda dizinin altındaki öğeleri yeniden karıştırmaya çalıştığınız için çok verimsiz olur. sıranın elemanı.

kullanma ayrılmaz tipi dizisi head için endeksler ve bir Sıranızdaki öğelerin toplam sayısını belirlemek için sayaç, senin enqueue ve dequeue fonksiyonları ile birlikte oldukça gerçek işaretçi türlerinden daha tail, görünebilir kadar basit:

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

Bu konsepti, istediğiniz diğer işlevlere, yani, STL'nin sıraya erişim için kullandığı ve aslında bir öğenin sıradan "kaldırıldığı" gibi ayrı bir işlev kullanmasını istiyorsanız, genişletebilirsiniz.

Answer 2

NOT: Bir dizi (doğrusal veri deposu) bir dairesel veri deposu olarak simüle edilirken ve Kuyruğun özelliklerini korurken, bir hücre her zaman kullanılmayacaktır. Bu nedenle, 6 hücreye sahip dizi için dizinin maksimum kapasitesi 5 olacaktır. Aşağıdaki C++ kodu kendiliğinden açıklayıcıdır. Ayrıca, Kuyruğun The Linked List Based Implementation'a bakın.

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

aynısının bir video öğretici

burada görülebilir: Data structures: Array implementation of Queue