Структуры данных и алгоритмы

Структуры данных и алгоритмы

(Третья часть — стеки и очереди)

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

Статья будет построена следующим образом:

Другой тип структуры?

Стек

Очередь

приоритетная очередь

Другой тип структуры?

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

Инструменты программиста

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

Ограниченный доступ

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

Более абстрактно

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

Стопки

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

Вот обзор операций стека и связанных с ними алгоритмов:

Операции со стеком:

• Push: эта операция добавляет элемент на вершину стека.
• Pop: эта операция удаляет элемент с вершины стека.
• Peek (или Top): эта операция извлекает элемент из вершины стека, не удаляя его.
• isEmpty: эта операция проверяет, пуст ли стек.
• Размер: эта операция возвращает количество элементов в стеке.

Стековые алгоритмы:

Соответствие круглых скобок:

В этом алгоритме стек используется для проверки сбалансированности заданной строки круглых скобок (а иногда и других символов). Например, «{[()]}» является сбалансированным, а «{[(])}» — нет. Стек помогает поддерживать правильный порядок открытия и закрытия символов.

Очереди

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

Вот обзор операций с очередями и связанных с ними алгоритмов:

Операции с очередью:

• Добавить (или предложить): эта операция добавляет элемент в конец очереди.
• Удалить (или опрос): эта операция удаляет элемент из начала очереди.
• Просмотр (или передний план): эта операция извлекает элемент из начала очереди, не удаляя его.
• isEmpty: Эта операция проверяет, пуста ли очередь.
• Размер: эта операция возвращает количество элементов в очереди.

Алгоритмы очереди:

Принтер:

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

Круговая очередь

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

Приоритетные очереди

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

Вот обзор операций приоритетной очереди и связанных с ними концепций:

Приоритетные операции с очередью:

• Вставить (или поставить в очередь): эта операция добавляет элемент в очередь с приоритетом, учитывая его значение приоритета. Элемент помещается в позицию, которая поддерживает порядок приоритета.
• Извлечь максимум (или удалить из очереди): эта операция удаляет и возвращает элемент с наивысшим приоритетом из очереди приоритетов.
• Просмотр (или просмотр): эта операция извлекает элемент с наивысшим приоритетом из очереди приоритетов, не удаляя его.
• isEmpty: эта операция проверяет, пуста ли приоритетная очередь. Размер: эта операция возвращает количество элементов в приоритетной очереди.

Алгоритмы приоритетной очереди:

Планирование задач с указанием сроков:

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

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