STL. Stack

STL. Stack

Что же такое 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

2 комментария

  • Марго

    Ответить 26.03.2012 01:48

    Вот про стек как раз задачка http://www.fulcrumweb.com.ua/fw/simple_online_interview — как из рекурсии дерево в стек переделать. Подскажите?

  • Topcoder

    Ответить 27.03.2012 01:48

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

    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;
    }

    Не знаю что должно хранится в левом и правом указателе листов, поэтому сделал в них ссылку вершины на саму себя.

Оставить комментарий