Стек в C++ STL с примером

Что такое std::stack?

Стек — это структура данных, которая работает на основе метода LIFO (Last In First Out). std::stack позволяет добавлять и удалять элементы только с одного конца.

Класс std::stack — это адаптер контейнера. Объекты-контейнеры содержат данные аналогичного типа. Вы можете создать стек из различных контейнеров последовательностей. Если контейнер не указан, по умолчанию будет использоваться контейнер deque. Адаптеры контейнеров не поддерживают итераторы, поэтому их нельзя использовать для управления данными.

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

Чтобы создать стек, мы должны включить заголовочный файл в нашем коде. Затем мы используем этот синтаксис для определения std::stack:

template <class Type, class Container = deque<Type> > class stack;
  • Тип – Тип элемента, содержащегося в std::stack. Это может быть любой допустимый тип C++ или даже тип, определяемый пользователем.
  • Container – Тип базового объекта-контейнера.

Типы участников

Вот типы членов стека:

  • value_type — первый параметр шаблона, T. Он обозначает типы элементов.
  • Container_type — второй параметр шаблона, Container. Он обозначает базовый тип контейнера.
  • size_type — целочисленный тип без знака.

Операции в стеке

A C + + стек поддерживает следующееwing основные операции:

  • push — добавляет/помещает элемент в стек.
  • pop – удаляет/выталкивает элемент из стека.
  • peek — возвращает верхний элемент стека, не удаляя его.
  • isFull – проверяет, заполнен ли стек.
  • isEmpty – проверяет, пуст ли стек.

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

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

Шаг 1) Изначально у нас есть пустой стек. Вершина пустого стека имеет значение -1.

Шаг 2) Далее мы поместили элемент 5 в стек. Вершина стека будет указывать на элемент 5.

Шаг 3) Далее мы поместили элемент 50 в стек. Вершина стека смещается и указывает на элемент 50.

Шаг 4) Затем мы выполнили операцию извлечения, удалив верхний элемент из стека. Элемент 50 извлекается из стека. Вершина стека теперь указывает на элемент 5.

push() и поп()

Функции 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() и поп()

Вот скриншот кода:

push() и поп()

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

  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 и функцию пустой(), чтобы проверить, НЕ пуст ли стек. ! является оператором НЕ.
  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 и функцию пустой(), чтобы проверить, пуст ли стек.
  8. Начало тела цикла while.
  9. Используйте функцию top(), хранящуюся в верхней части стека. Символ \t создаст новую вкладку.
  10. Используйте функцию pop(), чтобы удалить элемент наверху стека.
  11. Конец тела цикла while.
  12. Напечатайте пустую строку на консоли.
  13. Конец тела функции createStack.
  14. Вызовите функцию main(). Логику программы следует добавить в тело функции main().
  15. Начало тела функции main().
  16. Создайте объект стека st.
  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() — обменивает содержимое стека с содержимым другого стека.

Пример 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();
	}
}

Вывод:

вставить() и поменять()

Вот скриншот кода:

вставить() и поменять()

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

  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 и функцию пустой(), чтобы проверить, не пуст ли стек st1.
  15. Выведите содержимое стека st1 на консоль. Знак « » добавляет пространство между элементами стека при их печати на консоли.
  16. Выполните функцию pop() в стеке st1, чтобы удалить верхний элемент.
  17. Конец тела оператора while.
  18. Напечатайте текст на консоли. Endl — это ключевое слово C++ для обозначения конечной строки. Он перемещает курсор мыши на следующую строку, чтобы начать печать оттуда.
  19. Используйте оператор while и функцию пустой(), чтобы проверить, не пуст ли стек st2.
  20. Выведите содержимое стека st2 на консоль. Знак « » добавляет пространство между элементами стека при их печати на консоли.
  21. Выполните функцию pop() в стеке st2, чтобы удалить верхний элемент.
  22. Конец тела оператора while.
  23. Конец тела функции main().

Стек в STL

STL (стандартная библиотека шаблонов) поставляется с классами шаблонов, которые предоставляют общие структуры данных C++. Следовательно, стек также можно реализовать в STL. Мы просто включаем эту библиотеку в наш код и используем ее для определения стека.

stack<T> st; 

Приведенный выше синтаксис declares стек 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() предназначена для удаления верхнего элемента с шага.
  • Функция пустой() предназначена для проверки того, пуст ли стек или нет.