Как работает очередь в программировании

Очередь

Очередь (англ. queue) — это структура данных, добавление и удаление элементов в которой происходит путём операций [math] \mathtt [/math] и [math] \mathtt [/math] соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. first-in, first-out — FIFO). У очереди имеется голова (англ. head) и хвост (англ. tail). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове. Очередь поддерживает следующие операции:

• [math] \mathtt [/math] — проверка очереди на наличие в ней элементов,
• [math] \mathtt [/math] (запись в очередь) — операция вставки нового элемента,
• [math] \mathtt [/math] (снятие с очереди) — операция удаления нового элемента,
• [math] \mathtt [/math] — операция получения количества элементов в очереди.

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

Очередь, способную вместить не более [math]\mathtt[/math] элементов, можно реализовать с помощью массива [math]\mathtt[/math] . Она будет обладать следующими полями:

• [math]\mathtt[/math] — голова очереди,
• [math]\mathtt[/math] — хвост очереди.

empty

boolean empty(): return head == tail

push

function push(x : T): if (size() != n) elements[tail] = x tail = (tail + 1) % n

pop

T pop(): if (empty()) return null x = elements[head] head = (head + 1) % n return x

size

int size() if head > tail return n - head + tail else return tail - head

Из-за того что нам не нужно снова выделять память, каждая операция выполняется за [math]O(1)[/math] времени.

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

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

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

Для данной реализации очереди необходимо создать список [math]list[/math] и операции работы на созданном списке.

Реализация очереди на односвязном списке:

List

• ListItem(data : T, next : ListItem) — конструктор,
• [math]\mathtt[/math] — поле, в котором хранится значение элемента,
• [math]\mathtt[/math] — указатель на следующий элемент очереди.

push

function push(x : T): element = tail tail = ListItem(x, NULL) if size == 0 head = tail else element.next = tail size++

pop

T pop(): size-- element = head head = head.next return element

empty

boolean empty(): return head == tail

• каждая операция выполняется за время [math]O(1)[/math] .

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

Реализация на двух стеках

Очередь можно реализовать на двух стеках [math]\mathtt[/math] и [math]\mathtt[/math] . Поступим следующим образом: [math]\mathtt[/math] будем использовать для операции [math] \mathtt [/math] , [math]\mathtt[/math] для операции [math] \mathtt [/math] . При этом, если при попытке извлечения элемента из [math]\mathtt[/math] он оказался пустым, просто перенесем все элементы из [math]\mathtt[/math] в него (при этом элементы в [math]\mathtt[/math] получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а [math]\mathtt[/math] станет пустым).

• [math] \mathtt [/math] и [math] \mathtt [/math] — функции, реализующие операцию [math] \mathtt [/math] для соответствующего стека,
• [math] \mathtt [/math] и [math] \mathtt [/math] — аналогично операции [math] \mathtt [/math] .

push

function push(x : T): pushLeft(x)

pop

T pop(): if not rightStack.empty() return popRight() else while not leftStack.empty() pushRight(popLeft()) return popRight()

При выполнении операции [math] \mathtt [/math] будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию [math] \mathtt [/math] из первого стека, третью во второй стек на финальный [math] \mathtt [/math] . Тогда для операций [math] \mathtt [/math] учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции [math] \mathtt [/math] .

Таким образом, для каждой операции требуется [math]O(1)[/math] монет, а значит, амортизационная стоимость операций [math]O(1)[/math] .

• эту реализацию несложно модифицировать для получения минимума в текущей очереди за [math]O(1)[/math] .

• если [math]\mathtt[/math] не пуст, то операция [math] \mathtt [/math] может выполняться [math]O(n)[/math] времени, в отличие от других реализаций, где [math] \mathtt [/math] всегда выполняется за [math]O(1)[/math] .

Реализация на шести стеках

Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим [math]O(n)[/math] времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с [math]O(1)[/math] истинного времени на операцию.

Подробное описание в статье Персистентная очередь.

Отличия от других реализаций

• [math]O(1)[/math] реального времени на операцию,
• возможность дальнейшего улучшения до персистентной очереди, если использовать персистентные стеки.

• дольше в среднем выполняются операции,
• больше расход памяти,
• большая сложность реализации.

См. также

Источники информации

• Википедия — Очередь (программирование)
• Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
• T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1, p. 262
• Hood R., Melville R. Real Time Queue Operations in Pure LISP. — Cornell University, 1980

Алгоритмы и структуры данных для начинающих: стеки и очереди

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

Стек

Стек — это коллекция, элементы которой получают по принципу «последний вошел, первый вышел» (Last-In-First-Out или LIFO). Это значит, что мы будем иметь доступ только к последнему добавленному элементу.

В отличие от списков, мы не можем получить доступ к произвольному элементу стека. Мы можем только добавлять или удалять элементы с помощью специальных методов. У стека нет также метода Contains , как у списков. Кроме того, у стека нет итератора. Для того, чтобы понимать, почему на стек накладываются такие ограничения, давайте посмотрим на то, как он работает и как используется.

Наиболее часто встречающаяся аналогия для объяснения стека — стопка тарелок. Вне зависимости от того, сколько тарелок в стопке, мы всегда можем снять верхнюю. Чистые тарелки точно так же кладутся на верх стопки, и мы всегда будем первой брать ту тарелку, которая была положена последней.

Если мы положим, например, красную тарелку, затем синюю, а затем зеленую, то сначала надо будет снять зеленую, потом синюю, и, наконец, красную. Главное, что надо запомнить — тарелки всегда ставятся и на верх стопки. Когда кто-то берет тарелку, он также снимает ее сверху. Получается, что тарелки разбираются в порядке, обратном тому, в котором ставились.

Теперь, когда мы понимаем, как работает стек, введем несколько терминов. Операция добавления элемента на стек называется «push», удаления — «pop». Последний добавленный элемент называется верхушкой стека, или «top», и его можно посмотреть с помощью операции «peek». Давайте теперь посмотрим на заготовку класса, реализующего стек.

Класс Stack

Класс Stack определяет методы Push , Pop , Peek для доступа к элементам и поле Count . В реализации мы будем использовать LinkedList для хранения элементов.

public class Stack < LinkedList _items = new LinkedList(); public void Push(T value) < throw new NotImplementedException(); >public T Pop() < throw new NotImplementedException(); >public T Peek() < throw new NotImplementedException(); >public int Count < get; >> 

Метод Push

• Поведение: Добавляет элемент на вершину стека.
• Сложность: O(1).

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

public void Push(T value)

Метод Pop

• Поведение: Удаляет элемент с вершины стека и возвращает его. Если стек пустой, кидает InvalidOperationException .
• Сложность: O(1).

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

public T Pop() < if (_items.Count == 0) < throw new InvalidOperationException("The stack is empty"); >T result = _items.Tail.Value; _items.RemoveLast(); return result; > 

Метод Peek

• Поведение: Возвращает верхний элемент стека, но не удаляет его. Если стек пустой, кидает InvalidOperationException .
• Сложность: O(1).

public T Peek() < if (_items.Count == 0) < throw new InvalidOperationException("The stack is empty"); >return _items.Tail.Value; > 

Метод Count

• Поведение: Возвращает количество элементов в стеке.
• Сложность: O(1).

Зачем нам знать, сколько элементов находится в стеке, если мы все равно не имеем к ним доступа? С помощью этого поля мы можем проверить, есть ли элементы на стеке или он пуст. Это очень полезно, учитывая, что метод Pop кидает исключение.

public int Count < get < return _items.Count; >> 

Пример: калькулятор в обратной польской записи

Классический пример использования стека — калькулятор в обратной польской, или постфиксной, записи. В ней оператор записывается после своих операндов. То есть, мы пишем:

Другими словами, вместо «4 + 2» мы запишем «4 2 +». Если вам интересно происхождение обратной польской записи и ее названия, вы можете узнать об этом на Википедии или в поисковике.

То, как вычисляется обратная польская запись и почему стек так полезен при ее использовании, хорошо видно из следующего алгоритма:

for each input value if the value is an integer push the value on to the operand stack else if the value is an operator pop the left and right values from the stack evaluate the operator push the result on to the stack pop answer from stack. 

То есть, для выражения «4 2 +» действия будут следующие:

push(4) push(2) push(pop() + pop()) 

В конце на стеке окажется одно значение — 6.

Далее приводится полный код простого калькулятора, который считывает выражение (например, 4 2 + ) из консоли, разбивает входные данные по пробелам ( [«4», «2», «+»] ) и выполняет алгоритм вычисления. Вычисление продолжается до тех пор, пока не будет встречено слово quit .

void RpnLoop() < while (true) < Console.Write(">"); string input = Console.ReadLine(); if (input.Trim().ToLower() == "quit") < break; >// Стек еще не обработанных значений. Stack values = new Stack(); foreach (string token in input.Split(new char[] < ' ' >)) < // Если значение - целое число. int value; if (int.TryParse(token, out value)) < // . положить его на стек. values.Push(value); >else < // в противном случае выполнить операцию. int rhs = values.Pop(); int lhs = values.Pop(); // . и положить результат обратно. switch (token) < case "+": values.Push(lhs + rhs); break; case "-": values.Push(lhs - rhs); break; case "*": values.Push(lhs * rhs); break; case "/": values.Push(lhs / rhs); break; case "%": values.Push(lhs % rhs); break; default: // Если операция не +, -, * или / throw new ArgumentException( string.Format("Unrecognized token: ", token)); > > > // Последний элемент на стеке и есть результат. Console.WriteLine(values.Pop()); > > 

Очередь

Очереди очень похожи на стеки. Они также не дают доступа к произвольному элементу, но, в отличие от стека, элементы кладутся (enqueue) и забираются (dequeue) с разных концов. Такой метод называется «первый вошел, первый вышел» (First-In-First-Out или FIFO). То есть забирать элементы из очереди мы будем в том же порядке, что и клали. Как реальная очередь или конвейер.

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

Класс Queue

Класс Queue , как и стек, будет реализован с помощью связного списка. Он будет предоставлять методы Enqueue для добавления элемента, Dequeue для удаления, Peek и Count . Как и класс Stack , он не будет реализовывать интерфейс ICollection , поскольку это коллекции специального назначения.

public class Queue < LinkedList _items = new LinkedList(); public void Enqueue(T value) < throw new NotImplementedException(); >public T Dequeue() < throw new NotImplementedException(); >public T Peek() < throw new NotImplementedException(); >public int Count < get; >> 

Метод Enqueue

• Поведение: Добавляет элемент в очередь.
• Сложность: O(1).

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

Public void Enqueue(T value)

Метод Dequeue

• Поведение: Удаляет первый помещенный элемент из очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

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

public T Dequeue() < if (_items.Count == 0) < throw new InvalidOperationException("The queue is empty"); >T last = _items.Tail.Value; _items.RemoveLast(); return last; > 

Метод Peek

• Поведение: Возвращает элемент, который вернет следующий вызов метода Dequeue . Очередь остается без изменений. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T Peek() < if (_items.Count == 0) < throw new InvalidOperationException("The queue is empty"); >return _items.Tail.Value; > 

Метод Count

• Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
• Сложность: O(1).

public int Count < get < return _items.Count; >> 

Двусторонняя очередь

Двусторонняя очередь (Double-ended queue), или дек (Deque), расширяет поведение очереди. В дек можно добавлять или удалять элементы как с начала, так и с конца очереди. Такое поведение полезно во многих задачах, например, планирование выполнения потоков или реализация других структур данных. Позже мы рассмотрим вариант реализации стека с помощью двусторонней очереди.

Класс Deque

Класс Deque проще всего реализовать с помощью двусвязного списка. Он позволяет просматривать, удалять и добавлять элементы в начало и в конец списка. Основное отличие двусторонней очереди от обычной — методы Enqueue , Dequeue , и Peek разделены на пары для работы с обоими концами списка.

public class Deque < LinkedList _items = new LinkedList(); public void EnqueueFirst(T value) < throw new NotImplementedException(); >public void EnqueueLast(T value) < throw new NotImplementedException(); >public T DequeueFirst() < throw new NotImplementedException(); >public T DequeueLast() < throw new NotImplementedException(); >public T PeekFirst() < throw new NotImplementedException(); >public T PeekLast() < throw new NotImplementedException(); >public int Count < get; >> 

Метод EnqueueFirst

• Поведение: Добавляет элемент в начало очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueFirst .
• Сложность: O(1).

public void EnqueueFirst(T value)

Метод EnqueueLast

• Поведение: Добавляет элемент в конец очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueLast .
• Сложность: O(1).

public void EnqueueLast(T value)

Метод DequeueFirst

• Поведение: Удаляет элемент из начала очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T DequeueFirst() < if (_items.Count == 0) < throw new InvalidOperationException("DequeueFirst called when deque is empty"); >T temp = _items.Head.Value; _items.RemoveFirst(); return temp; > 

Метод DequeueLast

• Поведение: Удаляет элемент с конца очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T DequeueLast() < if (_items.Count == 0) < throw new InvalidOperationException("DequeueLast called when deque is empty"); >T temp = _items.Tail.Value; _items.RemoveLast(); return temp; > 

Метод PeekFirst

• Поведение: Возвращает элемент из начала очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T PeekFirst() < if (_items.Count == 0) < throw new InvalidOperationException("PeekFirst called when deque is empty"); >return _items.Head.Value; > 

Метод PeekLast

• Поведение: Возвращает элемент с конца очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T PeekLast() < if (_items.Count == 0) < throw new InvalidOperationException("PeekLast called when deque is empty"); >return _items.Tail.Value; > 

Метод Count

• Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
• Сложность: O(1).

public int Count < get < return _items.Count; >> 

Пример: реализация стека

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

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

Тем не менее, реализация стека или очереди с помощью массива — непростая задача, но такая реализация двусторонней очереди и использование ее в качестве основы для других структур данных даст нам серьезный плюс к производительности и позволит повторно использовать код. Это снижает стоимость поддержки.

Позже мы посмотрим на вариант очереди с использованием массива, но сначала давайте взглянем на класс стека с использованием двусторонней очереди:

public class Stack < Deque _items = new Deque(); public void Push(T value) < _items.EnqueueFirst(value); >public T Pop() < return _items.DequeueFirst(); >public T Peek() < return _items.PeekFirst(); >public int Count < get < return _items.Count; >> > 

Заметьте, что вся обработка ошибок теперь лежит на классе Deque , и, кроме того, любая оптимизация очереди также отразится на стеке. Реализация обычной очереди на основе двусторонней настолько проста, что мы оставим ее читателю в качестве упражнения.

Хранение элементов в массиве

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

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

При создании очереди у нее внутри создается массив нулевой длины. Красные буквы «h» и «t» означают указатели _head и _tail соответственно.

Deque deq = new Deque(); deq.EnqueueFirst(1); 

Добавляем элемент в начало

deq.EnqueueLast(2); 

Добавляем элемент в конец

deq.EnqueueFirst(0); 

Добавляем еще один элемент в начало

Обратите внимание: индекс «головы» очереди перескочил в начало списка. Теперь первый элемент, который будет возвращен при вызове метода DequeueFirst — 0 (индекс 3).

deq.EnqueueLast(3); 

И еще один в конец

Массив заполнен, поэтому при добавлении элемента произойдет следующее:

• Алгорим роста определит размер нового массива.
• Элементы скопируются в новый массив с «головы» до «хвоста».
• Добавится новый элемент.

deq.EnqueueLast(4); 

Добавляем значение в конец расширенного массива

Теперь посмотрим, что происходит при удалении элемента:

deq.DequeueFirst(); 

Удаляем элемент из начала

deq.DequeueLast(); 

Удаляем элемент с конца

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

Теперь давайте посмотрим на реализацию.

Класс Deque (с использованием массива)

Интерфейс очереди на основе массива такой же, как и в случае реализации через связный список. Мы не будем его повторять. Однако, поскольку список был заменен на массив, у нас добавились новые поля — сам массив, его размер и указатели на «хвост» и «голову» очереди.

public class Deque < T[] _items = new T[0]; // Количество элементов в очереди. int _size = 0; // Индекс первого (самого старого) элемента. int _head = 0; // Индекс последнего (самого нового) элемента. int _tail = -1; . > 

Алгоритм роста

Когда свободное место во внутреннем массиве заканчивается, его необходимо увеличить, скопировать элементы и обновить указатели на «хвост» и «голову». Эта операция производится при необходимости во время добавления элемента. Параметр startingIndex используется, чтобы показать, сколько полей в начале необходимо оставить пустыми (в случае добавления в начало).

Обратите внимание на то, как извлекаются данные, когда приходится переходить в начало массива при проходе от «головы» к «хвосту».

private void allocateNewArray(int startingIndex) < int newLength = (_size == 0) ? 4 : _size * 2; T[] newArray = new T[newLength]; if (_size >0) < int targetIndex = startingIndex; // Копируем содержимое. // Если массив не закольцован, просто копируем элементы. // В противном случае, копирует от head до конца, // а затем от начала массива до tail. // Если tail меньше, чем head, переходим в начало. if (_tail < _head) < // Копируем _items[head].._items[end] в newArray[0]..newArray[N]. for (int index = _head; index < _items.Length; index++) < newArray[targetIndex] = _items[index]; targetIndex++; >// Копируем _items[0].._items[tail] в newArray[N+1].. for (int index = 0; index > else < // Копируем _items[head].._items[tail] в newArray[0]..newArray[N] for (int index = _head; index > _head = startingIndex; _tail = targetIndex - 1; > else < // Массив пуст. _head = 0; _tail = -1; >_items = newArray; > 

Метод EnqueueFirst

• Поведение: Добавляет элемент в начало очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueFirst .
• Сложность: O(1) в большинстве случаев; O(n), когда нужно расширение массива.

public void EnqueueFirst(T item) < // Проверим, необходимо ли увеличение массива: if (_items.Length == _size) < allocateNewArray(1); >// Так как массив не заполнен и _head больше 0, // мы знаем, что есть место в начале массива. if (_head > 0) < _head--; >else < // В противном случае мы должны закольцеваться. _head = _items.Length - 1; >_items[_head] = item; _size++; if (_size == 1) < // Если мы добавили первый элемент в пустую // очередь, он же будет и последним, поэтому // нужно обновить и _tail. _tail = _head; >> 

Метод EnqueueLast

• Поведение: Добавляет элемент в конец очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueLast .
• Сложность: O(1) в большинстве случаев; O(n), когда нужно расширение массива.

public void EnqueueLast(T item) < // Проверим, необходимо ли увеличение массива: if (_items.Length == _size) < allocateNewArray(0); >// Теперь, когда у нас есть подходящий массив, // если _tail в конце массива, нам надо перейти в начало. if (_tail == _items.Length - 1) < _tail = 0; >else < _tail++; >_items[_tail] = item; _size++; if (_size == 1) < // Если мы добавили последний элемент в пустую // очередь, он же будет и первым, поэтому // нужно обновить и _head. _head = _tail; >> 

Метод DequeueFirst

• Поведение: Удаляет элемент с начала очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T DequeueFirst() < if (_size == 0) < throw new InvalidOperationException("The deque is empty"); >T value = _items[_head]; if (_head == _items.Length - 1) < // Если head установлен на последнем индексе, // переходим к началу массива. _head = 0; >else < // Переходим к следующему элементу. _head++; >_size--; return value; > 

Метод DequeueLast

• Поведение: Удаляет элемент с конца очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T DequeueLast() < if (_size == 0) < throw new InvalidOperationException("The deque is empty"); >T value = _items[_tail]; if (_tail == 0) < // Если tail установлен на начало массива, переходим к концу. _tail = _items.Length - 1; >else < // Переходим к предыдущему элементу. _tail--; >_size--; return value; > 

Метод PeekFirst

• Поведение: Возвращает элемент с начала очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T PeekFirst() < if (_size == 0) < throw new InvalidOperationException("The deque is empty"); >return _items[_head]; > 

Метод PeekLast

• Поведение: Возвращает элемент с конца очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T PeekLast() < if (_size == 0) < throw new InvalidOperationException("The deque is empty"); >return _items[_tail]; > 

Метод Count

• Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
• Сложность: O(1).

public int Count < get < return _size; >> 

Продолжение следует

Вот мы и закончили четвертую часть нашего цикла статей. В ней мы рассмотрели стеки и очереди. В следующий раз мы перейдем к бинарным деревьям поиска.
Перевод статьи «Stacks and Queues»

Очереди в программировании. Просто о сложном

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

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

Если, при загрузке, пользователь выберет одно, или два изображения, то он не будет ждать слишком долгого окончания загрузки и ответ сервера будет достаточно комфортным. Но, представьте, что случится, если пользователь попытается загрузить целую папку из 10, а то и 30 картинок. То мало того, что он будет ждать, пока все превьюхи сгенерируются, так ещё, и при единственной ошибке, загружать всё придётся по-новому.

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

Синхронная загрузка в этом случае — это не лучшее решение. Потому как, из него вытекают последствия в виде долгой загрузки страницы, и прерывание обработки при закрытии страницы. Вместо этого, пользователю можно позволить загрузить множество картинок, а создание их превьюшек делать уже отдельно, в фоне. Пример повседневного применения очереди:
youtube — при загрузке личного видео, оно становится доступным только через какое-то время, т.е. когда обработается в фоне;
vk — при загрузке песни, или видео, аналогично, становится доступным не сразу после загрузки, а только после обработки.

Жизненный цикл загрузки файлов без очереди

Обычный процесс загрузки выглядит так:

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

• Пользователь отменит загрузку, закрыв вкладку
• Пользователю надоест ожидать долгую работу скрипта, и он отменит загрузку
• Соединение будет разорвано браузером по таймауту

И при любой из этих ошибок, пользователь будет необходимо повторить загрузку заново. А, поверьте мне, не каждый пользователь вытерпит загрузку изображений в виде лотереи, и уйдёт с вашего сайта после первой-второй такой ошибки.
Не исключая и благоприятный исход, пользователь будет продолжать пользоваться вашим сервисом, так что это тоже имеет право на жизнь.

PHP + очередь

Что же, а как тогда будет выглядеть схема работы PHP с очередью? Просто:

Из картинки можно увидеть, что там изображено 3 очереди, каждая из которых работает отдельно над своей задачей: обработка изображений , видео , и отправка email писем .

Как только пользователь завершает загрузку изображений, в очередь добавляется новая задача, и выполняется. Воркер очереди картинок видит новую задачу, и начинает генерировать их превью.

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

Воркер обрабатывает задачи настолько быстро, насколько это возможно. Если будет загружено 5 картинок, то задача будет выполнена быстро, если 1000, то это займёт какое-то время. Но, зато, теперь пользователь это время обработки может потратить более полезно, чем при стандартном решении.

В результате, по завершению работы, воркер может сразу же оповестить пользователей. Каким способом отправлять уведомления — это всё на ваш выбор. Можете оповещать по вебсокетам, по email, или обычные оповещения после перезагрузки страницы.

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

Больше очередей

Более того, вы можете создавать целую цепочку очередей. К примеру, изнутри самой очереди обработки картинок, вы можете добавить новую задачу в очередь на отправку email письма.

Это вы можете увидеть на примере предыдущей картинки, немного видоизменённой:

Здесь показано, что, как только воркер завершит свою работу, будет создана новая задача по отправке письма, в другой очереди. В свою очередь, email-воркер уже отрабатывает, и оповещает пользователя о завершении работы над изображениями.

До сих пор непонятно?

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

1. Кто-то принимает ваш заказ, и начинает готовить пиццу (добавляя нужные ингредиенты, соусы, и т.д.)
2. Запаковывает в коробку, и едет по адресной доставке.
3. На месте, вы уже расплачиваетесь с курьером, и получаете свою пиццу.

Представьте, насколько долгим будет этот процесс, если только один работник будет выполнять все задачи. Конечно, если у него только один заказ в день, то звучит не так плохо. Но что случится, если он получит 5 заказов течении одной минуты? Очевидно, что сил одного тут будет слишком мало, и этот работник будет перегружен.

В результате, некоторые из заказов могут потеряться, в некоторых могут несоответствовать ингредиенты тем, что заказывали. Или, когда доставка производится в 5 разных мест, они могут находиться слишком далеко друг от друга, что повлечёт за собой опоздание курьера, и еда клиентов станет холодной.

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

1. Один человек ждёт входящие звонки, и принимает заказы
2. Второй готовит пиццу
3. И третий осуществляет доставку пиццы по адресу

И в итоге, когда каждый имеет чёткие обязанности, и занят только одним делом, то меньше вероятность ошибки, и процесс создания продукта является более оптимизированным.

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

Резюме

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

В серці. Назавжди.

Вчора у мене помер однокласник. А сьогодні бабуся. І хто б міг уявити, що цей рік принесе війну, смерть товариша, та смерть члена сім’ї? Це боляче. Проте це добре нагадування про те, як швидко тече час. І як його ціна збільшується кожної марно витраченої секунди. І я не скажу щось

20 мая 2022 г. 1 min read

Ось такий він, руський мир

«Руський мир» — звучить дуже сильно та виправдовуюче. Гарна обгортка виправдання слабкості, аморальності та нікчемності своїх дійсних намірів. Руський мир, який дуже солодко звучить для всіх, хто хоче закрити очі на факт повномасштабної війни. Дуже добре виправдання вбивства для купки звірів. Втім, це ж росія, в якій все виглядає логічно

16 апр. 2022 г. 3 min read

Перехват запросов и ответов JavaScript Fetch API

Перехватчики — это блоки кода, которые вы можете использовать для предварительной или последующей обработки HTTP-вызовов, помогая в обработке глобальных ошибок, аутентификации, логирования, изменения тела запроса и многом другом. В этой статье вы узнаете, как перехватывать вызовы JavaScript Fetch API. Есть два типа событий, для которых вы можете захотеть перехватить HTTP-вызовы:

Информатика. 10 класс (Повышенный уровень)

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

Различные виды структур данных подходят для различных задач; некоторые из них имеют узкую специализацию, другие являются универсальными (пример 21.1).

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

Ни одна профессиональная программа сегодня не пишется без использования структур данных, поэтому многие из них содержатся в стандартных библиотеках современных языков программирования (например, STL для С++).

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

Структуры данных классифицируют по разным признакам. В примере 21.2 приведена классификация структур данных по организации взаимосвязей между элементами.

Пример 21.1. Примеры некоторых структур данных:

1. Массив (вектор в C++) — самая простая и широко используемая структура данных.

2. Запись (структура в С++) — совокупность элементов данных разного типа. Содержит постоянное количество элементов, которые называют полями.

3. Связный список (Linked List) представляет набор связанных узлов, каждый из которых хранит собственно данные и ссылку на следующий узел. В реальной жизни связный список можно представить в виде поезда, каждый вагон которого может содержать некоторый груз или пассажиров и при этом может быть связан с другим вагоном.

4. Граф — совокупность вершин (узлов) и связей между ними (ребер). В реальной жизни по такому принципу устроены социальные сети: узлы — это люди, а ребра — их отношения.

5. Множество — совокупность данных, значения которых не повторяются, реализация математического объекта множество, за исключением того, что множество в программировании конечно.

Пример 21.2. Классификация структур данных.

• • массив;
  • список;
  • связанный список;
  • стек;
  • очередь;
  • хэш-таблица.

  • Иерархические:

  • • двоичные деревья;
    • n-арные деревья;
    • иерархический список.
    • • неориентированный граф;
      • ориентированный граф.
      • • таблица реляционной базы данных;
        • двумерный массив.
        Похожие публикации:

        1. Mobilesync что это за папка
        2. Mrr sha 256 что это
        3. Как посмотреть свои комментарии в тик ток
        4. Как умножать на не целое число