Немножко не про математику.. Скорее общеобразовательное про компьютер. Изначально было в форме диалога, поэтому длинно. Переделывать не стала, т.к. мне кажется, что так все воспринимается лучше.
Стеки
Erlang
слушай, объясни, что такое стек
и что из него удаляют и что в него добавляют)))
Minority
э... тебе это так важно знать? сейчас... подожди.. напишу
Erlang
важно)
Minority
Стек - это линейный список, отображенный в векторную память, в котором можно выполнять следующие операции:
1. добавлять в "верхушку"
2. удалять из "верхушки"
3. чтение любого элемента без удаления.
Работа со стеком осуществляется по правилу LIFO (Last in, first out, т.е. последний пришел - первый ушел)
Erlang
понял.
Erlang
так. а ты можешь привести работающий пример использования стека?
Minority
например, когда ты запускаешь программу, ее параметры записываются в стек системы
Erlang
а почему они могут извлекаться только по принципу lifo?
Minority
потому что так организована структура. это искуственно созданные людьми правила.
Erlang
а это логически объяснимо?
Minority
а, тебе хочется понять, в каких случаях это надо применять?
Erlang
да
Minority
ну вот например знаешь, как представляются арифметические выражения в памяти компьютера?
Erlang
как?
Minority
в польской инверсной записи. знаешь такую?
Erlang
нет)
Minority
(a+b)*c+d*e -> ab+c*de*+
Minority
т.е. сначала записывается два операнда, после этого - знак операции, которую надо с ними выполнить и т.д.
Erlang
понял
так, дальше про стеки
Minority
как известно, есть 10 категорий людей: 1 - которые знают двоичную арифметику 10. которые не знают =)
Erlang
)))))))
Minority
так вот, польскую инверсную запись знают единицы
а компьютер только ее и знает))
Erlang
почему применяется она и как это связано со стеком?
Minority
допустим, пользователь вводит (2+3)*3
входная строка обрабатывается так:
0. в стек записывается (
1. записывается 2 в ячейку памяти
2. операция записывается в стек.
3. записывается 3 в другую ячейку памяти
4. встретили ) -> из стека выталкивается "+" с открывающеся скобкой, "+" применяется по отношению к 2 и 3.
5. результат операции записывается в первую ячейку памяти.
6. * записывается в стек
7. 3 - в ячейку памяти
8. * выталкивается из стека, применяется по отношению к (2+3) и 3
9. стек пуст, строка закончилась, поиск завершен.
на более сложных выражениях может быть так, что в стеке сразу очень много разных элементов
Erlang
ага, сразу понял. спасибо большое
Minority
еще стек применяется для проверки баланса скобок в арифметическом выражении
Minority
поступила "(" - записали в стек, поступила ")" - удалили один элемент из стека.
если удалять нечего или в конце стек не пуст, значит баланс нарушен
Erlang
ясно... вот я темнота
Minority
почему?
Erlang
ничего не знал этого
Minority
ну тебе этого не надо было знать, очевидно
Erlang
но интересно
Minority
еще стеки, очереди необходимы для создания рекурсии, обхода дерева...
Erlang
да, могу понять теперь, почему
Minority
а рекурсия, думаешь, как работает?
Erlang
ну, вызов функцией самой себя при заданных условиях
Minority
это сама суть рекурсии. А вот что происходит: при вызове подпрограммы из самой себя формируется стек, в который записывается точка возврата в подпрограмму и с какими параметрами она была вызвана, чтобы потом, после вызова, программа смогла вернуться к самому первому, изначальному вызову
Erlang
угу.
Minority
кстати, то же самое происходит и вообще при любом вызове подпрограммы... основная программа записывает точку возврата и параметры.)))
Erlang
а точка в каком виде записывается?
Minority
некоторый адрес памяти. когда ты работаешь с отладчиком, для тебя это - строка. но все, что мы видим, ведь на самом участок памяти компьютера. и при запуске программы процессор ей выделяет участок ОП
Про стеки
Немножко не про математику.. Скорее общеобразовательное про компьютер. Изначально было в форме диалога, поэтому длинно. Переделывать не стала, т.к. мне кажется, что так все воспринимается лучше.
Стеки
Стеки