Приветствую всех,
После окончания школы Flatiron я изучал алгоритмы и структуры данных. Мне это показалось очень интересным, и они являются важной частью вашего технического интервью. Итак, на этот раз я вернулся с другим блогом о структурах данных и на этот раз о его стеках и очередях. Стеки и очереди очень похожи, обычно они рассматриваются вместе в главе. Они очень простые и имеют много общего.
Куча
Стек - это линейная структура данных, в которой есть один элемент, другой элемент и так далее. Вы можете добавлять или удалять элемент по ходу. Стек следует за LIFO (последний вошел - первым ушел), последний элемент, добавленный в стек, будет первым элементом, удаленным из стека. Возможно, вы слышали о стеках в стеке вызовов рекурсии, это очень похоже на это. Например, представьте себе стопку тарелок. Недавно добавленная пластина находится сверху и будет первой, когда вы ее удалите. Пример программирования из реальной жизни, вы можете подумать о функциях Undo или Redo в документе Microsoft Word. Стеки могут быть реализованы разными способами, два из которых - это массивы и связанные списки.
Большое количество стопок:
- Вставка - O (1)
- Удаление - O (1)
- Поиск - O (N)
- Доступ - O (N)
Очередь
Queue похож на Stack, основное отличие состоит в том, как элементы удаляются из Stacks. Очередь следует за FIFO (первым пришел - первым ушел), первый элемент, добавленный в стек, будет первым элементом, удаленным из стека. Например, вы можете представить очередь кассы в продуктовом магазине: первый человек, который встанет в очередь, будет обслужен первым. Так же и в Queue, первый добавленный элемент будет первым выведенным элементом. Пример программирования из реальной жизни, представьте, когда вы распечатываете 5 разных документов. Принтер может обрабатывать (печатать) только одну вещь за раз, оставшиеся будут помещены в очередь. Как и стеки, вы можете реализовать разными способами.
Большое количество очередей:
- Вставка - O (1)
- Удаление - O (1)
- Поиск - O (N)
- Доступ - O (N)
В заключение, в самых общих чертах, стек - это набор объектов, доступ к которым осуществляется в режиме LIFO (последний вошел - первым ушел). С другой стороны, очередь - это набор объектов, доступ к которым осуществляется по шаблону FIFO (First In First Out).
Удачного кодирования :) и счастливых праздников
Ресурсы:
https://www.thecrazyprogrammer.com/2019/01/types-of-queues-in-data-structure.html
