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

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, который указывают на «первую» и «последнюю» позиции в массиве очереди, и когда указатель хвоста (или значение индекса) перемещается в позицию «после» конца массива, он фактически возвращается к началу массив. Неограниченная очередь, основанная на массиве, будет ужасно неэффективной, поскольку вам нужно будет перераспределять память каждый раз, когда вы заполняете максимальный размер массива, и / или пытаться переставлять элементы в массиве при удалении первого элемент очереди.

Использование индексов массива целочисленного типа для 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

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

Видео-ту же туториал можно посмотреть здесь: Структуры данных: реализация массива в очереди