Стек std::stack

Класс std::stack<T> представляет стек - структуру данных, которая работает по принципу LIFO (last-in first-out или "последний вошел — первым вышел") — первым всегда извлекается последний добавленный элемент. Стек можно сравнить со стопкой предметов, например, стопкой тарелок - тарелки добавляются сверху, каждая последующая тарелка кладется поверх предыдущей. А если надо взять тарелку, то сначала берется та, которая в самом верху (которую положили самой последней).

Для работы со стеком надо подключать заголовочный файл <stack>. Определение пустого стека:

#include <iostream>
#include <stack>
#include <string>

int main()
{
    std::stack<std::string> stack;	// пустой стек строк
}

Размер стека

С помощью функции size() можно получить количество элементов в стеке, а с помощью функции empty() проверить стек на наличие элементов (если возвращается true, то стек пуст):

#include <iostream>
#include <stack>
#include <string>

int main()
{
    std::stack<std::string> stack;
    if(stack.empty())
    {
        std::cout << "stack is empty" << std::endl;
    }
    std::cout << "stack size: " << stack.size() << std::endl; // stack size: 0
}

добавление элементов

Для добавления в стек применяется функция push(), в которую передается добавляемый элемент:

#include <iostream>
#include <stack>
#include <string>

int main()
{
    std::stack<std::string> stack;
	// добавляем три элемента
    stack.push("Tom");
    stack.push("Bob");
    stack.push("Sam");

	std::cout << "stack size: " << stack.size() << std::endl; // stack size: 3
}

Получение элементов

Мы можем получить только самый верхний элемент стека - для этого применяется функция top():

#include <iostream>
#include <stack>
#include <string>

int main()
{
    std::stack<std::string> stack;
    stack.push("Tom");
    stack.push("Bob");
    stack.push("Sam");
    std::cout << "Top: " << stack.top() << std::endl;   // Top: Sam
}

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

-------
| Sam |
-------
| Bob |
-------
| Tom |
-------

На верхушке стека будет располагаться послдений добавленный элемент. И с помощью функции top() можно получить этот элемент

Удаление элементов

Для удаления элементов применяется функция pop(). Удаление производится в порядке, обратном добавлению:

stack.pop()

Комбинируя эту функцию с функцией top() можно извлечь все элементы стека:

#include <iostream>
#include <stack>
#include <string>

int main()
{
    std::stack<std::string> stack;
    stack.push("Tom");
    stack.push("Bob");
    stack.push("Sam");

    while (!stack.empty())	// пока стек не пуст
    {
        std::cout << stack.top() << std::endl;
        stack.pop();	// извлекаем верхний элемент
    }
}

В данном случае, пока стек не станет пустым, выводим на консоль верхний (последний добавленный) элемент с помощью функции top и затем извлекаем его с помощью функции pop. Консольный вывод программы:

Sam
Bob
Tom

Инициализация деком

Стек можно инициализировать другим стеком или деком (двусторонней очередью):

#include <iostream>
#include <stack>
#include <string>

int main()
{
    std::deque<std::string> users{"Tom", "Sam", "Bob"};
    std::stack<std::string> stack {users};

    while (!stack.empty())
    {
        std::cout << stack.top() << std::endl;
        stack.pop();
    }
}