Стек (stack) у C++: легко та просто!

Всім привіт! Сьогодні ми розберемо структуру даних, яка часто використовується для вирішення задач або оптимізації програм. Усі колись у програмуванні чули таке слово, як стек.

Не лякайтеся, якщо ви його не знаєте. Ми вам покажемо, що це за звір і спробуємо розібратися як використовувати його для спільної роботи.

Що таке стек і як він працює

Стек – це структура даних, яка працює за принципом FILO (First in – last out; перший прийшов – останній пішов). У C++ вже є готовий шаблон-stack.

У стеку елемент, який увійшов перший – вийде самим останнім. Виходить, якщо ви додали три елементи в стек першим буде видалено останній доданий елемент.

На малюнку 1 ви можете побачити 6 чисел: 6, 5, 1, 2, 5, 9. До речі, витягувати їх будемо у такому самому порядку. Наприклад, щоб отримати число 1, нам доведеться спочатку витягти числа 6 і 5, а потім уже 1. Так як це стек, ці числа ми додавали в зворотному порядку. Якщо бути точним ось так: 9, 5, 2, 1, 5, 6.

У стеку немає індексів як у масиві, а значить ви не можете звернутися до певного елементу. Все тому, що стек побудований на зв'язкових списках.

Це означає, що кожен елемент (крім останнього – він вказує на NULL, якщо простими словами, то на нічого) має покажчик на наступний елемент. Але є елемент, на який немає покажчика – перший (або як його ще називають головний).

Ви напевно запитаєте, навіщо використовувати зв'язкові списки, якщо з таким же успіхом можна було використовувати простий масив. Тим більше, навіть новачкові не знадобиться багато часу, щоб розібратися в ньому.

Але вся перевага шаблонного стека полягає в додаванні та видаленні елементів.Ці операції відбуваються за константний час (Це хороший плюс).

До речі, деякі програмісти роблять стек на масивах. Про такий спосіб використання стека ми поговоримо трохи згодом.

Як створити стек у C++

Для використання шаблону стека на початку програми ми повинні підключити бібліотеку – .

Щоб створити стек нам знадобиться оперувати схемою нижче:

stack тип даних> ім'я>;

Давайте ретельніше її розберемо:

• З нового рядка ми маємо написати слова stack.
• – тут нам доведеться написати той тип даних, який зберігатиметься в стеку.
• – тут вам все має бути зрозумілим.

Методи – це функції, які використовуються для контейнерів типу черги та стеку. Зараз ми розберемо такі функції на прикладі нижче:

#include #include // Підключаємо бібліотеку для  // Використання стека using namespace std; int main()  setlocale(LC_ALL,"rus"); stack int> steck; // створюємо стек int i = 0; cout  <"Введіть шість будь-яких цілих чисел: "  <>; // пропонуємо користувачеві // Ввести 6 чисел while (i != 6)  int a; cin >> a; steck.push(a); // додаємо введені числа i++; > if (steck.empty()) cout  <"Стек не порожній"; // перевіряємо чи порожній стек (ні) cout  <"Верхній елемент стеку:"  <>.top()  <>; // Виводимо верхній елемент cout  <"Давайте видалимо верхній елемент"  <>; steck.pop(); // видаляємо верхній елемент cout  <"А це новий верхній елемент:"  <>.top(); // Виводимо вже новий // верхній елемент system("pause"); return 0; > 

А ось розбір цієї програми:

У рядку 18: ми додаємо в стек елемент за допомогою функції push() . У дужках має бути значення, яке ми хочемо додати.

До речі, якщо ви хочете самі створювати такі функції у себе в програмах (як це роблять професіонали) або хочете дізнатися як вони працюють, то про все це ви можете дізнатися ось тут.

У рядку 22: щоб перевірити чи порожній стек ми скористалися функцією empty() .

• Якщо результатом цієї функції буде true, то стек чистий.
• Якщо ж результатом буде false, то в стеку щось є.

У рядку 27: була використана функція pop(). Її використовують для видалення верхнього елемент стека.

У функції pop() на відміну від функції push() у дужках не потрібно нічого вказувати, але самі дужки обов'язково повинні бути присутніми. Також для функцій: empty() і top() !

У рядках 24 та 29: ми вирішили звернутися до верхнього елементу стека, для цього було використано функцію – top() .

Давайте подивимося, який буде результат цієї програми при запуску:

Введіть шість будь-яких цілих чисел: 9 5 2 1 5 6 Верхній елемент стека: 6 Давайте видалимо верхній елемент А це новий верхній елемент: 5 Process returned 0 (0x0) execution time : 0.010 s 1

У бібліотеку stack додали нову функцію peek() , за допомогою якої можна звернутися до N елементу стека (від вершини).

Так, за допомогою цієї функції стек починає нагадувати масив.

Нижче ви використовували функцію peek() , щоб вивести третій елемент:

 setlocale(LC_ALL,"rus"); stack int> steck; steck.push(5); // Додаємо steck.push(1); // Елементи steck.push(9); // в steck.push(10); // стек cout  <"Третій елемент стеку:"  <>.peek(3); // виведе 1

Цією функцією ми можемо скористатися лише у версіях C++ 11 та вище.

Функцію peek() використовує невелике коло програмістів і треба відразу сказати ця функція не стала такою затребуваною, як від неї очікували творці.

Як створити стек за допомогою масиву

Багато програмістів використовують не використовують шаблон стек, а замість них оперують стеками через масиви. Нині ми вам покажемо як реалізувати стек за допомогою масиву.

Нижче ми створили масив під ім'ям – steck на 20 елементів, також ми створили змінну i яка буде вказувати на верхній елемент стеку.

Для додавання елемента ми збільшуватимемо i на один і в комірку steck[i] записуватимемо елемент.

Для видалення елемента ми просто зменшуватимемо i на один.

Як ви напевно вже здогадалися щоб звернутися до верхнього елементу стеку ми просто звертаємось до i елементу масиву.

Змінна i замінила нам функцію push() та функцію top() .

Щоб подивитись чи порожній стек ми просто перевіряємо умову i == -1 :

• Якщо воно true, то стек порожній.
• Якщо воно false, то в стеку є якісь елементи.

Реалізація стека за допомогою масиву знаходиться нижче:

#include using namespace std; int main()  int steck[20]; int i = -1; // оголосили стек for (int j = 0; j  6; j++)  int a; cin >> a; i++; // збільшуємо i на один steck[i] = a; // додаємо в стек елемент > if (i == -1) cout  <"Стек порожній"; // перевіряємо чи порожній стек (ні) cout  <>[i]  <"це верхній елемент стека"; cout  <"Зараз ми видалимо верхній елемент"; i--; // зменшуємо i на один system("pause"); return 0; >

Який спосіб створення стека використовувати

Сьогодні ми вивчили два способи реалізації стеку:

Якщо ви використовуєте стек у вашій програмі і вам краще щоб вона робота якнайшвидше, то використовуйте перший спосіб реалізації стека.

Якщо вам все одно на швидкодію програми, то можете використовувати створення стека через масив. Особисто ми використовуємо перший спосіб реалізації стека. Він швидкий і простий для використання та оголошення.

У наступному уроці ми вивчимо ще одну дуже важливу структуру даних – чергу. Цю структуру даних використовують у багатьох месенджерах (наприклад, телеграм).

Щоб закріпити прочитаний матеріал, ми радимо вам:

1. Оголосити стек.
2. Додати до нього 3 будь-які елементи.
3. Вивести верхній елемент.
4. Видалити верхній елемент.
5. Знову вивести верхній елемент.

У цій статті ми хотіли вам показати які функції є у ​​стеку і як ним користуватися у своїй програмі. Сподіваємося ви дізналися що це за звір!

Є питання, пишіть у коментарі, ми з радістю вам відповімо. Успіхів!

Якщо хочете завжди бути в курсі останніх новин у світі програмування та IT, підписуєтеся на мій Telegram-канал, де я поділяюся свіжими статтями, новинами та корисними порадами. Радий бачити вас серед передплатників!

Читайте також

У цій статті ми розберемося зі списками C++. Ми дізнаємося що таке list, як його створити, як ним користуватися та підіб'ємо підсумки.

У цьому уроці ви дізнаєтеся, що таке вектор у C++, а також якщо ви хочете дізнатися, як правильно користуватися і які функції до них застосовувати – вам сюди.

У C++, контейнер std::vector є динамічним масивом, який може автоматично змінювати свій розмір. Часто виникає необхідність визначити скільки елементів на даний момент містить vector. Зустрічайте функцію size! У цій статті ми розглянемо, як працює функція size, покажемо практичні приклади та розповімо про інші корисні функції.

У цьому уроці ви дізнаєтеся, що таке функція copy, як її використовувати. А також дізнаєтесь, з якими контейнерами вона працює.

У цьому уроці ви познайомитеся з двома контейнерами C++, які є дуже важливими – set і multiset. Інакше їх ще називають множиною і мультимножиною. Вони автоматично сортуються під час додавання нового елемента. Але кожен з них має свою особливість, яку ми розуміємо в цій статті.

У цьому уроці ви дізнаєтеся: що таке map, як правильно його використовувати, якими функціями можна оперувати, а також чи варто його використовувати в проектах.

Тут ви дізнаєтеся про ітератори все, що вам потрібно: що це таке, як воно працює, з якими контейнерами його можна застосовувати. І, звісно, ​​винятки.

Розберемося у функції find із C++ і навчимося використовувати її з такими контейнерами, як vector та set.

C++ пропонує різноманітні інструменти для роботи з рядками, і одна з найважливіших функцій – це string::size. У цій статті ми докладно розглянемо цю функцію, зрозуміємо, як вона вимірює рядки та досліджуємо її практичне застосування.

Привіт я студент другого курсу технічного університету. Після пропуску кількох пар програмування за станом здоров'я я зіткнувся з нерозумінням таких тем, як «Стек» та «Черга». Шляхом спроб і помилок, за кілька днів, до мене нарешті дійшло, що це таке і з чим це їдять. Щоб у вас розуміння не зайняло стільки часу, у цій статті я розповім про те, що таке «Стек», яким чином і на яких прикладах я зрозумів, що це таке. Якщо вам сподобається, я напишу другу частину, яка торкатиметься вже такого поняття, як «Черга»

На Вікіпедії визначення стека звучить так:

Стек (англ. stack – стопка; читається стек) – абстрактний тип даних, що представляє собою список елементів, організованих за принципом LIFO (англ. last in – first out, "останнім прийшов – першим вийшов").

Досить повне визначення, але можливе для новачків воно буде трохи важким для розуміння.

Тому перше, на чому я хотів би загострити увагу, це уявлення стека у вигляді речей з життя. Першою на думку мені спала інтерпретація у вигляді стопки книг, де верхня книга — це вершина.

Насправді стек можна уявити у вигляді стопки будь-яких предметів чи то стопка листів, зошитів, сорочок тощо, але приклад із книгами я думаю буде найоптимальнішим.

Отже, з чого складається стек.

Стек складається з осередків (у прикладі – це книги), які представлені у вигляді структури, що містить будь-які дані та покажчик типу даної структури на наступний елемент.
Важко? Чи не біда, давайте розбиратися.

На цій картинці схематично зображено стек. Блок виду «Дані/*next» і є наш осередок. *next, як бачимо, вказує на наступний елемент, тобто покажчик *next зберігає адресу наступного осередку. Покажчик *TOP вказує на вершину стек, тобто зберігає її адресу.

З теорією закінчили, перейдемо до практики.

Для початку нам потрібно створити структуру, яка буде нашою «осередком»

Початківцям можливо буде не зрозуміло, навіщо наш покажчик типу comp, точніше сказати покажчик типу структури comp. Поясню, щоб покажчик *next міг зберігати структуру comp, їй потрібно позначити тип цієї структури. Тобто вказати, що зберігатиме покажчик.

Після того, як у нас заданий «Комірка», перейдемо до створення функцій.

Функції

Функція створення «Стека»/додавання елемента до «Стек»

При додаванні елемента у нас виникне дві ситуації:

• Стек порожній, і потрібно створити його
• Стек вже є і потрібно лише додати до нього новий елемент

void s_push(comp **top, int D) < //функція типу void(нічого не повертає) яка приймає вказівник на вершину стека і змінну яка записуватиметься в комірку comp *q; // Створюємо новий покажчик типу типу структури comp. По суті, це і є наш новий елемент q = new comp(); //виділяємо пам'ять нового елемента q->Data = D; //Записуємо необхідне число в Data елемента if (top == NULL) < //Якщо вершини немає, тобто стек порожній *top = q; //вершиною стека буде новий елемент >else //якщо стек не порожній < q->next = * top; //Проводимо зв'язок від нового елемента, до вершини. Тобто кладемо книжку на вершину чарки. * top = q; //Позначаємо, що вершиною тепер є новий елемент > > 

Розберемо трохи трохи докладніше.
По-перше, чому функція приймає **top, тобто покажчик на покажчик, щоб вам було найбільш зрозуміло, я залишу розгляд цього питання на потім. По-друге, детальніше поговоримо про q->next = *top і про те, що означає ->.

-> означає те, що грубо кажучи, ми заходимо до нашої структури і дістаємо звідти елемент цієї структури. У рядку q->next = *top ми з нашого осередку дістаємо покажчик на наступний елемент *next і замінюємо його на покажчик, який вказує на вершину стека *top. Тобто ми проводимо зв'язок, від нового елемента до вершини стека. Тут нічого складного, як з книжками. Нову книгу ми кладемо рівно на вершину стопки, тобто проводимо зв'язок від нової книги до вершини стопки книг.Після цього нова книга автоматично стає вершиною, тому що стек не стопка книг, нам потрібно вказати, що новий елемент – вершина, для цього пишеться: * top = q;.

Функція видалення елемента із «Стеку» за даними

Ця функція видалятиме елемент із стека, якщо число Data осередку(q->Data) дорівнюватиме числу, яке ми самі позначимо.

Тут можуть бути такі варіанти:

• Осередок, який нам потрібно видалити є вершиною стека
• Осередок, який нам потрібно видалити знаходиться в кінці, або між двома осередками

void s_delete_key(comp **top, int N) Data == N) next;//пересуваємо вершину на наступний елемент free(q);//очищаємо комірку q->Data = NULL; //Далі щоб уникнути помилок ми обнуляємо змінні у віддаленій комірці, оскільки у деяких компіляторах віддалена комірка має змінні не NULL значення, а дослівно " Читання пам'яті неможливо " чи числа " -2738568384 " чи інші, залежно від компілятора. q->next = NULL; > else//якщо елемент останній або знаходиться між двома іншими елементами < prev->next = q->next;//Проводимо зв'язок від попереднього елемента до наступного free(q);//очищаємо комірку q->Data = NULL;/ /обнулюємо змінні q->next = NULL; > >// якщо Data елемента НЕ дорівнює числу, яке потрібно видалити prev = q; //запам'ятовуємо поточну комірку як попередню q = q->next; // Переміщуємо покажчик q на наступний елемент > > 

Покажчик q у разі грає таку ж роль, як і покажчик у блокноті, він бігає у всьому стеку, доки стане рівним NULL(while(q != NULL)), іншими словами, поки стек не закінчиться.

Для кращого розуміння видалення елемента проведемо аналогії з звичкою. Якщо нам потрібно прибрати книгу зверху, ми її забираємо, а книга під нею стає верхньою.Тут те саме, тільки на початку ми повинні визначити, що наступний елемент стане вершиною *top = q->next; і лише потім видалити елемент free(q);

Якщо книга, яку потрібно прибрати, знаходиться між двома книгами або між книгою та столом, попередня книга ляже на наступну або на стіл. Як ми вже зрозуміли, книга у нас-це осередок, а стіл виходить це NULL, тобто наступного елемента немає. Виходить так само як з книгами, ми позначаємо, що попередній осередок буде пов'язаний з наступним prev->next = q->next;, варто зазначити що prev->next може дорівнювати як комірці, так і нулю, якщо q->next = NULL, тобто комірки немає (книга ляже на стіл), після цього ми очищаємо комірку free(q).

Так само варто відзначити, що якщо не провести цей зв'язок, ділянка осередків, яка лежить після віддаленого осередку стане недоступною, так як загубиться той самий зв'язок, який з'єднує один осередок з іншого і ця ділянка просто загубиться в пам'яті

Функція виведення даних стека на екран

Найпростіша функція:

void s_print(comp *top) < // приймає покажчик на вершину стека comp *q = top; //встановлюємо q на вершину while(q) < //поки q не порожній (while(q) еквівалентно while(q != NULL)) printf_s("%i", q->Data);//виводимо на екран дані осередки стека q = q->next; // Після того як вивели пересуваємо q на наступний елемент (комірку) > > 

Тут я думаю все зрозуміло, хочу сказати лише те, що q потрібно сприймати як бігунок, він бігає по всіх осередках від вершини, куди ми його встановили спочатку: * q = top;до останнього елемента.

Головна функція

Добре, основні функції роботи зі стеком ми записали, викликаємо.
Подивимося код:

Повернемося до того, чому в функцію ми передавали покажчик на покажчик вершини.Справа в тому, що якби ми ввели в функцію лише покажчик на вершину, то «Стек» створювався і змінювався тільки всередині функції, в головній функції вершина як була б, так і залишалася NULL. Передаючи вказівник на покажчик ми змінюємо верхню частину *top у головній функції. Виходить, якщо функція змінює стек, потрібно передавати в неї вершину покажчиком на покажчик, так у нас було в функції s_push, s_delete_key. У функції s_print "Стек" не повинен змінюватися, тому ми передаємо просто вказівник на вершину.
Замість цифр 1,2,3,4,5 можна також використовувати змінні типу int.

Повний код програми:

#include; #include; struct comp <// Структура з ім'ям comp int Data; //Якісь дані (можуть бути коханими, наприклад можна написати int key; char Data; або додати ще якісь дані) comp *next;//Покажчик типу comp на наступний елемент >; void s_push(comp **top, int D) < //функція типу void(нічого не повертає) яка приймає вказівник на вершину стека і змінну яка записуватиметься в комірку comp *q; / / Створюємо новий покажчик q, який прирівнюємо до вершини стека. По суті, це і є наш новий елемент q = new comp(); //виділяємо пам'ять нового елемента q->Data = D; //Записуємо D в Data елемента if (top == NULL) < //Якщо вершини немає, тобто стек порожній *top = q; //вершиною стека буде новий елемент >else //якщо стек не порожній < q->next = * top; //Проводимо зв'язок від нового елемента, до вершини. Тобто кладемо книжку на вершину чарки. * top = q; //Пишемо, що вершиною тепер є новий елемент > > void s_delete_key(comp **top, int N) Data == N) next;//пересуваємо вершину на наступний елемент free(q);//очищаємо комірку q->Data = NULL; //Далі щоб уникнути помилок ми обнулюємо змінні у віддаленій комірці, оскільки у деяких компіляторах віддалена комірка має змінні не NULL значення, а дослівно "Чіння пам'яті неможливо" чи числа "-2738568384" чи інших, залежно від компілятора. q->next = NULL; > else//якщо елемент останній або знаходиться між двома іншими елементами < prev->next = q->next;//Проводимо зв'язок від попереднього елемента до наступного free(q);//очищаємо комірку q->Data = NULL;/ /обнулюємо змінні q->next = NULL; > >// якщо Data елемента НЕ дорівнює числу, яке потрібно видалити prev = q; //запам'ятовуємо поточну комірку як попередню q = q->next; // Переміщаємо покажчик q на наступний елемент > > void s_print(comp *top) //встановлюємо q на вершину while(q) < //поки q не порожній (while(q) еквівалентно while(q != NULL)) printf_s("%i", q->Data);//виводимо на екран дані клітинки стека q = q->next; //на початку програми у нас немає черги, відповідно вершини немає, даємо їй значення NULL //Далі починаємо додавати цифри від 1 до 5 в наш стек s_push(&top, 1); s_push(&top, 2); s_push(&top, 3); s_push(&top, 4); s_push(&top, 5); //після виконання функцій у стеку ми будемо 54321 s_print(top);//выводим s_delete_key(&top, 4); //Потім видаляємо 4, у стеку виходить 5321 printf_s("\n");//перекладаємо на новий рядок s_print(top);//виводимо system("pause");//ставимо на паузу >

Так як в стек елементи постійно додаються на вершину, елементи будуть виводитися в зворотному порядку

Насамкінець хотілося б подякувати за приділений моїй статті час, я дуже сподіваюся, що цей матеріал допоміг деяким програмістам-початківцям зрозуміти, що таке «Стек», як ним користуватися і надалі у них більше не виникне проблем. Пишіть у коментарях свою думку, а також про те, як мені покращити свої статті в майбутньому. Дякую за увагу.