Что же такое STL. STL (Standard Template Library) или стандартная библиотека шаблонов — это встроенный в язык набор алгоритмов и структур данных. То есть проще говоря, вместо того, что бы писать длинные алгоритмы самому, как вам пришлось бы это делать например на паскале, вы можете воспользоваться уже готовым алгоритмом и написать его в одну строчку.
Итак, что же такое структура данных Stack (Читается как Стэк)? Чтобы было проще понять, представьте стопку книг. Если вы хотите положить книгу в стопку, то вы кладете ее наверх. А если хотите взять книгу, то сначала берете верхнюю. Вот стек делает то же самое.
Чтобы начать пользоваться стеком, нужно подключить соответствующую библиотеку. То есть написать
#include <stack>
Объявить стек можно там же где и различные переменные или массивы — то есть практически везде.
Для этого пишем stack name; Например:
stack <int> st; // — получился стек st, состоящий из целых значений.
Стек поддерживает несколько функций. А именно:
1) Push()
Функция push() ставит значение на вершину стека. Например:
st.push(1); // — на вершине число 1
st.push(2); // — на вершине число 2
st.push(3); // — на вершине число 3
2) Pop()
Функция pop() удаляет значение с вершины, то есть удаляет последний элемент. Используя предыдущий пример:
// — изначально стек 123
st.pop(); // осталось 12
st.pop(); // осталось 1
3) Top()
Функция top() получает значение верхнего элемента, не удаляя его.
// изначально стек 123
int a = st.top(); // a = 3;
4) Size()
Функция size() возвращает количество элементов в стеке.
// изначально стек 12121
int a = st.size(); // a = 5;
5) Empty()
Булева функция empty() дает понять пуст стек или нет. Возвращает true если стек пуст.
if (st.empty())
cout << «Stack is empty»;
else
cout << st.top();
// Программа выведет верхний элемент если он есть, иначе выведет сообщение о том, что стек пуст.
Полный текст программы, а которой я объединил все вышесказанное(вывод осуществляется в файл a.out):
#include <iostream>
#include <stack>using namespace std;
stack <int> st;
int main() {
freopen(«a.out», «w», stdout);for (int i = 0; i < 5; i++)
st.push(i);cout << st.size() << endl;
if (!st.empty())
cout << «Stack has some elements» << endl;for (int i = 0; i < 5; i++) {
cout << st.top() << » «;
st.pop();
}if (st.empty())
cout << endl << «Stack is empty»;return 0;
}
В файле a.out будет записано
5 Stack has some elements 4 3 2 1 0 Stack is empty
Вот про стек как раз задачка http://www.fulcrumweb.com.ua/fw/simple_online_interview — как из рекурсии дерево в стек переделать. Подскажите?
Задачка не на стек, а на очередь) Ведь на каждом шаге нужно извлекать элемент, ближайший к корню, а он будет в глубене структуры и достать его может только очередь. Сама задачка решается вот так примерно:
queue q;
bool SearchValue(TreeNode * root, int search_value) {
q.push(root);
while (!q.empty()) {
TreeNode* x = q.front();
q.pop();
if (x->value == search_value)
return true;
else {
if (x->left != x) q.push(x->left);
if (x->right != x) q.push(x->right);
}
}
return false;
}
Не знаю что должно хранится в левом и правом указателе листов, поэтому сделал в них ссылку вершины на саму себя.