§ 21. Структуры данных: 21.3. Стек

§ 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. Проверку скобочной последовательности, состоящей из скобок различного типа, удобно выполнить при помощи структуры стек. Будем просматривать строку слева направо.

2.1. Если текущий символ — открывающаяся скобка, то этот символ заносится в стек.
2.2. Если текущий символ — закрывающаяся скобка, то проверяем, что находится в вершине стека.
2.2.1. Если в вершине стека лежит соответствующая открывающаяся скобка, то очередная скобка не добавляется, а имеющаяся в вершине удаляется.
2.2.2. Если в вершине скобка другого типа, то работа программы прерывается и выдается ответ «нет».
2.2.3. Если стек пуст, то работа программы прерывается и выдается ответ «нет».
2.3. Если в конце работы программы стек оказывается пустым, то скобочная последовательность правильная, иначе — нет.

3. Вывод результата.

IV. Описание переменных: s – string, st – stack<char>.

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

Пример 21.10. Добавление и удаление элемента в вершине стека:

Пример 21.11. Операции для типа данных stack.

Функция	Действие
top	Доступ к вершине стека
empty	Проверяет отсутствие элементов
size	Возвращает количество элементов
push	Вставляет элемент
pop	Удаляет верхний элемент

Пример 21.12.

Правильные скобочные последовательности: [([])((([[[]]])))]{()}, ()((()))[[]]. Неправильные скобочные последовательности: [[)) (несоответствие типа закрывающихся скобок типу открывающихся), }{ (закрывающая скобка стоит раньше открывающейся), [[{{}}] (не каждой открывающейся скобке соответствует закрывающаяся).

V. Программа:

#include <iostream>

#include <string>

#include <stack>

using namespace std;

using namespace std::__cxx11;

int main()

{

string s;

cout << "s = " ;

cin >> s;

string otkr = "([{<";

string zakr = ")]}>";

int n = s.length();

stack <char> st;

bool f = true;

for (int i = 0; i < n; i++){

if (otkr.find(s[i]) != -1)

st.push(s[i]);

if (zakr.find(s[i]) != -1){

if (st.empty()){

f = false;

break;

}

if (zakr.find(s[i]) ==

otkr.find(st.top()))

st.pop();

else{

f = false;

break;

}

if (st.empty() && f)

cout << "da";

else

cout << "net";

return 0;

}

VI. Тестирование.

VII. Анализ результатов. Рассмотрим пример для правильной скобочной последовательности [([])(([]))]. В первой строке — текущий символ, во второй — состояние стека.

[	(	[	]	)	(	(	[	]	)	)	]
[	[(	[([	[(	[	[(	[((	[(([	[((	[(	[