§ 21. Структуры данных
21.3. Стек
Стек — динамическая линейная структура данных, хранящая последовательность элементов, в которой размещение новых и удаление существующих происходит с одного конца, называемого вершиной стека (top). Стек организован по принципу LIFO (англ. last in — first out, «последним пришел — первым ушел»). Для стека определены операции добавления элемента и удаления элемента (пример 21.10). По своей организации стек является линейным списком, добавление и удаление элементов в который допускается только в начало списка. В STL для работы со стеком определен тип данных stack, для чего подключается одноименная библиотека. Описание стека: stack <тип данных> имя переменной; В примере 21.11 перечислены операции, доступные для работы со стеком. Большинство функций для работы со стеком имеют аналоги для типа данных list. Пример 21.12. Правильная скобочная последовательность — последовательность, состоящая из символов — «скобок», в которой каждой открывающейся скобке соответствует закрывающаяся скобка такого же типа, что и открывающаяся скобка. Проверить, является ли заданная скобочная последовательность правильной. Этапы выполнения задания I. Исходные данные: переменная s — строка, содержащая скобочную последовательность. II. Результат: ответ «да» или «нет». III. Алгоритм решения задачи. 1. Ввод исходных данных. 2.1. Если текущий символ — открывающаяся скобка, то этот символ заносится в стек. 3. Вывод результата. IV. Описание переменных: s – string, st – stack<char>. |
Принцип работы стека часто сравнивают со стопкой тарелок: чтобы взять тарелку из середины стопки, нужно снять верхние. Стек также можно сравнить с железнодорожным путём: вагон, который попал туда последним, заберут первым. Пример 21.10. Добавление и удаление элемента в вершине стека: Пример 21.11. Операции для типа данных stack.
Правильные скобочные последовательности: [([])((([[[]]])))]{()}, ()((()))[[]]. Неправильные скобочные последовательности: [[)) (несоответствие типа закрывающихся скобок типу открывающихся), }{ (закрывающая скобка стоит раньше открывающейся), [[{{}}] (не каждой открывающейся скобке соответствует закрывающаяся). V. Программа:
VI. Тестирование. VII. Анализ результатов. Рассмотрим пример для правильной скобочной последовательности [([])(([]))]. В первой строке — текущий символ, во второй — состояние стека.
|