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

Обновлено: 30.06.2024

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

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

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

Начнем с пустой подставки для тарелок.

И затем мы добавляем красную, синюю и зеленую табличку в стойку в указанном порядке.

Ключевой момент, который необходимо понять, заключается в том, что по мере добавления новых пластин они добавляются в верхнюю часть стопки. Если клиент забирает тарелку, он или она получит последнюю добавленную тарелку (зеленая тарелка). Следующий клиент получит синюю табличку, и, наконец, красная табличка будет удалена.

Определение класса

Класс Stack определяет методы Push , Pop и Peek , свойство Count , и использует класс LinkedList для хранения значений, содержащихся в стеке.

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

По определению, структура данных - способ представления данных в памяти, позволяющий эффективно выполнять с ними определённый набор операций. Например, простой массив лучше всего подходит для частого обращения к элементам по индексам и их изменению. А удаление элемента из середины массива работает за \(O(N)\). Если вам для решения задачи нужно часто удалять элементы, то придётся воспользоваться другой структурой данной. Например, бинарное дерево ( std::set ) позволяет делать это за \(O(\log N)\), но не поддерживает работу с индексами, только поочерёдный обход всех элементов и поиск по значению (тоже за \(O(\log N)\)).

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

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

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

Добавить элемент в стек (Сложность: \(O(1)\))
Извлечь элемент из стека (Сложность: \(O(1)\))
Проверить, пуст ли стек (Сложность: \(O(1)\))

Для объяснения принципа работы стека часто используется аналогия со стаканом с печеньем. Представьте, что на дне вашего стакана лежат несколько кусков печенья. Вы можете положить наверх ещё один кусок или достать уже находящийся наверху. Остальные куски закрыты верхним, и вы про них ничего не знаете. Для описания стека часто используется аббревиатура LIFO (Last In, First Out), подчёркивающая, что элемент, попавший в стек последним, первым будет из него извлечён.

Приведём простую реализацию стека на C++. Для простоты максимальный размер нашего стека будет ограничен тысячей элементов:

Как видите, для реализации стека хватает одного массива и одного указателя, обозначающего крайний элемент.

Очередь

Очередь поддерживает тот же набор операций, что и стек, но имеет противоположную семантику. Для описания очереди используется аббревиатура FIFO (First In, First Out), так как первым из очереди извлекается элемент, раньше всех в неё добавленный. Название этой структуры говорит само за себя: принцип работы совпадает с обычными очередями в магазине или на почте.

Реализация очереди похожа на реализацию стека, но в этот раз нам понадобятся два указателя: для первого элемента очереди (“головы”) и последнего (“хвоста”):

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

Структура, объединяющая стек и очередь, называется дек (англ. deque - сокращение от double-ended queue, очередь с двумя концами). Как можно догадаться, она поддерживает уже знакомый набор операций:

Добавить элемент в начало дека (Сложность: \(O(1)\))
Извлечь элемент из начала дека (Сложность: \(O(1)\))
Добавить элемент в конец дека (Сложность: \(O(1)\))
Извлечь элемент из конца дека (Сложность: \(O(1)\))
Проверить, пуст ли дек (Сложность: \(O(1)\))

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

Стек, очередь и дек в стандартной библиотеке C++

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

С реализацией дека дела обстоят несколько иначе. Стандартный класс std::deque является не классическим деком, а скорее вектором с возможностью вставки и добавления в начало за \(O(1)\). Он поддерживает все операции, поддерживаемые классом std::vector , в том числе обращение к элементу по индексу и итераторы с произвольным доступом. Так что для работы с ним используйте те же методы, что и при работе с вектором.

Более сложные структуры данных

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

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

Цель лекции: изучить понятия, объявления, особенности доступа к данным и работы с памятью в стеках и очередях, научиться решать задачи с использованием стеков и очередей в языке C++.

Стек и очередь – это частные случаи линейного списка.

Стеки

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

Стек (англ. stack – стопка) – это структура данных , в которой новый элемент всегда записывается в ее начало (вершину) и очередной читаемый элемент также всегда выбирается из ее начала ( рис. 30.1). В стеках используется метод доступа к элементам LIFO ( Last Input – First Output, "последним пришел – первым вышел"). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно сначала взять верхнюю.

Стек – это список , у которого доступен один элемент (одна позиция). Этот элемент называется вершиной стека. Взять элемент можно только из вершины стека , добавить элемент можно только в вершину стека . Например, если записаны в стек числа 1, 2, 3, то при последующем извлечении получим 3,2,1.

Описание стека выглядит следующим образом:

где информационное поле – это поле любого ранее объявленного или стандартного типа;

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

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

Описание элементов стека аналогично описанию элементов линейного однонаправленного списка. Поэтому объявим стек через объявление линейного однонаправленного списка:

Основные операции , производимые со стеком:

создание стека;
печать (просмотр) стека;
добавление элемента в вершину стека ;
извлечение элемента из вершины стека ;
проверка пустоты стека;
очистка стека.

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

Пример 1. Дана строка символов . Проверьте правильность расстановки в ней круглых скобок.

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

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

Общие операции стека следующие четыре

нажмите, вставьте элемент в верхнюю часть стека
pop, вытолкнуть верхний элемент стека
посмотреть, просмотреть верхний элемент стека
getSize, посмотреть количество элементов в стеке

В этой статье стек реализован в виде массива.

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

Операция вставки, вставка нового элемента в позицию mTop, и mTop может увеличиваться автоматически.

Операция pop возвращает элемент в позиции после уменьшения mTop.

Получите количество элементов в стеке, равное размеру значения mTop.

Реализация стека относительно проста, но стек очень полезен.

В виртуальной машине Java вызов функции будет генерировать стек вызовов функции.Когда функция выполняется, возвращается возвращаемое значение функции, стек выталкивается, и функция вызывается обратно в то место, где функция была ранее называется. Рекурсия может легко решить многие проблемы, но самая большая проблема с рекурсией заключается в том, что эффективность выполнения невысока из-за слишком большого количества вызовов функций. Можно ли оптимизировать рекурсию в сочетании с идеей вызова функции виртуальной машины Java? Потому что рекурсия по существу сохраняет результат определенного состояния в стеке, а затем вычисляет другое состояние. Если вам не нужна рекурсия, вы также можете использовать структуру данных стека для хранения частичных результатов.

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

Обход предзаказа очень прост, и его легче всего преобразовать из трех обходов.

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

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

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

очередь

Общие операции очереди:

enqueue, enqueue, вставить элемент в начало очереди
dequeue, dequeue, удалить элементы в конце очереди
getSize, получить количество элементов очереди

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

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

Читайте также: