Стек - это набор элементов, хранящихся с использованием политики последний пришел - первый ушел или LIFO. Это означает, что последнее, что вставляется в стек, - это первое, что удаляется из стека. Часто мы можем думать о стопке как о стопке обеденных тарелок. Когда мы кладем тарелку в стопку, мы помещаем ее сверху, и, в свою очередь, когда мы хотим снять тарелку со стопки, мы также снимаем ее сверху. Это такая же структура, которую мы хотим реализовать с программным стеком.

Давайте начнем с визуального примера стека. Предположим, я вставил в свой стек три значения: 5, 6 и 7. Если они вставлены в указанном порядке, наш стек будет выглядеть, как показано ниже.

Последнее, что было вставлено, то есть 7, это верхний элемент в стеке, а первое, что было вставлено, то есть 5, это нижний элемент в стеке. Когда мы работаем со стеками, мы обычно реализуем три метода для управления данными в них. Это методы push, pop и peek. Push вставит новое значение в верхнюю часть стека, pop удалит верхнее значение из стека, а peek вернет значение из верха стека.

В нашем примере предположим, что теперь мы хотим поместить значение 8 в стек. Когда мы это делаем, 8 становится новой вершиной стека, а элемент прямо под ней был предыдущей вершиной 7.

Если бы мы хотели затем вытолкнуть из этого стека, он бы удалил текущую вершину и обновил бы вершину, чтобы она была следующей в стеке. В этом случае 8 будет удалено и возвращено пользователю, а 7 станет вершиной стека.

Наконец, если бы мы захотели заглянуть в этот стек, он просто сообщил бы нам верхнее значение, не изменяя его вообще. В этом случае он вернет 7, а стек останется прежним.

Когда мы реализуем стек на C, мы обычно используем две структуры. Первая структура называется узлом и отслеживает отдельный элемент, а также указатель на следующий элемент в стеке. Вторая структура называется стеком, в которой верхний элемент хранится как узел. Поскольку узел имеет указатель на следующий элемент в стеке, если нам когда-нибудь понадобится получить элемент ниже вершины, мы можем использовать указатель, чтобы найти его.

Итак, в нашем примере стека, если 7 является вершиной стека, у него будет указатель на 6, который является следующим элементом в стеке. Узел для 6 будет иметь указатель на 5, поскольку 5 идет после 6. Наконец, 5 будет иметь указатель на NULL, поскольку за ним нет значений. Следующий код показывает, как эти две структуры могут быть реализованы в C.

В этой реализации наш узел отслеживает свое значение с помощью атрибута данных. Он дополнительно имеет атрибут указателя с именем next, который указывает на узел, который непосредственно следует за ним. Наш стек отслеживает верхний узел через атрибут top, а также отслеживает его размер в атрибуте size.

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

Теперь, когда наш стек готов, мы начнем смотреть, как мы можем реализовать наши операции push, pop и peek. Мы также создадим метод для отображения данных, которые в настоящее время находятся в стеке, чтобы иметь возможность проверить правильность работы наших операций.

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

Для операции pop нашим первым шагом будет убедиться, что в стеке есть хотя бы один элемент, который можно удалить. Для этого мы можем посмотреть размер стека, чтобы проверить, равен ли он 0. Если размер стека не равен 0, мы приступаем к выталкиванию элемента из стека. В противном случае мы напечатаем сообщение об ошибке и завершим программу. При извлечении из стека мы начинаем с сохранения значения верхнего элемента в стеке. Затем мы обновляем верх стека, чтобы он стал следующим доступным элементом, на который указывает следующий атрибут вершины. Наконец, мы уменьшаем размер стека на 1 и возвращаем пользователю значение, которое было наверху стека.

Операция просмотра - это, по сути, упрощенная версия операции pop. Мы делаем те же шаги, за исключением обновления вершины и размера стека.

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

Чтобы протестировать эту реализацию, мы можем создать основную функцию и запустить каждый из наших методов.

Следует отметить несколько моментов, касающихся того, как мы настраиваем наш стек для использования. Во-первых, когда мы объявляем нашу структуру стека, мы назначаем размер стека, поскольку он должен быть инициализирован в памяти, прежде чем мы сможем его использовать. После этого мы сначала запускаем функцию init, чтобы настроить наш стек с правильными начальными значениями. Как только это будет сделано, мы можем запускать операции push, pop, peek и print в любой последовательности, чтобы увидеть, какие результаты мы получим. Запустив эту последовательность, я получаю следующий результат.

Полный код C для этой реализации стека доступен по адресу: https://github.com/scprogramming/The-Complete-Guide-to-C-Data-Structures-and-Algorithms/tree/master/Stacks