Структуры данных: введение в стеки

Массивы - это здорово, но пробовали ли вы использовать стеки?

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

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

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

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

Ресурсы, рекомендуемые для начинающих

Cracking the Coding Interview: 189 вопросов и решений по программированию Гейл Лаакманн МакДауэлл.
Введение в алгоритмы Томаса Х. Кормена.

Концепция стека

Представьте стопку как серию тарелок, расположенных одна над другой, вертикально, снизу вверх.

Предположим, есть пять тарелок, P1, P2, P3, P4 и P5, и вы хотите организовать их в виде стопки (то есть поставить их одну над другой), тогда как бы вы это сделали?

Очевидно, вы возьмете первую тарелку, P1, и поверх нее вы положите тарелку P2, а затем следующую тарелку и так далее, пока вы не поставите последнюю тарелку, то есть P5.

Все это образует стопку тарелок, что показано на следующей диаграмме.

И всякий раз, когда вы хотите получить доступ к определенной пластине или вынуть ее, вы должны сначала увидеть, находится ли пластина, к которой вы хотите получить доступ, вверху или нет.

Допустим, мы хотим получить доступ к P3, а затем, прежде чем дойти до пластины P3, вам сначала нужно удалить пластины P5 и P4 из стопки.

Стек также известен как LIFO (last-in-first-out), что означает, что элемент, который вставлен в стек последним, будет удален из стека первым.

Операции над стеком

Push: чтобы вставить элемент в стек.
Поп: удалить элемент из стека.

Реализация стека

Есть два способа реализовать структуру данных стека.

1. Использование массива

В этом представлении мы будем реализовывать стек, используя массив, индекс которого начинается с 0.

Перед вставкой или удалением элемента мы должны проверить два условия: первое - это условие переполнения, а второе - это условие недостаточного заполнения.

Условие переполнения просто проверяет, заполнен ли стек или нет. Если он уже заполнен, вы не можете вставить новый элемент в стек.

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

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

Здесь указатель top отслеживает самое верхнее положение стека. Если значение верхнего указателя равно -1, это означает, что стек пуст. Этот момент также применим к представлению стека в виде связанного списка.

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

Сложность времени для вставки и удаления элемента в массиве занимает O (1), то есть постоянное время.

2. Использование связанного списка

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

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

Но перед вставкой элемента мы сначала должны создать новый узел, а затем добавить этот узел в связанный список. Здесь также мы должны проверить условия переполнения и потери значимости.