На этом шаге мы рассмотрим, что предствляют собой стек и очередь.
Рекурсия очень полезна и удобна, когда для реализации алгоритма требуется стек - линейная структура данных, моделирующая кучу объектов, которые могут добавляться или удаляться в строго определённом порядке. А именно: при добавлении элемент помещается на вершину стека, тогда как единственным элементом, который можно удалить из стека, является тот, что находится на вершине стека, как показано на рисунке 1(a).
Рис.1. Структуры данных стек и очередь
Поэтому такая структура данных называется магазином или структурой, отвечающей правилу LIFO.
Last In, First Out – последним вошёл, первым вышел.
Операции добавления и удаления элементов стека, в нашем случае растущего вниз, называются push (втолкнуть) и pop (вытолкнуть) соответственно. В отличие от стека, родственная ему структура данных очередь (queue) отвечает правилу FIFO, моделируя очередь ожидания, как показано на рисунке 1(b).
First In, First Out – первым вошёл, первым вышел.
Новый элемент добавляется в конец очереди, а удаляется из неё самый первый элемент. Эти операции обозначаются как enqueue (в очередь) и dequeue (из очереди) соответственно.
На нижнем уровне исполнения кода вызовы подпрограмм и возвраты из них реализуются в памяти посредством специального стека, именуемого программным стеком (program stack), управляющим стеком (control stack), стеком вызовов (call stack) или просто стеком. И хотя он скрыт в языках программирования высокого уровня, представлять его устройство чрезвычайно важно для понимания механизма рекурсии.
На следующем шаге мы рассмотрим стековые кадры.
