Стек в 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 – Тип базового объекта-контейнера.

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

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

• тип значения– Первый параметр шаблона, T. Он обозначает типы элементов.
• тип_контейнера– Второй параметр шаблона, Container. Он обозначает базовый тип контейнера.
• тип_размера– Целочисленный тип без знака.

Operaв стеке

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

• протолкнуть. – Добавляет/помещает элемент в стек.
• поп – Эта функция удаляет/извлекает элемент из стека.
• заглядывать – Возвращает верхний элемент стека, не удаляя его.
• isFull – Проверяет, заполнен ли стек.
• пусто – Проверяет, пуст ли стек.

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

Следующие шаги показывают, как смещается верхняя часть стека при добавлении и удалении элементов:

Шаг 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();
	}
}

Выход:

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

Code Объяснение:

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().

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

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

• пустой()– проверяет, пуст ли стек или нет.
• размер()– возвращает размер стека, то есть количество элементов в стеке.
• Вверх()– осуществляет доступ к элементу стека в верхней части.

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

Выход:

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

Code Объяснение:

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()– создает элемент, а затем вставляет новый элемент в начало стека.
• поменять местами()– обменивается содержимым стека с содержимым другого стека.

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

Выход:

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

Code Объяснение:

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. Напечатайте текст на консоли. Конец - это C++ ключевое слово для конечной строки. Он перемещает курсор мыши на следующую строку, чтобы начать печать оттуда.
19. Используйте оператор while и функцию пустой(), чтобы проверить, не пуст ли стек 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();  
}

Выход:

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

Code Объяснение:

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

Часто задаваемые вопросы (FAQ)