Про стеки

[Minority]

Немножко не про математику.. Скорее общеобразовательное про компьютер. Изначально было в форме диалога, поэтому длинно. Переделывать не стала, т.к. мне кажется, что так все воспринимается лучше.

Стеки

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

некоторый адрес памяти. когда ты работаешь с отладчиком, для тебя это - строка. но все, что мы видим, ведь на самом участок памяти компьютера. и при запуске программы процессор ей выделяет участок ОП

Comments

[chebur12]

интересно но ничерта не понятно про что

[Minority]

chebur12

даа? =( вот жалко-то... Наверное, все-таки программирование немножко надо знать =(

[chebur12]

Minority угу... тут слэнга много... может составишь словарик... если время есть.....?

[Minority]

chebur12

ой.. сейчас нету. скорее сил, а не времени. но попробую заняться. хотя было бы проще, если бы мне составили список того, что надо объяснить

[Disprein]

В целом — Ваше понимание чувствуется, разъяснительную работу провели — дай бог каждому, алгоритмы знаете — очень приятно видеть, но не будь я программистом — ничего бы не понял, наверное)



Я так понимаю, речь шла о конкретной реализации стека — реализации на массиве. В классическом понимании стека как абстрактной структуры данных чтение любого элемента стека запрещено, есть только операции добавления на вершину, удаления с вершины и проверки стека на пустоту.



При запуске программы параметры не записываются в стек системы. По крайней мере, в системах Windows и Unix. Там вообще нет понятия стека системы. Есть стек процессора (машинный стек). Но если речь о Форт-машинах — то там действительно так, и я проникаюсь к Вам глубоким уважением. Серьезно.



Про то, что компьютер знает только обратную польскую запись, тоже не очень хорошо. Это верно только опять-таки только для Форт-машин, а обычные двухадресные машины (представителем которых является и семейство Intel x86) производят арифметические операции как раз без стека. Стек может понадобиться только для разбора арифметического выражения при трансляции с языков высокого уровня.



Про баланс скобок — хороший пример.

Про ПОЛИЗ — хорошо, но сложно, неподготовленному будет очень тяжело понять.

Применение стека в рекурсии — тоже хороший пример, но его по-настоящему осознают только те, кто понимает реализацию локальных данных и параметров процедур на уровне ассемблера.

Про стек для хранения точек возврата — хорошо и наглядно даже для изучающего программирование первый год, а главное — тут действительно видно, каким образом стек приносит пользу)



Свои пять копеек: стеки нужны там, где присутствует вложенность. И неважно, вложенность скобок или вызовов функций. Именно во вложенности — природа стека.



P.S. Да, и что такое "линейный список, отображенный в векторную память"? Дейкстра нервно курит?) Вам неопытный товарищ вопрос задал, а Вы его такими словами приложили... )

[Minority]

Disprein

Ну наверное, сказалось еще то, что человек тоже не совсем уж был несведующим в программировании...



В классическом понимании стека как абстрактной структуры данных чтение любого элемента стека запрещено, есть только операции добавления на вершину, удаления с вершины и проверки стека на пустоту.

а нас учат, что вот эта самая описанная Вами структура называется магазином...



Стек может понадобиться только для разбора арифметического выражения при трансляции с языков высокого уровня.

ну вот об этой трансляции я и говорила... А вообще-то, понятное дело, что все происходит несколько иначе. Но для этого мне бы пришлось отойти от нашей темы + вспоминать СПТ и СФТ, которые я могу посчитать только с поддержкой учебников..



P.S. Да, и что такое "линейный список, отображенный в векторную память"? Дейкстра нервно курит?) Вам неопытный товарищ вопрос задал, а Вы его такими словами приложили... )

А выдала на автомате. Это уже потом я поняла, что перебор вышел. Но все равно основу-то он понял: по какому правилу с ним работать.

[Disprein]

Minority, о, как давно я не слышал термина "магазин"...) Правильно, в СССР был магазин, а за рубежом — stack, и означали они одно и то же. Но мне казалось, что в терминологии стеки полностью вытеснили магазины... Оказывается, нет, советская информатика продолжает жить)

[Minority]

Disprein

Теперь мы друг друга поняли? =)

[Disprein]

Вполне)

[chebur12]

иномирье

[Дилетант]

Minority, Disprein позвольте пару слов вставить динозавру от программирования )))



Что такое Форт-машины? Мне очень-очень интересно! На заре юности я ходила в КРУЖОК по Форту. Там мы и учили всё, так славно описанное Minority )))



А после этого что-то ни разу мне с этим сталкиваться не довелось...

Спасибо! Здорово! )))



Термин "магазин" вроде больше похож на термин "очередь" чем на "стек"? Нет? То есть я была еще в СССР, когда у нас были стеки и очереди. А вот очереди и магазины, что-то плохо представляю )))

[Disprein]

Дилетант, Форт-машины, они же стековые машины, они же безадресные машины — это машины, в системе команд которых арифметические команды не имеют операндов (все операнды берутся со стека и результат кладется обратно на стек). Форт-машинами их называют потому, что Форт — наиболее известный язык программирования для таких машин. Идея таких машин раньше была популярна, потому что их было легче реализовывать аппаратно, и работали они быстрее. А вот программировать под них сложнее.

Вообще я слышал, что Форт-процессоры применяли в каких-то портативных устройствах, но сейчас, мне кажется, эта ветвь развития вычислительной техники окончательно свернулась.



"Магазин" имеется в виду оружейный.) В смысле, не тот, в котором оружие продают, а тот, который вставляют в автомат. Патроны в магазин вставляют сверху, и первым в ствол попадает тот патрон, который лежал в магазине на самом верху. То есть тот же стек.



В СССР все хотели сделать свое, и терминологию тоже. Поэтому и языки программирования были с русскими ключевыми словами, и стеки назывались магазинами (назвать stack стопкой не позволяли особенности русского менталитета), и компьютеры — ЭВМ, и мышь — графическим манипулятором, и плоттер — графопостроителем.

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

[Дилетант]

Disprein )))) Спасибо за ликбез )))

Про Форт-машины я оказывается кое-что знаю )))))) Только что-то название не отложилось в памяти ))))

"Магазин" вчера так и подумала про оружейный, но уже потом )))))

А насчет стека — мои учителя говорили, что метафора тут не "стопочная")) Они утверждали, что это нечто типа полой трубки (трости, стека), в которую что-то кладут, а потом вытаскивают.

Первым-пришел-последним-ушел.



А насчет программирования на Форте — с огромной ностальгией вспоминаю то время! ))))

Вот уж где мозги сворачивались, и потом уж никак не разворачивались ))))