Очередь: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показаны 23 промежуточные версии этого же участника)
Строка 1: Строка 1:
== TLDR ==
<youtube width="300" height="180">2lumODP7BtI</youtube>
== Общие сведения ==
== Общие сведения ==
Очередь (англ. queue) &mdash; абстрактный контейнер, доступ к элементам которого организован по принципу «первым вошёл &mdash; первым вышел» (англ. FIFO, First In &mdash; First Out). Поведение элементов очереди напоминает обслуживание покупателей в магазине: каждый новый клиент встаёт в конец очереди и ожидает, когда уйдут все стоящие перед ним.
Очередь (англ. queue) &mdash; абстрактный контейнер, доступ к элементам которого организован по принципу «первым вошёл &mdash; первым вышел» (англ. FIFO, First In &mdash; First Out). Поведение элементов очереди напоминает обслуживание покупателей в магазине: каждый новый клиент встаёт в конец очереди и ожидает, когда уйдут все стоящие перед ним.
Строка 7: Строка 10:
Очередь предоставляет три основные операции:
Очередь предоставляет три основные операции:


{|
{| class="methodlist"
| <tt>void enqueue(T value)</tt> || &mdash; вставка элемента <tt>value</tt> в очередь;
| || void || enqueue(T value) || &mdash; вставка элемента <tt>value</tt> в очередь;
|-
|-
| <tt>T dequeue()</tt>         || &mdash; извлечение элемента из очереди;
| ||    T || dequeue()       || &mdash; извлечение элемента из очереди;
|-
|-
| <tt>bool isEmpty()</tt>       || &mdash; проверка очереди на отсутствие элементов.
| || bool || isEmpty()        || &mdash; проверка очереди на отсутствие элементов.
|}
|}


Строка 18: Строка 21:


== Демонстрация работы ==
== Демонстрация работы ==
[[Демонстрация работы очереди]]
 
* [http://www.cs.usfca.edu/~galles/visualization/QueueLL.html Data Structure Visualizations — Queue (Linked List Implementation)]
* [http://www.cs.usfca.edu/~galles/visualization/QueueArray.html Data Structure Visualizations — Queue (Array Implementation)]
* [http://visualgo.net/list.html VisuAlgo &mdash; Linked List, Stack, Queue, Deque]


== Реализация на списке ==
== Реализация на списке ==
Строка 30: Строка 36:
         next = n;
         next = n;
     }
     }
  } * head, * tail;
  } *head, *tail;


В конструкторе очереди указатели на голову и хвост инициализируются значением <tt>NULL</tt>.
В конструкторе очереди указатели на голову и хвост инициализируются значением <tt>NULL</tt>.
Строка 43: Строка 49:


  bool isEmpty() {
  bool isEmpty() {
     return top == NULL;
     return head == NULL;
  }
  }


Строка 117: Строка 123:
         else
         else
             tail = tail->next = new Node(value, NULL);
             tail = tail->next = new Node(value, NULL);
        }
    }
   
   
     int dequeue() {
     int dequeue() {
         assert(head != NULL)
         assert(head != NULL);
         int v = head->val;
         int v = head->val;
         Node *tmp = head;
         Node *tmp = head;
Строка 151: Строка 157:
Получается ситуация, в которой область, содержащая хранящиеся в очереди элементы, непрерывно смещается в сторону конца массива. Решением этой проблемы является «зацикливание» очереди, когда все смещения индексов происходят по модулю длины массива. Тогда после достижения конца массива область хранения элементов продолжается в начале массива.
Получается ситуация, в которой область, содержащая хранящиеся в очереди элементы, непрерывно смещается в сторону конца массива. Решением этой проблемы является «зацикливание» очереди, когда все смещения индексов происходят по модулю длины массива. Тогда после достижения конца массива область хранения элементов продолжается в начале массива.


[[Файл:queue_array_cycle.png|thumb|right|Работа очереди на циклическом массиве]]
[[Файл:queue_array_cycle.gif|thumb|right|360px|Работа очереди на циклическом массиве]]


Выше показана работа очереди на массиве из 10 элементов. Производится бесконечный цикл из двух операций вставки и двух операций извлечения. Символом «xx» обозначены ячейки массива, которые в текущий момент не хранят элементы очереди (и фактические значения которых нам в данный момент безразличны).
На иллюстрации показана работа очереди на массиве из 10 элементов. Производится бесконечный цикл из двух операций вставки и двух операций извлечения. Символом «xx» обозначены ячейки массива, которые в текущий момент не хранят элементы очереди (и фактические значения которых нам в данный момент безразличны).


=== Проверка на пустоту ===
=== Проверка на пустоту ===
Строка 203: Строка 209:
   
   
     void enqueue(int value) {
     void enqueue(int value) {
         assert((tail + 1) % MAX_SIZE != head)
         assert((tail + 1) % MAX_SIZE != head);
         a[tail] = value;
         a[tail] = value;
         tail = (tail + 1) % MAX_SIZE;
         tail = (tail + 1) % MAX_SIZE;
Строка 209: Строка 215:
   
   
     int dequeue() {
     int dequeue() {
         assert(head != tail)
         assert(head != tail);
         int tmp = head;
         int tmp = head;
         head = (head + 1) % MAX_SIZE;
         head = (head + 1) % MAX_SIZE;
Строка 222: Строка 228:


== Очередь в STL ==
== Очередь в STL ==
В стандартной библиотеке шаблонов C++ присутствует шаблон <tt>queue<T></tt>. Для возможности его использования требуется подключить заголовочный файл <tt><queue></tt> и пространство имён <tt>std</tt>:
В стандартной библиотеке шаблонов C++ присутствует шаблон [http://www.cplusplus.com/reference/queue/queue/ <tt>queue<T></tt>]. Для возможности его использования требуется подключить заголовочный файл <tt><queue></tt> и пространство имён <tt>std</tt>:


  #include <iostream>
  #include <iostream>
  #include <queue>
  #include <queue>
  using namespace std;
  using namespace std;
    int main() {
int main() {
     queue<int> q;
     queue<int> q;
     for (int i = 1; i < 6; i++)
     for (int i = 1; i < 6; i++)
         q.push(i);
         q.push(i);
        while (!s.empty()) {
    while (!s.empty()) {
            cout << q.front() << ' ';
        cout << q.front() << ' ';
         q.pop();
         q.pop();
     }             
     }             
Строка 240: Строка 246:
STL предоставляет следующий набор методов для очереди:
STL предоставляет следующий набор методов для очереди:


{|
{| class="methodlist"
| <tt>queue<T>()</tt>            || — конструктор;
| ||        || queue<T>()       || — конструктор;
|-
|-
| <tt>void push(const T& x)</tt> || — добавление элемента;
| ||  void || push(const T& x) || — добавление элемента;
|-
|-
| <tt>void pop()</tt>           || — удаление элемента. Обратите внимание на то, что значение удаляемого элемента не возвращается;
| ||  void || pop()            || — удаление элемента. Обратите внимание на то, что значение удаляемого элемента не возвращается;
|-
|-
| <tt>T& front()</tt>            || — получение значения элемента в голове очереди. Этот метод не производит удаление элемента;
| ||    T& || front()         || — получение значения элемента в голове очереди. Этот метод не производит удаление элемента;
|-
|-
| <tt>T& back()</tt>            || — получение значения элемента в хвосте очереди. Этот метод не производит удаление элемента;
| ||    T& || back()           || — получение значения элемента в хвосте очереди. Этот метод не производит удаление элемента;
|-
|-
| <tt>bool empty()</tt>         || — проверка на пустоту;
| ||  bool || empty()          || — проверка на пустоту;
|-
|-
| <tt>size_t size()</tt>        || — получение количества элементов в очереди. Метод возвращает беззнаковое целое число.
| || size_t || size()           || — получение количества элементов в очереди. Метод возвращает беззнаковое целое число.
|}
|}


Строка 259: Строка 265:
Дек (англ. deque, double-ended queue) — тип, представляющий двустороннюю очередь, оба конца которой могут принимать и возвращать элементы. Интерфейс дека похож на интерфейс очереди, но содержит по паре методов вставки и удаления (для начала и конца двусторонней очереди). Дек естественным образом реализуется на двусвязном списке или на массиве.
Дек (англ. deque, double-ended queue) — тип, представляющий двустороннюю очередь, оба конца которой могут принимать и возвращать элементы. Интерфейс дека похож на интерфейс очереди, но содержит по паре методов вставки и удаления (для начала и конца двусторонней очереди). Дек естественным образом реализуется на двусвязном списке или на массиве.


В стандартной библиотеке шаблонов C++ шаблон <tt>std::deque<T></tt>, объявленный в заголовочном файле <tt><deque></tt>, является базой для шаблонов стека и очереди и поддерживает значительно более широкий набор операций по сравнению с ними (в том числе доступ к элементам с помощью метода <tt>at()</tt> или оператора <tt>[]</tt>, вставки значения в любую позицию с помощью метода <tt>insert()</tt>, доступ к итераторам и т. д.). Вставка элементов в дек STL производится с помощью методов <tt>push_front()</tt> и <tt>push_back()</tt>, удаление — с помощью <tt>pop_front()</tt> и <tt>pop_back()</tt>.
В стандартной библиотеке шаблонов C++ шаблон [http://www.cplusplus.com/reference/deque/deque/ <tt>std::deque<T></tt>], объявленный в заголовочном файле <tt><deque></tt>, является базой для шаблонов стека и очереди и поддерживает значительно более широкий набор операций по сравнению с ними (в том числе доступ к элементам с помощью метода <tt>at()</tt> или оператора <tt>[]</tt>, вставки значения в любую позицию с помощью метода <tt>insert()</tt>, доступ к итераторам и т. д.). Вставка элементов в дек STL производится с помощью методов <tt>push_front()</tt> и <tt>push_back()</tt>, удаление — с помощью <tt>pop_front()</tt> и <tt>pop_back()</tt>.
 
== Ссылки ==
Теория:
* [http://e-maxx.ru/algo/stacks_for_minima e-maxx.ru — Модификация очереди для нахождения минимума]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C neerc.ifmo.ru/wiki — Очередь]
* [https://brestprog.by/topics/datastructures/ brestprog.by — Простейшие структуры данных: стек, очередь, дек]
* [http://algorithmica.org/tg/basic-data-structures algorithmica.org — Стек и другие структуры данных]
* [http://opendatastructures.org/ods-cpp/2_3_Array_Based_Queue.html opendatastructures.org — ArrayQueue]
* [http://opendatastructures.org/ods-cpp/3_1_Singly_Linked_List.html#SECTION00711000000000000000 opendatastructures.org — Queue operations via SLList]
* [https://algs4.cs.princeton.edu/lectures/keynote/13StacksAndQueues.pdf algs4.cs.princeton.edu/lectures — 1.3 Stacks and Queues]
Демонстрация:
* [https://visualgo.net/en/list visualgo.net — Queue]
* [https://www.cs.usfca.edu/~galles/visualization/QueueArray.html www.cs.usfca.edu — Queue: Array Implementation]
* [https://www.cs.usfca.edu/~galles/visualization/QueueLL.html www.cs.usfca.edu — Queue: Linked List Implementation]
Код:
* [https://github.com/indy256/codelibrary/blob/master/cpp/structures/queue_min.cpp indy256/codelibrary/cpp/structures/queue_min.cpp]
* [https://github.com/ADJA/algos/blob/master/DataStructures/QueueWithMinimum.cpp ADJA/algos/DataStructures/QueueWithMinimum.cpp]
* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/Queue.java kevin-wayne/algs4/Queue.java]
* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/LinkedQueue.java kevin-wayne/algs4/LinkedQueue.java]
* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/ResizingArrayQueue.java kevin-wayne/algs4/ResizingArrayQueue.java]
Задачи:
* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru &mdash; Курс &laquo;Структуры данных&raquo; &mdash; часть 1]
* [[:Категория:Задачи: Очередь|Задачи: Очередь]]
 
[[Category:Базовые структуры и абстрактные типы данных]]

Текущая версия от 15:21, 24 мая 2023

TLDR

Общие сведения

Очередь (англ. queue) — абстрактный контейнер, доступ к элементам которого организован по принципу «первым вошёл — первым вышел» (англ. FIFO, First In — First Out). Поведение элементов очереди напоминает обслуживание покупателей в магазине: каждый новый клиент встаёт в конец очереди и ожидает, когда уйдут все стоящие перед ним.

Для очереди вводятся два абстрактных понятия: хвост (конец) очереди — место, в которое происходит добавление элементов, и голова (начало) очереди — место, из которого происходит удаление элементов.

Интерфейс

Очередь предоставляет три основные операции:

void enqueue(T value) — вставка элемента value в очередь;
T dequeue() — извлечение элемента из очереди;
bool isEmpty() — проверка очереди на отсутствие элементов.

Все три метода должны иметь константное время работы (O(1)).

Демонстрация работы

Реализация на списке

Очередь можно реализовать на односвязном списке. Добавлять элементы в равной степени удобно как в начало списка, так и в конец (если имеется указатель на последний элемент), но в то же время удаление из конца списка реализуется сложнее, чем из начала (так как нужно иметь указатель на предпоследний элемент). Поэтому голова очереди будет располагаться в начале списка, а конец — в конце списка. На голову ссылается указатель Node *head, на хвост — Node *tail.

struct Node {
   int val;
   Node *next;
   Node(int v = 0, Node *n = NULL) {
       val = v;
       next = n;
   }
} *head, *tail;

В конструкторе очереди указатели на голову и хвост инициализируются значением NULL.

Queue() {
    head = tail = NULL;
}

Проверка на пустоту

Проверка очереди на пустоту (реализация на списке)

Если очередь не пуста, то указатели head и tail обязательно будут ссылаться на какие-то её элементы (возможно, что на один и тот же). Поэтому проверку на остутствие элементов в очереди можно производить с помощью любого из этих двух указателей:

bool isEmpty() {
    return head == NULL;
}

Вставка элемента

Вставка в очередь (реализация на списке)

Если до вставки элемента очередь пуста, то необходимо выполнить следующие операции:

  • Определение нового элемента списка и инициализация его поля val;
  • Так как единственный элемент будет являться и началом, и концом очереди, нужно направить на только что созданный элемент указатели head и tail.

Во всех остальных случаях добавление нового элемента подразумевает следующие действия:

  • Определение нового элемента списка и инициализация его поля val;
  • Новый элемент будет следовать за текущим конечным, поэтому на него будет указывать поле tail->next;
  • Так как новый элемент становится последним, на него теперь будет указывать tail.

Обратите внимание, как выполнение последних двух операций происходит с помощью цепочки присваиваний: сначала адрес нового элемента сохраняется в tail->next, а затем он же передаётся в сам tail.

void enqueue(int value) {
    if (head == NULL)
        head = tail = new Node(value, NULL);
    else
        tail = tail->next = new Node(value, NULL);
}

Извлечение элемента

Извлечение из очереди (реализация на списке)

Из пустой очереди нельзя удалить элемент, поэтому, как и в случае стека, такую ситуацию необходимо обрабатывать отдельно.

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

  • Требуется сохранить значение head->val во временной переменой для возможности последующего возврата;
  • Указатель на голову очереди нужно сместить на следующий элемент, но перед этим нужно сохранить во временной переменной предыдущий адрес, чтобы можно было освободить память;
  • Единственная разница в реализации заключается в том, что если очередь становится пустой, то требуется явно присвоить значение NULL указателю tail;
  • Далее можно освободить память и вернуть сохранённое ранее значение.
int dequeue() {
    if (head == NULL)
        /* обработка ошибки - нет элементов для извлечения */
    int v = head->val;
    Node *tmp = head;
    head = head->next;
    if (head == NULL)
        tail = NULL;
    delete tmp;
    return v;
}

Ниже приведён полный код реализации очереди на односвязном списке. Попытка извлечения из пустой очереди выявляется с помощью конструкции assert (заголовочный файл <assert.h> либо <cassert>).

class Queue {

    struct Node {
        int val;
        Node *next;
        Node(int v = 0, Node *n = NULL) {
            val = v;
            next = n;
        }
    } *head, *tail;

public:

    Queue() {
        head = tail = NULL;
    }

    void enqueue(int value) {
        if (head == NULL)
            head = tail = new Node(value, NULL);
        else
            tail = tail->next = new Node(value, NULL);
    }

    int dequeue() {
        assert(head != NULL);
        int v = head->val;
        Node *tmp = head;
        head = head->next;
        if (head == NULL)
            tail = NULL;
        delete tmp;
        return v;
    }

    bool isEmpty() {
        return head == NULL;
    }

};

Реализация на массиве

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

static const int MAX_SIZE = 100;
int a[MAX_SIZE];
int head, tail;

Queue() {
    head = tail = 0;
}

При реализации очереди на массиве определяются два индекса head и tail. При добавлении элемента он сохраняется в ячейку массива, на которую указывает tail, и затем tail смещается далее по массиву. При удалении элемента сдвигается уже индекс head, причём в том же направлении (смещение самих хранящихся элементов к началу массива невозможно по причине сложности O(N)).

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

Работа очереди на циклическом массиве

На иллюстрации показана работа очереди на массиве из 10 элементов. Производится бесконечный цикл из двух операций вставки и двух операций извлечения. Символом «xx» обозначены ячейки массива, которые в текущий момент не хранят элементы очереди (и фактические значения которых нам в данный момент безразличны).

Проверка на пустоту

Проверка очереди на пустоту (реализация на массиве)

Можно видеть, что в том случае, когда очередь не содержит элементов, индексы head и tail указывают на одну и ту же ячейку.

bool isEmpty() {
    return head == tail;
}

Вставка элемента

Вставка в очередь (реализация на массиве)

Новый элемент вставляется в то место, на которое указывает индекс tail. Сам индекс после вставки необходимо увеличить (по модулю длины массива, чтобы обеспечить цикличность). Нужно отслеживать переполнение очереди, признаком которого будет являться равенство значений head и tail после увеличения.

void push(int value) {
    if ((tail + 1) % MAX_SIZE == head)
        /* обработка ошибки - переполнение очереди */            
    a[tail] = value;
    tail = (tail + 1) % MAX_SIZE;
}

Извлечение элемента

Извлечение из очереди (реализация на массиве)

Удаление элемента требует только циклического увеличения индекса head. Должна быть предусмотрена проверка на удаление из пустой очереди.

int pop() {
    if (head == tail)
        /* обработка ошибки - нет элементов для извлечения */
    int tmp = head;
    head = (head + 1) % MAX_SIZE;
    return a[tmp];
}

Ниже приведён полный код реализации очереди на массиве. Переполнение и попытка извлечения из пустой очереди выявляются с помощью конструкции assert (заголовочный файл <assert.h> либо <cassert>).

class Queue {

    static const int MAX_SIZE = 100;
    int a[MAX_SIZE];
    int head, tail;

public:

    Queue() {
        head = tail = 0;
    }

    void enqueue(int value) {
        assert((tail + 1) % MAX_SIZE != head);
        a[tail] = value;
        tail = (tail + 1) % MAX_SIZE;
    }

    int dequeue() {
        assert(head != tail);
        int tmp = head;
        head = (head + 1) % MAX_SIZE;
        return a[tmp];
    }

    bool isEmpty() {
        return head == tail;
    }

};

Очередь в STL

В стандартной библиотеке шаблонов C++ присутствует шаблон queue<T>. Для возможности его использования требуется подключить заголовочный файл <queue> и пространство имён std:

#include <iostream>
#include <queue>
using namespace std;
int main() {
    queue<int> q;
    for (int i = 1; i < 6; i++)
        q.push(i);
    while (!s.empty()) {
        cout << q.front() << ' ';
        q.pop();
    }            
    return 0;       //результат "1 2 3 4 5 "
}

STL предоставляет следующий набор методов для очереди:

queue<T>() — конструктор;
void push(const T& x) — добавление элемента;
void pop() — удаление элемента. Обратите внимание на то, что значение удаляемого элемента не возвращается;
T& front() — получение значения элемента в голове очереди. Этот метод не производит удаление элемента;
T& back() — получение значения элемента в хвосте очереди. Этот метод не производит удаление элемента;
bool empty() — проверка на пустоту;
size_t size() — получение количества элементов в очереди. Метод возвращает беззнаковое целое число.

Дек

Дек (англ. deque, double-ended queue) — тип, представляющий двустороннюю очередь, оба конца которой могут принимать и возвращать элементы. Интерфейс дека похож на интерфейс очереди, но содержит по паре методов вставки и удаления (для начала и конца двусторонней очереди). Дек естественным образом реализуется на двусвязном списке или на массиве.

В стандартной библиотеке шаблонов C++ шаблон std::deque<T>, объявленный в заголовочном файле <deque>, является базой для шаблонов стека и очереди и поддерживает значительно более широкий набор операций по сравнению с ними (в том числе доступ к элементам с помощью метода at() или оператора [], вставки значения в любую позицию с помощью метода insert(), доступ к итераторам и т. д.). Вставка элементов в дек STL производится с помощью методов push_front() и push_back(), удаление — с помощью pop_front() и pop_back().

Ссылки

Теория:

Демонстрация:

Код:

Задачи: