В прошлых статья мы разобрались с простыми линейными структурами теперь поговорим о их ближайших родственниках тоже о линейных структурах данных, но с конечными точками, а конкретно о «Стеках» и «Очередях».
Что же такое Стек?
Что бы нам быстро понять это мы прибегнем к визуализации и представив стопку книг на вашем столе. Глядя эту стопку, мы можем получить доступ только к книге которая сверху, а остальные у нас скрыты, и мы не сможем прочитать их название. После прочтения верхний книги мы убираем ее в сторону и открываем доступ к книге, лежавшей под ней. В этом заключается идея стека.
Для информации рассмотрим более серьезное определение:
Стек — это структура LIFO. Это расшифровывается как Last In First Out («последним вошёл, первым вышел»). При добавлении и удалении из стека последний добавленный элемент будет первым удаляемым.
Такая структура дает нам простоту ее использования так как несет в себе возможность применения только 3 операций: Push, Pop и Top
- С помощью Push мы добавляем новый объект в стек
- Pop удаляет объект из стека
- Ну а Top дает нам доступ к самому последнему объекту в стеке.
И это все!
Но плюс его заключается в том, что из-за того, что самыми быстрыми операциями являются добавление в конец и удаление элементов из конца. А стек всегда добавляет и удаляет с конца, благодаря этому операции выполняются невероятно быстро.
Что такое Очередь?
Ну тут как бы это банально не звучало представим, что вы стоите в очереди на кассу в магазине. Первого человека в очереди обслуживают, после чего он уходит. Потом обслуживается и уходит второй в очереди. Новые люди подходят к очереди и встают в её конец. Вот в этом заключается идея структуры данных «очередь» банально, но просто.
Ну и для закрепления разберем умную формулировку:
Очередь — это структура FIFO (First In First Out, «первым зашёл, первым вышел»). При добавлении и удалении из очереди первый добавляемый элемент будет первым извлекаемым.
Так же как и в стеке очередь не иметь большего разнообразия используемых операций, их всего 4:
- С помощью Push_Back мы добавляем элемент к концу очереди.
- Pop_Front позволяет нам удалять элемент из начала очереди.
- Front и Back позволяют нам получить доступ к двум концам очереди.
Часто бывает необходимость добавлять или удалять элементы из обоих концов очереди. На помощь в этом нам приходит структура называемая - двухсторонней очередью. В этом случае добавляется еще две операции: Push_Front – добавить в начало и Pop_Back – удалить с конца очереди.
Рассмотрим что такое «Очередь с приоритетом»
Это очень распространённая вариация очереди. Очередь с приоритетом очень похожа на обычную очередь. Разница в том, что мы можем задать приоритеты необходимым нам элементам очереди. Все самые важные элементы обрабатываются в порядке FIFO (вспоминаем - First In First Out, «первым зашёл, первым вышел»). Потом в порядке FIFO обрабатываются элементы с более низким приоритетом и так повторяется, пока обработаются все низкоприоритетные элементы, разумеется в порядке FIFO.
Такая же Схема работает и с добавлением нового элемента с более высоким приоритетом чем остальные элементы в очереди, новый элемент (так он по записи) попадает в начало очереди.
Очередь с приоритетом можно использовать для удобной реализации алгоритмов, например, процедуры поиска.
Заключение
Стеки, очереди, двухсторонние очереди и очереди с приоритетом — это не фундаментальные структуры данных, но их часто используют. Они очень эффективны, когда нужно работать только с конечными элементами данных, а элементы в середине не важны.
Всем добра!