Програмування С, С++теорія та практика (частина 1)
1.19.2 Стеки
Стек — динамічна структура даних, яка представляє собою впорядкований набір елементів, в якому додавання нових елементів і видалення існуючих проходить з одного кінця, який називається вершиною стека.
Стек реалізує принцип ЬІРО (іакі іп - йгкі оиі, останнім прийшов - першим пішов). Найбільш наглядним прикладом організації стеку може бути дитяча пірамідка, де додавання і знімання кілець здійснюється як раз відповідно до цього принципу.
Основні операції, які можна виконувати над стеками :
• додавання елемента в стек;
• вилучення елемента із стека;
• перевірка, чи порожній стек;
• перегляд елемента у вершині стека без видалення;
• очистка стека.
Стек створюється так само, як і лінійний список, так як стек є частковим випадком односпрямованого списку.
£урейе£ 1опд е1ет^уре;
£урейе£ з'Ьгис'Ь пойе {
е1ет^уре Vа1; з'Ьгис'Ь пойе *пех£;
} з'Ьаск;
Реалізація основних операцій над стеками :
1. Початкове формування стеку з£аск *£ігз'Ь(е1ет'Ьуре й)
{
з£аск *рV=(з■Ьаск*) са11ос(1,зігео£(з^аск)); рV->Vа1=й;
рV->пех£=ниьь; ге'Ьигп рV;
};
2. Занесення значення в стек
VОій ризЬ(з^аск **'Ьор,е1ет'Ьуре й)
{
з£аск *рV=(з^аск*) са11ос(1,зігео£(з^аск));
рV->Vа1=й;
рV->пех£= * £ор;
*■Ьор=рV;
};
3. Вилучення елемента зі стека е1епЛуре рор(з£аск **£ор)
{
е1епЛуре ■Ьетр= (* £ор) - ^а1 ; з £аск *рV= * £ор;
* £ор=(* £ор)->пеx^;
£гее(рV); ге'Ьигп ■Ьетр;
};
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99