§ 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. Калі бягучы сімвал — адкрываючая дужка, то гэты сімвал заносіцца ў стэк.
3. Вывад выніку. IV. Апісанне пераменных: s – string, st – stack<char>. |
Прынцып работы стэка часта параўноўваюць са стосам талерак: каб узяць талерку з сярэдзіны стоса, трэба зняць верхнія. Стэк таксама можна параўнаць з чыгуначным пуцём: вагон, які трапіў туды апошнім, забяруць першым. Прыклад 21.10. Дабаўленне і выдаленне элемента ў вяршыні стэка: Прыклад 21.11. Аперацыі для тыпу даных stack.
Правільныя паслядоўнасці дужак: [([])((([[[]]])))]{()}, ()((()))[[]]. Неправільныя палядоўнасці дужак: [[)) (неадпаведнасць тыпу закрываючых дужак тыпу адкрываючых), }{ (закрываючая дужка стаіць раней за адкрываючую), [[{{}}] (не кожнай адкрываючай дужцы адпавядае закрываючая). V. Праграма:
VI. Тэсціраванне. VII. Аналіз вынікаў. Разгледзім прыклад для правільнай паслядоўнасці дужак [([])(([]))]. У першым радку — бягучы сімвал, у другім — стан стэка.
|