§ 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. Алгарытм рашэння задачы.

Увод зыходных даных.
Праверку паслядоўнасці дужак, якая складаецца з дужак рознага тыпу, зручна выканаць пры дапамозе структуры стэк.

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. Аналіз вынікаў. Разгледзім прыклад для правільнай паслядоўнасці дужак [([])(([]))]. У першым радку — бягучы сімвал, у другім — стан стэка.

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