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

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

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

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

В этом руководстве по C++ вы узнаете

• Что такое std::stack?
• Синтаксис стека
• Типы участников
• Операции в стеке
• Реализация стека
• push() и pop()
• пустой(), размер(), верхний()
• emplace() и swap()
• Стек в STL

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

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

template <class Type, class Container = deque<Type> > class stack;

• Тип – Тип элемента, содержащегося в std::stack. Это может быть любой допустимый тип C++ или даже пользовательский тип.
• Контейнер – Тип базового объекта-контейнера.

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

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

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

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

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

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

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

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

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

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

Шаг 4) Затем мы выполнили операцию извлечения, удалив верхний элемент из стека. Элемент 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();
	}
}

Вывод:

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

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

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(), чтобы проверить, НЕ пуст ли стек. ! является оператором НЕ.
13. Печать текущего содержимого стека на консоли.
14. Вызовите функцию pop() в стеке.
15. Конец тела цикла while.
16. Конец тела функции main().

пустой(), размер(), верхний()

Стеки имеют встроенные функции, которые можно использовать для экспериментов со стеком и его значениями. К ним относятся:

• empty() — проверяет, пуст стек или нет.
• 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();
	}
}

Вывод:

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

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

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

Стек в STL

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

stack<T> st; 

Приведенный выше синтаксис объявляет стек st для элементов типа данных T.

Пример 3:

#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();  
}

Вывод:

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

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

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() предназначена для проверки того, пуст стек или нет.