Читайте также:
|
Опубликовано 16.05.2013 автором Dauren
Что такое структура данных?
Это способ хранения данных по особым правилам, использующий функции для доступа к ним. Одним из структур данных является стек (англ. stack - стопка).
Стек немного схож с ханойской башней. Вкратце вся суть этой игры такова:
§ Имеется доска с тремя стержнями;
§ На первом находятся восемь колец упорядоченных по размеру, т.е. получается своеобразная пирамида; 
§ Нужно перенести кольца с первого стержня на третий, притом кольцо может лежать лишь на доске или же на кольце большего размера.
Теперь более формально.
Стек это — структура данных, использующая следующие функции:
§ push (x): добавить элемент x на самый верх стека;
§ top (): возвратить значение самого верхнего элемента;
§ pop (): удалить самый верхний элемент;
Получается некий шампур (т.е. стек), на который мы нанизываем еду (т.е информацию).
Cтек уже реализован в С++, в качестве контейнера. Перечислим все его функции:
§ stack < a > b - создать стек типа b с именем a;
§ b.push (x) — добавить в стек b элемент x (x должен быть того же типа, что и сам стек);
§ b.pop () - удалить самый верхний элемент стека;
§ b.top () — возвратить значение самого верхнего элемента стека;
§ b.size () - возвратить количество элементов в стеке;
§ b.empty () - true, если стек пуст, иначе — false;
Пример работы со стеком:
| stack < int > st; // создание стека типа integer в c++ st.push (1); // [1] st.push (2); // [1][2] st.push (3); // [1][2][3] cout << st.top () << "\n"; // [1][2]->[3]<-, выводим "3" st.push (4); // [1][2][3][4] cout << st.top () << "\n"; // [1][2][3]->[4]<-, выводим "4" st.pop (); // [1][2][3] st.pop (); // [1][2] st.pop (); // [1] cout << st.top () << "\n"; // ->[1]<-, выводим "1" |
Но ведь так не интересно, давайте напишем свой стек, хотя бы просто для int-ов. Сразу выкладываю код, объяснения как обычно там же:
| # include <iostream> # include <cstdlib> # include <cstdio> using namespace std; int st[1000]; // наш будущий стек int st_size; // размер стека, изначально положим равным нулю void push (int x) { st[++st_size] = x; // увеличиваем размер стека и сразу записываем в него наш элемент } void pop () { st[st_size--] = 0; // обнуляем верхний элемент и уменьшаем размер стека } int top () { return st[st_size]; // возвращаем значение самого верхнего элемента } int size () { return st_size; // возвращаем размер стека } bool empty () { if (st_size >= 1) // проверяем, есть ли в стеке хоть 1 элемент return true; return false; // иначе возвращаем false } int main () { push (1); // [1] push (2); // [1][2] push (3); // [1][2][3] cout << top () << "\n"; // [1][2]->[3]<-, выводим "3" push (4); // [1][2][3][4] cout << top () << "\n"; // [1][2][3]->[4]<-, выводим "4" pop (); // [1][2][3] pop (); // [1][2] pop (); // [1] cout << top () << "\n"; // ->[1]<-, выводим "1" system ("pause"); return 0; } |
Теперь, разобравшись с теорией, поговорим об использовании стека.
Вы когда-нибудь слышали о обратной польской нотации (далее ОПН)? Если да, то наверняка слышали и о стековой машине, используемой для решения ОПН.
В простых словах, ОПН это — вид записи арифметических выражений, не использующий скобок для указания порядка действий. Вместо скобок, для указания порядка действий, используется стек. Также в нем знаки стоят после самих чисел (т.е «2 + 2″ в простой записи это — «2 2 +» в ОПН).
Для полного понимания пример:
X3 * (2xy — 36) тоже самое, что и X X X * * 2 X Y * * 36 — *
Любой число (в нашем случае X или Y) значит добавление в стек этого числа
Любой знак (арифметический или бинарный, о которых подробнее писалось тут) значит произвести операцию, связанную с этим знаком, над двумя верхними числами в стеке, и заменить эти два числа результатом. Для лучшего понимания разбор нашего примера (X X X * * 2 X Y * * 36 — *):
§ [стек до операции] -> [после]
§ 1) [] -> [X]
§ 2) [X] -> [X,X]
§ 3) [X,X] -> [X,X,X]
§ 4) [X,X,X] -> [X,X2]
§ 5) [X,X2] -> [X3]
§ 6) [X3] -> [X3,2]
§ 7) [X3,2] -> [X3,2,X]
§ 8) [X3,2,X] -> [X3,2,X,Y]
§ 9) [X3,2,X,Y] -> [X3,2,XY]
§ 10) [X3,2,XY] -> [X3,2XY]
§ 11) [X3,2XY] -> [X3,2XY,36]
§ 12) [X3,2XY,36] -> [X3,2XY-36]
§ 13) [X3,2XY-36] -> [X3*(2XY-36)]
В качестве закрепления темы, советую написать стековую машину реализующую решение ОПН. Спасибо за внимание, удачи в начинаниях.
Дата добавления: 2015-09-10; просмотров: 17 | Поможем написать вашу работу | Нарушение авторских прав |