Какая структура данных описывается как fifo
Перейти к содержимому

Какая структура данных описывается как fifo

  • автор:

Очереди типов FIFO и LIFO

Мы продолжаем изучение структур данных. На этом занятии познакомимся с еще одним способом организации данных – очередями.

Само слово очередь (по англ. queue) сразу ассоциируется с очередью в магазин за каким-нибудь долгожданным или дефицитным продуктом:

Здесь тот, кто первым пришел (First In), тот первым и покидает очередь (First Out). Именно поэтому такой тип очереди получил сокращенное название FIFO. То есть, в такой структуре данные добавляются в конец очереди, а извлекаются из начала.

Где может быть полезна такая организация данных? Распространенный пример – буфер приема или передачи какого-либо устройства:

Здесь вновь поступающие данные добавляются в конец очереди, а извлекаются (читаются) из начала очереди.

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

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

Но это первый тип очереди, который, как мы уже знаем, носит название FIFO. Есть еще один тип очереди под названием:

LIFO (Last In, First Out)

Что это за очередь? Представьте себе ящик, в который складываются разные вещи:

А вынимать их можно только сверху. В результате, последняя положенная вещь будет извлечена первой, вторая – второй и так до последней. Получаем очередь типа LFIO: последний зашел, первый вышел.

Классический пример использования этого типа очереди – организация стеков вызова функций в программах. Пусть имеется вот такая простая программа на языке Python, в которой последовательно вызываются три функции: сначала main, затем show_sum и последней print:

def show_sum(a, b): print(a+b) def main(): show_sum ()

Чтобы интерпретатор «знал» в какой последовательности функции были вызваны и в какой последовательности продолжать их выполнять, после завершения очередной, формируется очередь по принципу LIFO: последняя вызванная функция должна первой и завершаться, затем, вторая и, наконец, третья.

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

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

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

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

deque (сокращение от double ended queue)

То есть, очереди часто представляют собой обычные двусвязные списки. В результате, чтобы организовать очередь типа FIFO нам достаточно добавлять новые элементы в начало списка, а извлекать с конца. Это делается с помощью уже знакомых нам методов push_front() и pop_back(). А для очереди типа LIFO можно использовать методы push_front() и pop_front(). Кстати, можно заметить, что тот же эффект достигается, если мы будем конец списка считать началом, а начало – концом. Тогда очередь FIFO будет строиться методами push_back() и pop_front(), а очередь LIFO методами push_back() и pop_back(). Принципиальной разницы в их функционировании при этом не будет.

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

Благодаря такому подходу доступ к отдельным промежуточным элементам осуществляется несколько быстрее, чем в случае с обычными связными списками. В частности, по такой схеме реализована очередь deque в стандартной библиотеке шаблонов STL языка C++. Недостатком такой структуры является более медленный алгоритм вставки новых элементов в начало этого модифицированного списка, т.к. приходится сдвигать ранее записанные элементы массива первого объекта списка.

Очередь, как абстрактная структура данных

Вообще, очереди можно реализовывать не только на базе связных списков, но, например, и динамического массива. Тогда для типа FIFO нам придется при добавлении нового элемента в начало сдвигать все остальные элементы массива, что вычислительно несколько дольше – O(n) операций (вместо O(1) для связных списков). Да и операции добавления новых элементов в конец динамического массива требуют большего числа операций, чем у связных списков. Поэтому динамический массив для очередей, в общем случае, не лучший выбор. Хотя, в некоторых частных задачах, возможно, это будет иметь смысл.

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

На следующих занятиях мы увидим, как реализуются очереди на языках программирования С++ и Python.

Видео по теме

#1. О большое (Big O) — верхняя оценка сложности алгоритмов

Очередь

Fifo new.png

Очередь (англ. 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

Queue.png

  • каждая операция выполняется за время [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

Очередь и стек — Основы алгоритмов и структур данных

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

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

Польский математик Ян Лукасевич около ста лет назад предложил необычный способ записи выражений, в котором не нужны ни приоритеты операций, ни скобки. Сейчас этот способ называют обратной польской записью.

Обратная запись непривычна и не получила широкого распространения, но ее можно встретить в таких языках программирования, как Forth и PostScript.

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

  • Обычная запись — , обратная —
  • Обычная запись — , обратная —

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

можно записать так:

Эта запись читается слева направо и воспринимается так:

  • Число
  • Число
  • Операция сложения
  • Число
  • Число
  • Операция сложения
  • Операция умножения

Преимущество обратных выражений в том, что они не вызывают разночтения.

Чтобы разобраться на примере, дальше мы пошагово вычислим это выражение:

Шаг 1. Берем из стопки два верхних числа —

. Выполняем над ними первую операцию — сложение:

Шаг 2. Идем дальше по выражению — нужно взять следующие два значения и второй оператор. Берем эти значения и применяем к ним вторую операцию сложения:

Шаг 3. Вспомним изначальное выражение:

Мы провели две операции сложения. Оставим только умножение и запишем в выражение результаты первых двух вычислений:

Шаг 4. Проводим последнюю операцию и получаем результат:

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

В программировании такие стопки называются стеком — от английского stack, то есть стопка или кипа.

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

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

Реализация стека через массив

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

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

  • Метод push() помещает элемент на вершину стека, как карточку наверх стопки
  • Метод pop() убирает элемент с вершины и возвращает его
  • Метод isEmpty() проверяет, пуст ли стек

В JavaScript методы push() и pop() уже присутствуют в массиве, поэтому мы можем использовать их как есть:

class Stack  items = []; push(value)  this.items.push(value); > pop()  return this.items.pop(); > isEmpty()  return this.items.length == 0; > >
class Stack: items = [] def push(self, value): self.items.append(value) def pop(self): return self.items.pop() def is_empty(self): return len(self.items) == 0
php class Stack  public $items = []; public function push($value)  array_push($this->items, $value); > public function pop()  return array_pop($this->items); > public function isEmpty()  return count($this->items) == 0; > >
import java.util.List; import java.util.ArrayList; class StackT>  ListT> items = new ArrayList<>(); public void push(T item)  items.add(item); > public T pop()  var lastElementIndex = items.size() - 1; var lastElement = (T) items.get(lastElementIndex); items.remove(lastElementIndex); return lastElement; > public boolean isEmpty()  return items.isEmpty(); > >

Метод isEmpty() возвращает true , потому что массив пуст — содержит

Воспользуемся нашим стеком, чтобы вычислить значение выражения

let stack = new Stack(); const expression = '3 2 + 4 5 + *'; const lexems = expression.split(' '); for (lexem of lexems)  let a; let b; switch (lexem)  case '+': b = stack.pop(); a = stack.pop(); stack.push(a + b); break; case '-': b = stack.pop(); a = stack.pop(); stack.push(a - b); break; case '*': b = stack.pop(); a = stack.pop(); stack.push(a * b); break; case '/': b = stack.pop(); a = stack.pop(); stack.push(a / b); break; default: stack.push(parseFloat(lexem)); > > console.log(stack.pop()); // 45
stack = Stack() expression = '3 2 + 4 5 + *' lexems = expression.split(' ') for lexem in lexems: # В Python версии 3.10 и выше возможно использовать конструкцию match/case, но в данном случае рассмотрим реализацию через if/else if lexem == '+': a = stack.pop() b = stack.pop() stack.push(a + b) elif lexem == '-': a = stack.pop() b = stack.pop() stack.push(a - b) elif lexem == '*': a = stack.pop() b = stack.pop() stack.push(a * b) elif lexem == '': a = stack.pop() b = stack.pop() stack.push(a / b) else: stack.push(float(lexem)) print(stack.pop()) # 45
php $stack = new Stack(); $expression = '3 2 + 4 5 + *'; $lexems = explode(' ', $expression); foreach ($lexems as $lexem)  $a; $b; switch ($lexem)  case '+': $b = $stack->pop(); $a = $stack->pop(); $stack->push($a + $b); break; case '-': $b = $stack->pop(); $a = $stack->pop(); $stack->push($a - $b); break; case '*': $b = $stack->pop(); $a = $stack->pop(); $stack->push($a * $b); break; case '/': $b = $stack->pop(); $a = $stack->pop(); $stack->push($a / $b); break; default: $stack->push(floatval($lexem)); > > print_r($stack->pop()); // 45
var stack = new Stack(); var expression = "3 2 + 4 5 + *"; String[] lexems = expression.split(" "); for (String lexem : lexems)  float a; float b; switch (lexem)  case "+": b = stack.pop(); a = stack.pop(); stack.push(a + b); break; case "-": b = stack.pop(); a = stack.pop(); stack.push(a - b); break; case "*": b = stack.pop(); a = stack.pop(); stack.push(a * b); break; case "/": b = stack.pop(); a = stack.pop(); stack.push(a / b); break; default: stack.push(Float.parseFloat(lexem)); > > stack.pop(); // 45

Как видите, решение не очень сложное. Мы разбиваем строку с выражением на лексемы и обрабатываем каждую лексему в цикле.

Если лексема — это знак операции, то мы «снимаем» с вершины стека два числа, выполняем операцию и помещаем результат обратно на стек.

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

Порядок операндов не важен для таких операций, как сложение и умножение, потому что

. Но при делении это уже не так —

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

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

Очередь организована по принципу FIFO (англ. first in — first out, «первым пришел — первым ушел»).

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

В STL для работы со стеком определен тип данных queue , для работы с которым подключается одноименная библиотека. Описание стека:

queue имя переменной ;

В примере 21.14 перечислены операции, доступные для работы с очередью. Большинство функций для работы с очередью имеют аналоги для типа данных list .

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

Этапы выполнения задания

I. Исходные данные: переменная s — строка, содержащая прописные и строчные буквы.

II. Результат: пары букв и набор букв, оставшийся без пары.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Будем просматривать строку слева направо.

2.1. В очередь будем заносить буквы одного регистра.
2.2. Если появляется символ в другом регистре, то достаем букву из очереди и выводим пару.
2.2.1. Для проверки того, что две буквы относятся к одному регистру, создадим логическую функцию check. Буква x является прописной, если для нее выполняется условие x >= ‘A’ && x = ‘a’ && x 2.2.2. Для вывода букв в нужном порядке создадим функцию vyvod .

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

IV. Описание переменных: s – string, q – queue.

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

Пример 21.13. Добавление и удаление элемента в очереди:

Пример 21.14. Операции для типа данных queue.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *