Класс std::stack<T> представляет стек - структуру данных, которая работает по принципу LIFO (last-in first-out или "последний вошел — первым вышел") — первым всегда извлекается последний добавленный элемент. Стек можно сравнить со стопкой предметов, например, стопкой тарелок - тарелки добавляются сверху, каждая последующая тарелка кладется поверх предыдущей. А если надо взять тарелку, то сначала берется та, которая в самом верху (которую положили самой последней).
Для работы со стеком надо подключать заголовочный файл <stack>
. Определение пустого стека:
#include <iostream> #include <stack> int main() { std::stack<std::string> stack; // пустой стек строк }
С помощью функции size() можно получить количество элементов в стеке, а с помощью функции empty() проверить стек на наличие элементов (если возвращается
true
, то стек пуст):
#include <iostream> #include <stack> 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> 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> 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> 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> 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(); } }