25 ноября 2021

Очередь

Структура данных очередь - это разновидность упорядоченного контейнера (т.е. контейнера, элементы которого распотожены в определенном порядке). Новые элементы добавляются в начало, а удаление элементов происходит с конца (first in first out, FIFO). Название этой структуры даннх подсказывает аналогию, например, с очередью покупателей в магазине, которая устроена по тому же принципу. Очередь должна выполнять операции добавления и удаления эффективно, т.е. за определенное количество операций, которое (в среднем) не должно записеть от количества элементов в очереди.

Очередь используется во многих приложениях. Например:

• Алгоритм обхода вершин графа в ширину (breadth first search, BFS)
• Самые разные очереди заданий (в операционной системе, задания на печать для принтера, очередь для передачи пакетов по сети и т.п.)

Реализация очередь на языке Си - не такая очевидная, как в случае со стеком (свойства которого хорошо согласованы с динамическим массивом). Рассмотрим две идеи реализации очереди.

Очередь на основе связного списка

Связный список - это готовая реализация очереди. Действительно. Вспомним структуры данных и функции, которые мы написали для реализации списка:

struct List {
    int value;
    struct List *next;
};
typedef struct List List;

typedef struct {
    size_t size;
    List* head;
    List* tail;
} LinkedList;

// Создание пустого списка
List list_init();

// Удаление первого элемента и возвращение его значения
int list_pop_front(LinkedList* l);

// Вставка элемента в конец списка
void list_push_back(LinkedList* l, int value);

Этого достаточно для того, чтобы реализовать функциональность очереди:

// Определим для наглядности псевдоним
typedef LinkedList Queue;

// Создание пустой очереди
Queue queue_init();

// Добавление значения в очередь
void enqueue(Queue* q, int value);

// Удаление значения из очереди
int dequeue(Queue* q);

При корректной реализации всех функций следующая программа должна работать:

int main() {
    Queue q = queue_init();
    for (int i = 1; i < 10; ++i) enqueue(&q, i * i);
    for (int i = 1; i < 10; ++i) printf("%d ", dequeue(&q));
    putchar('\n');
    return 0;
}

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

1 4 9 16 25 36 49 64 81

Очередь на основе двух стеков

Существует остроумный способоб реализации очереди на основе двух стеков. Напомним, что наше основное условие - добиться эффективного добавления и удаления элементов очереди. Заведем два стека s1 и s2.

typedef struct {
    Stack s1;
    Stack s2;
} Queue;

Добавлять новый элемент всегда будем в стек s1. Операция удаления элемента выполняется в два этапа:

1. Если стек s2 пустой, то перекладываем все элементы из s1 в s2.
2. Выполняем функцию pop_stack для s2.

Может показаться, что удаление элемента не является эффективной операцией из-за первого шага. Эффективность удаления легко показать, проследив за перемещением элемента в этой структуре данных. Каждый элемент будет добавлен в s1, перемещен в s2 и удален оттуда. Это набор операций, который не зависит от размера контейнера, а это значит, что мы достигли цели.

При корректной реализации очереди с помощью двух стеков пример функции main из предыдущего пункта должен работать аналогично.

Упражнение 1. Выполните обе предложенные реализации очереди и сравните их производительность. Можно ли заранее понять какая из реализаций работает быстрее?