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
Понравилась новость? Добавь в закладки!
Хочешь получать свежие новости? Подпишись на обновления с сайта!
Рекомендуем посмотреть:
#1 | написал: Марго | 26 марта 2012 18:27 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0

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


#2 | написал: Topcoder | 27 марта 2012 00:43 | ICQ: | Пользователь offline

Группа: Администраторы
Публикаций: 14
Комментариев: 9

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

queue <TreeNode*> 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;



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


Добавление комментария

Ваше Имя:
Ваш E-Mail:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Вставка исходного кода Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера

Введите два слова, показанных на изображении: