• Очередь это связано с

    Закрыть ... [X]

    Очередь – структура данных типа «список», позволяющая добавлять элементы лишь в конец списка, и извлекать их из его начала. Она функционирует по принципу FIFO (First In, First Out — «первым пришёл — первым вышел»), для которого характерно, что все элементы a1, a2, …, an-1, an, добавленные раньше элемента an+1, должны быть удалены прежде, чем будет удален элемент an+1. Также очередь может быть определена как частный случай односвязного списка, который обслуживает элементы в порядке их поступления. Как и в «живой» очереди, здесь первым будет обслужен тот, кто пришел первым.

     

    Очередь

    Очередь

     

    Стандартный набор операций (часто у разных авторов он не идентичен), выполняемых над очередями, совпадает с тем, что используется при обработке стеков:

    • добавление элемента;
    • удаление элемента;
    • чтение первого элемента.

    Только, если в отношении стека в момент добавления или удаления элемента допустимо задействование лишь его вершины, то касательно очереди эти две операции должны быть применены так, как это регламентировано в определении этой структуры данных, т. е. добавление – в конец, удаление  – из начала. Далее, при реализации интерфейса очереди, список стандартных операций будет расширен.

    Выделяют два способа программной реализации очереди. Первый из них основан на базе массива, а второй на базе указателей (связного списка). Первый способ – статический, т. к. очередь представляется в виде простого статического массива, второй – динамический.

    Реализация очереди с помощью массива

    Данный способ позволяет организовать и впоследствии обрабатывать очередь, имеющую фиксированный размер. Определим список операций, который будет использоваться как при реализации статической очереди, так и динамической:

    • Creation(Q) – создание очереди Q;
    • Full(Q) – проверка очереди Q на пустоту;
    • Add(Q) – добавление элемента в очередь Q (его значение задается из функции);
    • Delete(Q) – удаление элемента из очереди Q;
    • Top(Q) – вывод начального элемента очереди Q;
    • Size(Q) – размер очереди Q.

    В программе каждая из этих операций предстанет в виде отдельной подпрограммы. Помимо того, потребуется описать массив данных data[N], по сути, являющийся хранилищем данных вместимостью N, а также указатель на конец очереди (на ту позицию, в которую будет добавлен очередной элемент) – last. Изначально last равен 0.

     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78

    #include "stdafx.h"
    #include <iostream>
    using namespace std;
    const int N=4; //размер очереди
    struct Queue
    {
    int data[N]; //массив данных
    int last; //указатель на начало
    };
    void Creation(Queue Q) //создание очереди
    { Q->last=0; }
    bool Full(Queue Q) //проверка очереди на пустоту
    {
    if (Q->last==0) return true;
    else return false;
    }
    void Add(Queue Q) //добавление элемента
    {
    if (Q->last==N)
    { cout<<"\nОчередь заполнена\n\n"; return; }
    int value;
    cout<<"\nЗначение > "; cin>>value;
    Q->data[Q->last++]=value;
    cout<<endl<<"Элемент добавлен в очередь\n\n";
    }
    void Delete(Queue Q) //удаление элемента
    {
    for (int i=0; i<Q->last && i<N; i++) //смещение элементов
    Q->data[i]=Q->data[i+1]; Q->last--;
    }
    int Top(Queue Q) //вывод начального элемента
    { return Q->data[0]; }
    int Size(Queue Q) //размер очереди
    { return Q->last; }
    void main() //главная функция
    {
    setlocale(LC_ALL,"Rus");
    Queue Q;
    Creation(&Q);
    char number;
    do
    {
    cout<<"1. Добавить элемент"<<endl;
    cout<<"2. Удалить элемент"<<endl;
    cout<<"3. Вывести верхний элемент"<<endl;
    cout<<"4. Узнать размер очереди"<<endl;
    cout<<"0. Выйти\n\n";
    cout<<"Номер команды > "; cin>>number;
    switch (number)
    {
    case '1': Add(&Q);
    break;
    //-----------------------------------------------
    case '2':
    if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
    else
    {
    Delete(&Q);
    cout<<endl<<"Элемент удален из очереди\n\n";
    } break;
    //-----------------------------------------------
    case '3':
    if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
    else cout<<"\nНачальный элемент: "<<Top(&Q)<<"\n\n";
    break;
    //-----------------------------------------------
    case '4':
    if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
    else cout<<"\nРазмер очереди: "<<Size(&Q)<<"\n\n";
    break;
    //-----------------------------------------------
    case '0': break;
    default: cout<<endl<<"Команда не определена\n\n";
    break;
    }
    } while(number!='0');
    system("pause");
    }

     

    В функции main, сразу после запуска программы, создается переменная Q структурного типа Queue, адрес которой будет посылаться в функцию (в зависимости от выбора операции) как фактический параметр. Функция Creation создает очередь, обнуляя указатель на последний элемент. Далее выполняется оператор цикла do..while (цикл с постусловием), выход из которого осуществляется только в том случае, если пользователь ввел 0 в качестве номера команды. В остальных случаях вызывается подпрограмма соответствующая команде, либо выводиться сообщение о том, что команда не определена.

    Из всех подпрограмм особого внимания заслуживает функция Delete. Удаление элемента из очереди осуществляется путем сдвига всех элементов в начало, т. е. значения элементов переписываются: в data[0] записывается значение элемента data[1], в data[1] – data[2] и т. д.; указатель конца смещается на позицию назад. Получается, что эта операция требует линейного времени O(n), где n – размер очереди, в то время как остальные операции выполняются за константное время. Данная проблема поддается решению. Вместо «мигрирующей» очереди, наиболее приемлемо реализовать очередь на базе циклического массива. Здесь напрашивается аналогия с «живой» очередью: если в первом случае покупатели подходили к продавцу, то теперь продавец будет подходить к покупателям (конечно, такая тактика оказалась бы бесполезной, например, в супермаркетах и т. п.). В приведенной реализации очередь считалась заполненной тогда, когда указатель last находился над последней ячейкой, т. е. на расстоянии N элементов от начала. В циклическом варианте расширяется интерпретация определения позиции last относительно начала очереди. Пусть на начало указывает переменная first. Представим массив в виде круга – замкнутой структуры. После последнего элемента идет первый, и поэтому можно говорить, что очередь заполнила весь массив, тогда когда ячейки с указателями last и first находятся радом, а именно за last следует first. Теперь, удаление элемента из очереди осуществляется простым смещением указателя first на одну позицию вправо (по часовой); чтобы добавить элемент нужно записать его значение в ячейку last массива data и сместить указатель last на одну позицию правее. Чтобы не выйти за границы массива воспользуемся следующей формулой:

    (A mod N) + 1

    Здесь A – один из указателей, N – размер массива, а mod – операция взятия остатка от деления.

    В циклической реализации, как и прежде, очередь не содержит элементов тогда, когда first и last указывают на одну и ту же ячейку. Но в таком случае возникает одно небольшое отличие этой реализации от предшествующей. Рассмотрим случай заполнения очереди, основанной на базе массива, размер которого 5:

     

    Элементы first last — 1 1 1 1 2 1, 2 1 3 1, 2, 3 1 4 1, 2, 3, 4 1 5

     

    В левом столбце записаны произвольные значения элементов, а в двух других значения указателей при соответствующем состоянии очереди. Необходимо заметить, что в массив размером 5 удалось поместить только 4 элемента. Все дело в том, что еще один элемент требует смещения указателя last на позицию 1. Тогда last=first. Но именно эта ситуация является необходимым и достаточным условием отсутствия в очереди элементов. Следовательно, мы не можем хранить в массиве больше N-1 элементов.

    В следующей программе реализован интерфейс очереди, основанной на базе циклического массива:

     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83

    #include "stdafx.h"
    #include <iostream>
    using namespace std;
    const int N=6; //размер очереди
    struct Queue
    {
    int data[N]; //массив данных
    int first; //указатель на начало
    int last; //указатель на конец
    };
    void Creation(Queue Q) //создание очереди
    { Q->first=Q->last=1; }
    bool Full(Queue Q) //проверка очереди на пустоту
    {
    if (Q->last==Q->first) return true;
    else return false;
    }
    void Add(Queue Q) //добавление элемента
    {
    int value;
    cout<<"\nЗначение > "; cin>>value;
    if ((Q->last%(N-1))+1==Q->first)
    cout<<"\nОчередь заполнена\n\n";
    else
    {
    Q->data[Q->last]=value;
    Q->last=(Q->last%(N-1))+1;
    cout<<endl<<"Элемент добавлен в очередь\n\n";
    }
    }
    void Delete(Queue Q) //удаление элемента
    {
    Q->first=(Q->first%(N-1))+1;
    cout<<endl<<"Элемент удален из очереди\n\n";
    }
    int Top(Queue Q) //вывод начального элемента
    { return Q->data[Q->first]; }
    int Size(Queue Q) //размер очереди
    {
    if (Q->first>Q->last) return (N-1)-(Q->first-Q->last);
    else return Q->last-Q->first;
    }
    void main() //главная функция
    {
    setlocale(LC_ALL,"Rus");
    Queue Q;
    Creation(&Q);
    char number;
    do
    {
    cout<<"1. Добавить элемент"<<endl;
    cout<<"2. Удалить элемент"<<endl;
    cout<<"3. Вывести верхний элемент"<<endl;
    cout<<"4. Узнать размер очереди"<<endl;
    cout<<"0. Выйти\n\n";
    cout<<"Номер команды > "; cin>>number;
    switch (number)
    {
    case '1': Add(&Q);
    break;
    //-----------------------------------------------
    case '2':
    if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
    else Delete(&Q);
    break;
    //-----------------------------------------------
    case '3':
    if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
    else cout<<"\nНачальный элемент: "<<Top(&Q)<<"\n\n";
    break;
    //-----------------------------------------------
    case '4':
    if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
    else cout<<"\nРазмер очереди: "<<Size(&Q)<<"\n\n";
    break;
    //-----------------------------------------------
    case '0': break;
    default: cout<<endl<<"Команда не определена\n\n";
    break;
    }
    } while(number!='0');
    system("pause");
    }

     

    Таким образом, циклический вариант позволяет оптимизировать операцию Delete, которая прежде требовала линейного времени, а теперь выполняется за константное, независимо от длины очереди. Тем не менее, реализация очереди на базе массива имеет один существенный недостаток: размер очереди статичен, поскольку зависит от размера массива. Реализация очереди на базе связного списка позволит обойти эту проблему.

    Реализация очереди с помощью указателей

    Данный способ предполагает работу с динамической памятью. Для представления очереди используется односвязный список, в конец которого помещаются новые элементы, а старые извлекаются, соответственно, из начала списка. Здесь каждый узел списка имеет два поля: информационное и связующее:

     

    1
    2
    3
    4
    5

    struct Node
    {
    int data;
    Node next;
    };

     

    Также понадобиться определить указатели на начало и конец очереди:

     

    1
    2
    3
    4
    5

    struct Queue
    {
    Node first;
    Node last;
    };

     

    Следующее консольное приложение обслуживает очередь, каждый элемент которой – целое число. Весь процесс обуславливают все те же операции: Creation, Full, Add, Delete, Top, Size.

     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88

    #include "stdafx.h"
    #include <iostream>
    using namespace std;
    struct Node //описание узла списка
    {
    int data; //информационное поле
    Node next; //указатель на следующий элемент
    };
    struct Queue //описание очереди
    {
    int size; //счетчик размера очереди
    Node first; //указатель на начало очереди
    Node last; //указатель на конец очереди
    };
    void Creation(Queue Q) //создание очереди
    {
    Q->first=new Node;
    Q->first->next=NULL;
    Q->last=Q->first;
    Q->size=0;
    }
    bool Full(Queue Q) //проверка очереди на пустоту
    {
    if (Q->first==Q->last) return true;
    else return false;
    }
    int Top(Queue Q) //вывод начального элемента
    { return Q->first->next->data; }
    void Add(Queue Q) //добавление элемента
    {
    int value;
    cout<<"\nЗначение > "; cin>>value;
    Q->last->next=new Node;
    Q->last=Q->last->next;
    Q->last->data=value; //добавление элемента в конец
    Q->last->next=NULL; //обнуление указателя на следующий элемент
    Q->size++;
    cout<<"\nЭлемент добавлен\n\n";
    }
    void Delete(Queue Q) //удаление элемента
    {
    Q->first=Q->first->next; //смещение указателя
    Q->size--;
    cout<<"\nЭлемент удален\n\n";
    }
    int Size(Queue Q) //размер очереди
    { return Q->size; }
    void main() //главная функция
    {
    setlocale(LC_ALL,"Rus");
    Queue Q;
    Creation(&Q);
    char number;
    do
    {
    cout<<"1. Добавить элемент"<<endl;
    cout<<"2. Удалить элемент"<<endl;
    cout<<"3. Вывести верхний элемент"<<endl;
    cout<<"4. Узнать размер очереди"<<endl;
    cout<<"0. Выйти\n\n";
    cout<<"Номер команды > "; cin>>number;
    switch (number)
    {
    case '1': Add(&Q);
    break;
    //-----------------------------------------------
    case '2':
    if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
    else Delete(&Q);
    break;
    //-----------------------------------------------
    case '3':
    if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
    else { cout<<"\nНачальный элемент: "<<Top(&Q)<<"\n\n"; }
    break;
    //-----------------------------------------------
    case '4':
    if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
    else cout<<"\nРазмер очереди: "<<Size(&Q)<<"\n\n";
    break;
    //-----------------------------------------------
    case '0': break;
    default: cout<<endl<<"Команда не определена\n\n";
    break;
    }
    } while(number!='0');
    system("pause");
    }

     

    Как отмечалось, этот способ позволяет не заботиться о месте, отводимом под рассматриваемую структуру данных – ее объем ограничен лишь памятью компьютера. Тем не менее, к числу недостатков данной реализации, в сравнении с предыдущей, можно отнести: увеличение времени обработки и количества памяти, да и сам код несколько сложнее для понимания.


    Источник: http://kvodo.ru/queue.html


    Поделись с друзьями



    Рекомендуем посмотреть ещё:



    Квалифицированный персонал набирать труднее, чем неквалифицированный Что можно нарисовать из символов

    Очередь это связано с Очередь это связано с Очередь это связано с Очередь это связано с Очередь это связано с Очередь это связано с Очередь это связано с Очередь это связано с

    ШОКИРУЮЩИЕ НОВОСТИ


    art-poisk.ru