Реализация простой очереди с использованием массивов

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, а не фактические типов указателей, а также счетчиком для определения общего количества элементов в очереди, ваш Епдиеее и DEQUEUE функций могут выглядеть так же просто, как:

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

ПРИМЕЧАНИЕ: Во время моделирования массива (хранения данных с использованием линейных данных) в качестве циклического хранения данных и поддержания свойств очереди одна ячейка всегда будет использоваться. Следовательно, максимальная емкость массива будет равна 5 для массива, имеющего 6 ячеек. Ниже приведен код 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