Кто-то новичок в программировании, вероятно, слышал слово «стек» применительно к автоматическому выделению памяти в C и из повседневной жизни мы все знакомы с тем, что такое очередь. Но что такое стек и очередь применительно к программированию?
Стек — это структура данных (в основном контейнер или средство для хранения данных), которая упорядочивает хранящиеся в ней данные друг над другом. В такой структуре, как стопка книг на изображении выше, можно удалить только те элементы, данные или книгу, которые находятся наверху стопки или стопки. Также проще всего вставить новый фрагмент данных только в верхнюю часть стека, так же как добавить новую книгу в верхнюю часть стопки.
С другой стороны, очередь представляет собой аналогичную структуру данных, в которой данные вводятся с одной стороны, называемой «концом», и удаляются с другой стороны, называемой «передней», в основном это обычная очередь, с которой мы все знакомы.
Из вышеприведенных определений видно, что данные удаляются из стека на основе принципа «последний пришел — первый ушел», что означает, что элемент, только что помещенный на вершину стека, будет удален из него первым, пока очередь работает в режиме ожидания. принцип «первым вошел – первым вышел» (первый человек в очереди первым выходит из нее). Отсюда и использование терминов бухгалтерского учета ФИФО и ЛИФО.
Итак, основное различие между стеком и очередью заключается в способе ввода данных.
Существует множество применений стеков и очередей и множество способов их реализации, таких как использование строк, односвязных списков и двусвязных списков, но я обнаружил, что наиболее универсальными и полезными являются двусвязные списки.
Используя двусвязные списки, можно построить стек на C для интерпретации интерпретируемого языка, такого как python. Стек может легко стать очередью и наоборот.
Например, рассмотрим следующий байт-код Python для простого модуля
3 0 LOAD_CONST 1 (98) 3 LOAD_FAST 0 (a) 6 LOAD_FAST 1 (b) 9 BINARY_ADD 10 BINARY_ADD 11 RETURN_VALUE
Используя стек, первая команда добавляет в стек постоянное значение 98, следующие две также добавляют в стек значения a и b, которые являются входными значениями модуля. Следующая команда добавляет в стек новый элемент, который представляет собой сумму двух верхних элементов стека, т. е. a + b вместо второго сверху, и удаляет верхний элемент, делая это новое значение вершиной стека (TOS).
Теперь в стеке осталось только два элемента: 98 и a+b. Последняя команда добавляет их оба и удаляет верхний элемент, сохраняя новое значение в единственном элементе, оставшемся в стеке. Последняя команда возвращает это значение из модуля python.
Интерпретатор построчно считывает байт-код и выполняет операции, соответствующие командам, используя стек.