Computational thinking and Problem-solving · ⁨Вычислительное мышление и решение задач⁩

Поиск находит целевое значение в наборе данных (часто в массиве) и возвращает его позицию или сообщение «не найдено».

Линейный поиск

Линейный поиск проходит от начала до конца, сравнивая каждый элемент с целевым:

FOR i ← 1 TO n
    IF A[i] = target THEN
        RETURN i
    ENDIF
NEXT i
RETURN -1   // not found

Подготовка не требуется, поэтому он работает с любым списком. Худший случай O($n$) (цель в конце или отсутствует); лучший случай 1 сравнение. Используйте его для неотсортированных данных или малых списков. (Возвращаемое -1 является сигнальным значением — невозможной позицией, означающей «не найдено»; вызывающая программа проверяет IF result = -1.)

Версия для экзамена. В задании Paper 3 требуется дополнить линейный поиск, написанный с использованием флага и цикла WHILE, а в Paper 4 — написать функцию, возвращающую индекс или счетчик. Оба варианта выглядят так:

FUNCTION LinearSearch(Data : ARRAY OF INTEGER, Target : INTEGER) RETURNS INTEGER
    DECLARE Index, Count : INTEGER
    Count ← 0
    FOR Index ← 1 TO 100
        IF Data[Index] = Target THEN
            Count ← Count + 1
        ENDIF
    NEXT Index
    RETURN Count          // how many times Target occurs; 0 means not found
ENDFUNCTION

Чтобы остановиться на первом совпадении, используйте цикл WHILE Index <= 100 AND NOT Found, который устанавливает Found ← TRUE и запоминает индекс. Баллы начисляются за проход по каждому элементу, сравнение и то, что возвращается при отсутствии значения.

Бинарный поиск

Бинарный поиск требует, чтобы данные были отсортированы. Посмотрите на средний элемент; если он целевой — готово; если цель меньше, ищите в левой половине, иначе в правой — уменьшая диапазон вдвое на каждом шаге:

low ← 1
high ← n
WHILE low <= high DO
    mid ← (low + high) DIV 2
    IF A[mid] = target THEN
        RETURN mid
    ENDIF
    IF A[mid] < target THEN
        low ← mid + 1
    ELSE
        high ← mid - 1
    ENDIF
ENDWHILE
RETURN -1

Худший случай O($\log_{2} n$) — для миллиона элементов около 20 сравнений. Гораздо быстрее линейного поиска на больших отсортированных массивах, но сначала нужно отсортировать (однократная стоимость O($n \log n$)), что оправдано, если поиск выполняется много раз.

«Укажите условие, необходимое для бинарного поиска.» Данные должны быть упорядочены (отсортированы по возрастанию или убыванию по ключу поиска). «Опишите, как выполнить бинарный поиск» (три балла): (1) найдите средний элемент списка (или текущего диапазона) и сравните его с целевым; (2) если совпадает, поиск завершается; если цель меньше, повторите для нижней половины, если больше — для верхней половины; (3) продолжайте делить пополам диапазон, пока элемент не будет найден или диапазон не опустеет, что означает отсутствие элемента.

Версия для экзамена, с границами и флагом, — это та, которую следует воспроизвести, когда просят дополнить алгоритм:

DECLARE Lower, Upper, Mid : INTEGER
DECLARE Found : BOOLEAN
Lower ← 0
Upper ← 99
Found ← FALSE
WHILE Lower <= Upper AND NOT Found
    Mid ← (Lower + Upper) DIV 2
    IF Names[Mid] = Target THEN
        Found ← TRUE
    ELSE
        IF Names[Mid] < Target THEN
            Lower ← Mid + 1
        ELSE
            Upper ← Mid - 1
        ENDIF
    ENDIF
ENDWHILE
IF Found THEN
    OUTPUT Mid
ELSE
    OUTPUT "Not found"
ENDIF

"Объясните, как производительность меняется с количеством элементов." Каждое сравнение сокращает количество оставшихся элементов вдвое, поэтому максимальное число сравнений составляет около $\log_{2} n$: удвоение размера списка добавляет лишь одно дополнительное сравнение. Это O($\log n$). «Сравните линейный и бинарный поиск»: линейный поиск требует до $n$ сравнений (O($n$)) и в среднем половину этого, но работает на неотсортированных данных; бинарный поиск требует максимум $\log_{2} n$ (O($\log n$)) и значительно быстрее для больших списков, но данные должны быть предварительно отсортированы, и необходимо произвольное обращение к среднему элементу (массив, а не связный список). Для $1000$ элементов: $1000$ против $10$ сравнений.

Пузырьковая сортировка

Пузырьковая сортировка многократно проходит по массиву, меняя местами соседние пары, стоящие в неправильном порядке, так что наибольшие элементы «всплывают» к концу при каждом проходе:

FOR pass ← 1 TO n - 1
    swapped ← FALSE
    FOR i ← 1 TO n - pass
        IF A[i] > A[i + 1] THEN
            temp ← A[i]
            A[i] ← A[i + 1]
            A[i + 1] ← temp
            swapped ← TRUE
        ENDIF
    NEXT i
    IF swapped = FALSE THEN      // already sorted
        EXIT FOR
    ENDIF
NEXT pass

Лучший случай O($n$) (уже отсортировано, с ранним выходом); средний/худший O($n^{2}$). Проста, но медленна для больших $n$.

Сортировка вставками

Сортировка вставками формирует отсортированный префикс слева, вставляя каждый новый элемент на место путем сдвига бо́льших элементов вправо:

FOR i ← 2 TO n
    key ← A[i]
    j ← i - 1
    WHILE j >= 1 AND A[j] > key DO
        A[j + 1] ← A[j]
        j ← j - 1
    ENDWHILE
    A[j + 1] ← key
NEXT i

Лучший случай O($n$) (уже отсортировано); худший O($n^{2}$). Хороша для малых или почти отсортированных массивов. Сортирует на месте и является стабильной (сохраняет порядок равных элементов).

Отслеживание сортировки

Типичная задача — показать массив после каждого внешнего прохода. Для [D, T, H, R] со сортировкой вставками: проход 1 (ключ T) без изменений; проход 2 (ключ H) → [D, H, T, R]; проход 3 (ключ R) → [D, H, R, T].

Написание сортировки с нуля. Задание «Запишите псевдокод для сортировки DataArray[1:1000] по возрастанию» решается полной сортировкой пузырьком с флагом раннего выхода или сортировкой вставками, объявленной и отступленной; оба варианта получают полный балл, если работают для любого входа:

DECLARE Pass, Index, Temp : INTEGER
DECLARE Swapped : BOOLEAN
Pass ← 1
REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO 1000 - Pass
        IF DataArray[Index] > DataArray[Index + 1] THEN
            Temp ← DataArray[Index]
            DataArray[Index] ← DataArray[Index + 1]
            DataArray[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    Pass ← Pass + 1
UNTIL Swapped = FALSE OR Pass = 1000

Для сортировки по убыванию замените > на <; для сортировки записей или двумерного массива 2D по одному полю сравнивайте это поле, но меняйте местами всю запись (или каждый столбец). Если просят написать сортировку вставками «выполняющую ту же задачу», что и заданная сортировка пузырьком, сохраните то же имя массива и направление, воспроизведите описанную выше сортировку вставками, изменив знак сравнения на обратный, если порядок убывающий.

"Опишите два способа, которыми данные влияют на производительность сортировки" (два балла). (1) Количество элементов: алгоритм $O(n^{2})$ требует в четыре раза больше времени для вдвое большего количества элементов. (2) Насколько данные уже упорядочены: пузырьковая сортировка с флагом или сортировка вставками завершается за один проход по уже отсортированным данным ($O(n)$) и выполняет наибольшую работу на данных, расположенных в обратном порядке; количество обменов зависит от количества неупорядоченных пар. (Также принимается: диапазон или количество дублирующихся значений, а также то, являются ли элементы крупными записями, перемещение которых обходится дорого.) Пузырьковая сортировка и сортировка вставками имеют сложность O($n^{2}$) в худшем и среднем случаях и O($n$) в лучшем; быстрая сортировка и слиянием имеют O($n \log n$), именно поэтому они используются для больших объемов данных.

Абстрактные типы данных (ADT) из Темы 10 используются во многих алгоритмах: стек обеспечивает обход в глубину и функцию отмены; очередь обеспечивает обход в ширину и порядок печати; связный список позволяет данным динамически расширяться и уменьшаться.

ADT могут строиться на основе других ADT, а не только массивов: очередь из двух стеков; стек из связного списка (push = добавить узел в начало узла); очередь из связного списка с указателями на голову и хвост; бинарное дерево из узлов с двумя указателями на потомков; словарь хранит пары ключ→значение (часто на хеш-таблице). Такое построение分层 (layering) разделяет ответственность — алгоритму, использующему ADT, не нужно знать, как он реализован.

ADT, которые требуется описать и реализовать на экзамене

Стек (last in, first out): элементы добавляются (push) и удаляются (pop) с одного конца — вершины; указатель TopOfStack хранит индекс верхнего элемента. Реализуется с помощью массива и одного указателя: push проверяет, что стек не полон, увеличивает указатель и сохраняет элемент; pop проверяет, что стек не пуст, возвращает верхний элемент и уменьшает указатель.

FUNCTION Push(Item : INTEGER) RETURNS BOOLEAN
    IF TopOfStack = 9 THEN      // full (array 0 to 9)
        RETURN FALSE
    ENDIF
    TopOfStack ← TopOfStack + 1
    StackData[TopOfStack] ← Item
    RETURN TRUE
ENDFUNCTION
FUNCTION Pop() RETURNS INTEGER
    IF TopOfStack = -1 THEN      // empty
        RETURN -1
    ENDIF
    TopOfStack ← TopOfStack - 1
    RETURN StackData[TopOfStack + 1]
ENDFUNCTION

Очередь (first in, first out): элементы добавляются в хвост (enqueue) и покидают из головы (dequeue); два указателя и счетчик. В линейной очереди указатель головы смещается по массиву до тех пор, пока пространство в начале не будет потеряно; циклическая очередь оборачивает оба указателя через MOD, благодаря чему каждая ячейка используется повторно.

FUNCTION Enqueue(Item : STRING) RETURNS BOOLEAN
    IF Count = 6 THEN      // full
        RETURN FALSE
    ENDIF
    Rear ← (Rear + 1) MOD 6
    QueueArray[Rear] ← Item
    Count ← Count + 1
    RETURN TRUE
ENDFUNCTION
FUNCTION Dequeue() RETURNS STRING
    IF Count = 0 THEN      // empty
        RETURN ""
    ENDIF
    DECLARE Item : STRING
    Item ← QueueArray[Front]
    Front ← (Front + 1) MOD 6
    Count ← Count - 1
    RETURN Item
ENDFUNCTION

Связный список: последовательность узлов, каждый из которых содержит элемент данных и указатель на следующий узел; указатель начала указывает на первый узел, а нулевой указатель (0 или $-1$) обозначает конец списка. При реализации на массиве два параллельных массива хранят данные и указатели, а неиспользованные ячейки соединяются в свободный список, чтобы при вставке можно было определить место для нового узла.

FUNCTION FindInList(Target : STRING) RETURNS INTEGER   // index, or 0 if absent
    DECLARE Current : INTEGER
    Current ← Start
    WHILE Current <> 0
        IF Data[Current] = Target THEN
            RETURN Current
        ENDIF
        Current ← Pointer[Current]
    ENDWHILE
    RETURN 0
ENDFUNCTION

Для вставки в упорядоченный список: возьмите первую свободную ячейку (NewNode ← FreeList, FreeList ← Pointer[FreeList]), сохраните элемент, затем пройдите по списку со значениями Previous и Current, пока не встретите Data[Current] > Item или конец; установите Pointer[NewNode] ← Current и Pointer[Previous] ← NewNode (или Start ← NewNode, если вставка происходит в начало). Для удаления пересоедините предыдущий узел, минуя удаленный, и верните ячейку в свободный список.

Двоичное дерево: узел корня, каждый узел содержит данные, левый указатель на поддерево меньших значений и правый указатель на поддерево бо́льших значений. Реализуется как 2-мерный массив (или три 1-мерных массива) Tree[Index, 0..2] для левого указателя, данных, правого указателя, с указателем корня и указателем следующего свободного элемента.

FUNCTION FindInTree(Target : INTEGER) RETURNS INTEGER   // index, or -1
    DECLARE Current : INTEGER
    Current ← Root
    WHILE Current <> -1
        IF Tree[Current, 1] = Target THEN
            RETURN Current
        ENDIF
        IF Target < Tree[Current, 1] THEN
            Current ← Tree[Current, 0]      // go left
        ELSE
            Current ← Tree[Current, 2]      // go right
        ENDIF
    ENDWHILE
    RETURN -1
ENDFUNCTION

Для вставки: сохраните элемент в следующую свободную ячейку, установив оба указателя равными $-1$; если дерево пусто, сделайте его корнем; иначе спускайтесь от корня, выбирая левый или правый путь в зависимости от сравнения, пока указатель, по которому следовало бы перейти, не станет $-1$, и установите этот указатель на новый узел. ADT на основе другого ADT: стек — это связный список, где push и pop работают с начала; очередь — это связный список с указателями начала и конца; очередь можно построить из двух стеков (push в один, pop из другого, перемещая все элементы, когда второй становится пустым); узлы бинарного дерева представляют собой записи или объекты, связанные указателями, поэтому оно строится на основе связанной структуры узлов. Укажите, какие операции нового ADT соответствуют операциям старого.

Сложность по времени

Временная сложность показывает, как время выполнения растет с увеличением размера входных данных $n$. Записывается в нотации Big-O (доминирующий член): O(1) — константная, O($\log n$) — бинарный поиск, O($n$) — линейный поиск, O($n \log n$) — эффективные сортировки, O($n^{2}$) — пузырьковая и сортировка вставками. Меньший порядок роста предпочтительнее на больших объемах данных, даже если другой алгоритм быстрее для малых $n$.

Чтобы это стало понятнее: при сортировке миллиона элементов алгоритм со сложностью $O(n \log n)$ завершится за долю секунды, тогда как алгоритм со сложностью $O(n^{2})$ может занять минуты.

Разобранный пример. В отсортированном списке находится ⟨⟩$1000$ элементов. Сколько сравнений потребуется каждому поиску в худшем случае?

Линейный поиск проверяет элементы по одному, поэтому ему может потребоваться до ⟨⟩$1000$ сравнений — это $O(n)$. Бинарный поиск на каждом шаге уменьшает список вдвое, поэтому ему нужно не более ⟨⟩$\lceil \log_2 1000 \rceil = 10$ сравнений — это $O(\log n)$. Удвоение списка до ⟨⟩$2000$ элементов добавляет к бинарному поиску всего одно сравнение, но до ⟨⟩$1000$ к линейному поиску — именно поэтому на больших объемах данных победителем становится порядок роста, а не абсолютная скорость.

Описание порядка. O(1): время постоянно и не зависит от количества элементов (добавление элемента в стек, чтение из массива). O($\log n$): время растет пропорционально логарифму количества элементов, поэтому удвоение данных добавляет лишь фиксированный дополнительный шаг (бинарный поиск). O($n$): время растет пропорционально количеству элементов (линейный поиск, один проход по списку). O($n \log n$): немного хуже линейного (эффективные сортировки). O($n^{2}$): время растет пропорционально квадрату количества элементов, поэтому удвоение данных увеличивает время в четыре раза (пузырьковая и сортировка вставками). Вопрос «Укажите Big O для бинарного поиска по ⟨⟩Names[0:99]» имеет ответ $O(\log n)$, а «опишите его значение» — см. выше; Big O измеряет масштабирование времени или памяти, а не фактическое время работы.

Пространственная сложность

Пространственная сложность — это дополнительная所需 памяти. Пузырьковая и сортировка вставках используют O(1) дополнительной памяти (in-place); слияние требует O($n$); рекурсия использует память стека, пропорциональную глубине. Часто существует компромисс между временем и памятью.

Другие критерии

Простота (легче кодить и поддерживать), стабильность и адаптивность (быстрее работает на почти отсортированных данных). Правильный выбор алгоритма зависит от данных и ограничений.

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

Факториал:

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
    IF n = 0 OR n = 1 THEN
        RETURN 1
    ELSE
        RETURN n * Factorial(n - 1)
    ENDIF
ENDFUNCTION

Рекурсия естественна для самоподобных задач: деревьев, разделяй и властвуй (бинарный поиск, слияние), и вложенных данных. Когда она плохо подходит, цикл обычно чище.

«Опишите, что понимается под рекурсией» (два балла). Функция или процедура, определенная через саму себя: она вызывает саму себя внутри собственного тела, передавая каждый раз меньшую версию задачи, пока не будет достигнут базовый случай. «Назовите три основных признака рекурсии»: (1) базовый случай (условие остановки), возвращающий значение без дальнейшего вызова; (2) общий случай, в котором процедура вызывает саму себя; (3) каждый вызов приближает задачу к базовому случаю (параметр уменьшается), так что рекурсия завершается. Некоторые схемы добавляют: значения возвращаются по мере того, как вызовы опустошают стек.

«Опишите, когда использование рекурсии полезно, и приведите пример». Когда задача естественно определяется через меньшие версии самой себя, так что рекурсивное решение короче, понятнее и ближе к математическому определению, чем циклическое: факториал или числа Фибоначчи, бинарный поиск, обход двоичного дерева, слияние или быстрая сортировка, обработка вложенных структур, таких как папки внутри папок. Это плохой выбор, когда глубина велика (стек может переполниться) или когда одна и та же подзадача вычисляется многократно (наивный алгоритм Фибоначчи).

Отслеживание рекурсивного вызова

Для ⟨⟩Factorial(4): вызовы спускаются до ⟨⟩Factorial(1)=1, затем опустошение умножает обратно вверх: ⟨⟩2*1=2, ⟨⟩3*2=6, ⟨⟩4*6=24. Итоговый результат ⟨⟩24. Отслеживайте каждый ожидающий вызов в стеке.

Разобранный пример. Ниже приведена функция без объяснения. Отследите ⟨⟩Unknown(3, 5) и укажите её вывод и возвращаемое значение.

FUNCTION Unknown(BYVAL X, BYVAL Y : INTEGER) RETURNS INTEGER
    IF X < Y THEN
        OUTPUT X + Y
        RETURN Unknown(X + 1, Y - 1) + 1
    ELSE
        RETURN 0
    ENDIF
ENDFUNCTION

Вызов 1: ⟨⟩$X = 3, Y = 5$: ⟨⟩$3 < 5$, вывод 8, вызов ⟨⟩Unknown(4, 4). Вызов 2: ⟨⟩$4 < 4$ является ложным, возврат 0. Опустошение: вызов 1 возвращает ⟨⟩$0 + 1 = 1$. Вывод 8, возвращаемое значение 1. Запишите отслеживание в виде таблицы со строкой на каждый вызов (параметры, условие, вывод, что он возвращает), и выполняйте возвраты от самого глубокого вызова вверх: именно такое опустошение ожидает ключ к оцениванию.

Разобранный пример (числа Фибоначчи). Fib(n) возвращает n при n < 2, иначе Fib(n - 1) + Fib(n - 2). Найдите Fib(5).

Fib(5) = Fib(4) + Fib(3); Fib(4) = Fib(3) + Fib(2); Fib(3) = Fib(2) + Fib(1); Fib(2) = Fib(1) + Fib(0) = 1 + 0 = 1. Таким образом, Fib(3) = 1 + 1 = 2, Fib(4) = 2 + 1 = 3, Fib(5) = 3 + 2 = 5. Базовый случай достигается множественно (Fib(2) вычисляется три раза), поэтому эта версия работает медленно: она выполняет 15 вызовов для $n = 5$ и примерно удваивает количество вызовов с каждым увеличением $n$.

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

FUNCTION Factorial(N : INTEGER) RETURNS INTEGER
    DECLARE Result, Count : INTEGER
    Result ← 1
    FOR Count ← 2 TO N
        Result ← Result * Count
    NEXT Count
    RETURN Result
ENDFUNCTION

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

Риски

• бесконечная рекурсия при отсутствии базового случая — завершается аварийно с ошибкой переполнения стека.
• высокое потребление памяти при глубокой рекурсии.
• медленная работа при повторении вычислений (наивное число Фибоначчи имеет экспоненциальную сложность — используйте цикл или мемоизацию).

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

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

"Объясните, почему стек подходит для реализации рекурсии (три балла).** Каждый рекурсивный вызов должен сохранить свой адрес возврата, параметры и локальные переменные, а вызовы завершаются в обратном порядке по отношению к тому, в котором они были сделаны (последний вызванный вызов является первым завершенным), что точно соответствует поведению стека «последним вошел — первым вышел» (LIFO): каждый новый вызов создает (push) фрейм, а каждый возврат удаляет (pop) самый последний фрейм, восстанавливая состояние вызывающей функции и указывая ей, где продолжать. Это задача компилятора при трансляции рекурсивного кода: он генерирует создание фрейма стека при каждом вызове и удаление при каждом возврате, а фреймы разматываются по мере поступления результатов.

Вопросы на определение оцениваются по фиксированной формулировке. Выучите их точно и дайте только один ответ.

• Поиски: линейный поиск не требует упорядоченности и имеет сложность O($n$); бинарный поиск требует отсортированного массива, делит задачу пополам на каждом шаге и имеет сложность O($\log n$). Выучите оба алгоритма наизусть, включая границы и флаги.
• Сортировки: пузырьковая с флагом обмена, вставками с ключом, сдвигающим бо́льшие элементы вправо; обе имеют худшую сложность O($n^{2}$) и лучшую O($n$) на отсортированных данных. Производительность зависит от количества элементов и степени их упорядоченности.
• Реализации АТД требуют управления указателями: указатель верха; front, rear и count с операцией MOD; start, указатели и свободный список; корень с указателями на левое и правое поддеревья. Всегда проверяйте условия полноты и пустоты.
• Big O касается масштабируемости: константная, логарифмическая, линейная, квадратичная. Для бинарного поиска говорите: «удвоение объема данных добавляет одну операцию сравнения».
• Рекурсия: базовый случай, общий случай, прогресс к базовому случаю; полезна, когда задача определена через саму себя; стек хранит адреса возврата и переменные, так как вызовы завершаются в обратном порядке. Отслеживайте процесс с помощью таблицы и разматывайте стек от самого глубокого вызова.

Распространенные ошибки

• Использование бинарного поиска на неотсортированных данных или на связном списке; а также установка Lower ← Mid вместо Mid + 1, что приводит к бесконечному циклу.
• Вложенный цикл пузырьковой сортировки, проходящий до конца массива при каждом проходе, или обмен без использования временной переменной.
• Операция push или enqueue без проверки на переполнение, или pop/dequeue без проверки на пустоту.
• Перемещение указателя front очереди без применения операции MOD в кольцевой очереди или трактовка front = rear как всегда означающего пустую очередь.
• Вставка в связный список путем сдвига содержимого массива; должны меняться только указатели.
• Рекурсивная функция без базового случая или у которой рекурсивный вызов не уменьшает размер задачи.
• Отслеживание рекурсивного вызова, но забывание добавить ожидаемую работу на обратном пути вверх.
• Ответ на вопрос «почему стек» — «потому что это быстро»; истинная причина заключается в порядке возврата элементов LIFO (последним вошедшим — первым вышедшим).