Кто-то новичок в программировании, вероятно, слышал слово «стек» применительно к автоматическому выделению памяти в 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.

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