Складіть в C++ STL з прикладом

Автор: Бенджамін Уокер Бенджамін Уокер
Hours оновлений

Що таке std::stack?

Стек — це структура даних, яка працює на основі техніки LIFO (останній прийшов, перший вийшов). std::stack дозволяє додавати та видаляти елементи лише з одного кінця.

Клас std::stack є адаптером контейнера. Об’єкти-контейнери містять дані подібного типу. Ви можете створити стек із різних контейнерів послідовності. Якщо контейнер не надано, за замовчуванням використовуватиметься deque containe. Контейнерні адаптери не підтримують ітератори, тому їх не можна використовувати для маніпулювання даними.

Синтаксис стека

Щоб створити стек, ми повинні включити файл заголовка в нашому коді. Потім ми використовуємо цей синтаксис для визначення std::stack:

template <class Type, class Container = deque<Type> > class stack;
  • тип – тип елемента, що міститься в std::stack. Він може бути будь-яким дійсним C++ тип або навіть тип, визначений користувачем.
  • Контейнер – тип базового об’єкта контейнера.

Типи учасників

Ось типи членів стека:

  • value_type - перший параметр шаблону, T. Він позначає типи елементів.
  • container_type - другий параметр шаблону, Container. Він позначає базовий тип контейнера.
  • size_type - беззнаковий інтегральний тип.

Operaції в стеку

A C++ стек підтримує наступні основні операції:

  • push – додає/виштовхує елемент у стек.
  • pop – видаляє/видаляє елемент зі стеку.
  • peek – повертає верхній елемент стека, не видаляючи його.
  • isFull – перевіряє, чи заповнений стек.
  • isEmpty – перевіряє, чи стек порожній.

Реалізація стека

Реалізація стека

Крок 1) Спочатку ми маємо порожній стек. Верхня частина порожнього стека встановлена ​​на -1.

Крок 2) Далі ми помістили елемент 5 у стек. Верхня частина стека вказуватиме на елемент 5.

Крок 3) Далі ми помістили елемент 50 у стек. Верхівка стека зсувається і вказує на елемент 50.

Крок 4) Потім ми виконали операцію pop, видаливши верхній елемент зі стеку. Елемент 50 витягується зі стеку. Тепер вершина стека вказує на елемент 5.

push() і pop()

Функція stack::push() додає новий елемент на вершину стека. Розмір стека збільшується на 1 після вставки. Синтаксис функції:

stack.push(value)

Значення - це елемент, який потрібно вставити в стек.

Функція stack:: pop() видаляє верхній елемент стека. Це найновіший елемент у стеку. Розмір стека зменшується на 1 після видалення. Ось синтаксис функції:

stack.pop()

Функція не приймає параметрів.

Приклад 1:

#include <iostream> 
#include <stack> 
using namespace std;
int main() {
	stack<int> st;
	st.push(10);
	st.push(20);
	st.push(30);
	st.push(40);
	
         st.pop();
	st.pop();

	while (!st.empty()) {
		cout << ' ' << st.top();
		st.pop();
	}
}

вихід:

push() і pop()

Ось скріншот коду:

push() і pop()

Пояснення коду:

  1. Включіть файл заголовка iostream у наш код, щоб використовувати його функції.
  2. Включіть файл заголовка стека в наш код, щоб використовувати його функції.
  3. Включіть простір імен std у наш код, щоб використовувати його класи без його виклику.
  4. Виклик функції main(). Логіку програми слід додати в цю функцію.
  5. Створіть стек st для зберігання цілочисельних значень.
  6. Використовуйте функцію push(), щоб вставити значення 10 у стек.
  7. Використовуйте функцію push(), щоб вставити значення 20 у стек.
  8. Використовуйте функцію push(), щоб вставити значення 30 у стек.
  9. Використовуйте функцію push(), щоб вставити значення 40 у стек.
  10. Використовуйте функцію pop(), щоб видалити верхній елемент зі стеку, тобто 40. Тепер верхній елемент стає 30.
  11. Використовуйте функцію pop(), щоб видалити верхній елемент зі стеку, тобто 30. Тепер верхній елемент стає 20.
  12. Використовуйте цикл while і функцію empty(), щоб перевірити, чи стек НЕ порожній. ! є оператором NOT.
  13. Друк поточного вмісту стека на консолі.
  14. Викличте функцію pop() у стеку.
  15. Кінець тіла циклу while.
  16. Кінець тіла функції main().

порожній(), розмір(), верх()

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

  • порожній() - перевіряє, порожній стек чи ні.
  • size() - повертає розмір стека, тобто кількість елементів у стеку.
  • top() - отримує доступ до елемента стека вгорі.

СТАТТІ ПО ТЕМІ

Приклад 2:

#include <iostream> 
#include <stack>  
using namespace std;
void createStack(stack <int> mystack)
{
	stack <int> ms = mystack;
	while (!ms.empty())
	{
		cout << '\t' << ms.top();
		ms.pop();
	}
	cout << '\n';
}
int main()
{
	stack <int> st;
	st.push(32);
	st.push(21);
	st.push(39);
	st.push(89);
	st.push(25);

	cout << "The stack st is: ";
	createStack(st);
	cout << "\n st.size() : " << st.size();
	cout << "\n st.top() : " << st.top();
	cout << "\n st.pop() : ";
	st.pop();
	createStack(st);
	return 0;
}

вихід:

порожній(),розмір(),верх()

Ось скріншот коду:

порожній(),розмір(),верх()

Пояснення коду:

  1. Включіть файл заголовка iostream у наш код, щоб використовувати його функції.
  2. Включіть файл заголовка стека в наш код, щоб використовувати його функції.
  3. Включіть простір імен std у нашу програму, щоб використовувати його класи без його виклику.
  4. Створіть функцію createStack, за допомогою якої ми зможемо створити стек mystack. Стек буде містити набір цілих чисел.
  5. Початок тіла функції createStack.
  6. Створіть екземпляр типу даних mystack і назвіть його ms.
  7. Використовуйте цикл while і функцію empty(), щоб перевірити, чи стек порожній.
  8. Початок тіла циклу while.
  9. Використовуйте функцію top(), яка зберігається у верхній частині стека. Символ \t створить нову вкладку.
  10. Використовуйте функцію pop(), щоб видалити елемент у верхній частині стека.
  11. Кінець тіла циклу while.
  12. Надрукуйте порожній рядок на консолі.
  13. Кінець тіла функції createStack.
  14. Виклик функції main(). Логіку програми слід додати в тіло функції main().
  15. Початок тіла функції main().
  16. Створити стековий об’єкт вул.
  17. Використовуйте функцію push(), щоб вставити елемент 32 у стек.
  18. Використовуйте функцію push(), щоб вставити елемент 21 у стек.
  19. Використовуйте функцію push(), щоб вставити елемент 39 у стек.
  20. Використовуйте функцію push(), щоб вставити елемент 89 у стек.
  21. Використовуйте функцію push(), щоб вставити елемент 25 у стек.
  22. Надрукуйте текст на консолі.
  23. Викличте функцію createStack, щоб виконати описані вище операції вставки в стек.
  24. Роздрукуйте розмір стопки на консолі поряд з іншим текстом.
  25. Роздрукуйте елемент у верхній частині стека на консолі.
  26. Надрукуйте текст на консолі.
  27. Видалити елемент у верхній частині стека. Потім він поверне елементи, що залишилися в стеку.
  28. Викличте функцію createStack, щоб виконати наведені вище операції.
  29. Після успішного завершення програма повинна повернути значення.
  30. Кінець тіла функції main().

emplace() і swap()

Це інші вбудовані функції стека:

  • emplace() - конструює, а потім вставляє новий елемент на вершину стека.
  • swap() - обмінює вміст стека вмістом іншого стека.

Приклад 3:

#include <iostream>    
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st1;
	stack<int> st2;

	st1.emplace(12);
	st1.emplace(19);

	st2.emplace(20);
	st2.emplace(23);

	st1.swap(st2);

	cout << "st1 = ";
	while (!st1.empty()) {
		cout << st1.top() << " ";
		st1.pop();
	}

	cout << endl << "st2 = ";
	while (!st2.empty()) {
		cout << st2.top() << " ";
		st2.pop();
	}
}

вихід:

emplace()& swap()

Ось скріншот коду:

emplace()& swap()

Пояснення коду:

  1. Включіть файл заголовка iostream у наш код, щоб використовувати його функції.
  2. Включіть файл заголовка стека в наш код, щоб використовувати його функції.
  3. Включіть файл заголовка cstdlib у наш код, щоб використовувати його функції.
  4. Включіть простір імен std у наш код, щоб використовувати його класи без його виклику.
  5. Виклик функції main(). Логіку програми буде додано в тіло цієї функції.
  6. Оголошіть стек під назвою st1 для зберігання цілочисельних значень.
  7. Оголошіть стек під назвою st2 для зберігання цілочисельних значень.
  8. Використовуйте функцію emplace(), щоб вставити ціле число 12 у стек з іменем st1.
  9. Використовуйте функцію emplace(), щоб вставити ціле число 19 у стек з іменем st1.
  10. Використовуйте функцію emplace(), щоб вставити ціле число 20 у стек з іменем st2.
  11. Використовуйте функцію emplace(), щоб вставити ціле число 23 у стек з іменем st2.
  12. Використовуйте функцію swap(), щоб поміняти вміст двох стеків, st1 і st2. Вміст стека st1 слід перемістити в стек st2. Вміст стека st2 слід перемістити в стек st1.
  13. Надрукуйте текст на консолі.
  14. Використовуйте оператор while і функцію empty(), щоб перевірити, чи стек st1 не порожній.
  15. Вивести на консоль вміст стека st1. ” ” додає простір між елементами стека під час друку їх на консолі.
  16. Виконайте функцію pop() у стеку st1, щоб видалити верхній елемент.
  17. Кінець тіла оператора while.
  18. Надрукуйте текст на консолі. Endl - це a C++ ключове слово для кінцевого рядка. Він переміщує курсор миші до наступного рядка, щоб почати друк звідти.
  19. Використовуйте оператор while і функцію empty(), щоб перевірити, чи стек st2 не порожній.
  20. Вивести на консоль вміст стека st2. ” ” додає простір між елементами стека під час друку їх на консолі.
  21. Виконайте функцію pop() у стеку st2, щоб видалити верхній елемент.
  22. Кінець тіла оператора while.
  23. Кінець тіла функції main().

Стек в STL

STL (стандартна бібліотека шаблонів) містить класи шаблонів, які надають загальні C++ структури даних. Таким чином, стек також може бути реалізований у STL. Ми просто включаємо цю бібліотеку в наш код і використовуємо її для визначення стека.

stack<T> st;

Наведений вище синтаксис оголошує стек st для елементів типу даних T.

Приклад 4:

#include <iostream>      
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st;
	st.push(12);
	st.push(19);
	st.push(20);
	cout << st.top();   
	cout << st.size();  
}

вихід:

Стек в STL

Ось скріншот коду:

Стек в STL

Пояснення коду:

  1. Включіть файл заголовка iostream у наш код, щоб використовувати його функції.
  2. Включіть файл заголовка стека в наш код, щоб використовувати його функції.
  3. Включіть файл заголовка cstdlib у наш код, щоб використовувати його функції.
  4. Включіть простір імен std у наш код, щоб використовувати його класи без його виклику.
  5. Виклик функції main(). Логіку програми слід додати в тіло цієї функції.
  6. Оголошіть стек st для зберігання цілочисельних даних.
  7. Додайте елемент 12 до стека.
  8. Додайте елемент 19 до стека.
  9. Додайте елемент 20 до стека.
  10. Роздрукуйте елемент у верхній частині стека на консолі.
  11. Роздрукуйте розмір стопки на консолі.
  12. Кінець тіла функції main().

Підсумки

  • Стек — це структура даних, яка працює за технологією LIFO (останній прийшов, перший вийшов).
  • std::stack дозволяє додавати та видаляти елементи лише з одного кінця.
  • Клас std::stack є контейнерним адаптером, що містить елементи подібного типу даних.
  • Стек можна створити з різних контейнерів послідовності.
  • Якщо ви не надасте контейнер, за умовчанням використовуватиметься контейнер deque.
  • Функція push() призначена для вставки елементів у стек.
  • Функція pop() призначена для видалення верхнього елемента зі сходинки.
  • Функція empty() призначена для перевірки того, порожній стек чи ні.

Вам може сподобатися: