Изменения

Как видно из псевдокода выше, все операции со стеком выполняются за $O(1)$.</wikitex>

===На списке===

<wikitex>Стек можно реализовать и на [[Список | списке]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <math> \mathrm {push} </math> будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью <math> \mathrm {pop} </math> будет текущая голова. После вызова функции <math> \mathrm {push} </math> текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции <math> \mathrm {pop} </math> будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.

В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же $n$. Стоит заметить, что, хотя общая оценка затрачиваемой памяти $O(n)$, в ней скрыта бóльшая константа, и реализация на списке требует несколько больше памяти.

</wikitex>

===На саморасширяющемся массиве===

<wikitex>Возможна реализация стека на [[Саморасширяющийся_массив|векторе]]. Для этого нужно создать вектор и определить операции стека на нём. В функции <math> \mathrm {push} </math> Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в <math> \mathrm {pop} </math>, перед тем, как изъять элемент из массива, {{---}} не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.