Стеки.

Стек представляет собой абстрактный тип данных. Стек реализуется по принципу LIFO(Last In – First Out, т.е. последним пришел – первым вышел). Стек также часто называют магазином по аналогии с огнестрельным оружием (последний заряженный патрон выходит из дула первым). Еще одним примером может быть стопка с письмами, которые вы начинаете читать, начиная с самого верхнего, постепенно добираясь до самого нижнего.

letter_stack

Основные операции, выполняемые со стеком:

  • — занесение элемента на вершину стека (push)
  • — извлечение элемента из вершины стека (pop)
  • — чтение элемента из вершины стека (peek) без его удаления из стека.

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

 

stack

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

Вы наверня-ка уже знакомы с такой структурой данных, как массивы. Теперь с помощью массивов мы и попробуем организовать стек.

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

Теперь последовательно реализуем операции для работы со стеком.

Помещение элемента на вершину стека (PUSH).

Все, что мы здесь делаем – это заносим наш элемент в стек с увеличением значения top на 1.

Извлечение элемента из стека (POP).

Для того, чтобы извлечь элемент из верхушки стека, мы просто уменьшаем значение переменной top на 1:

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

Чтение элемента с верхушки стека.

Отличается от операции pop() тем, что элемент не удаляется из стека, а только читается.

Также можно ввести вспомогательные операции для проверки того, пуст или полон сейчас стек:

Повторимся, что приведенная в данном уроке реализация стека не является оптимальной в том плане. что зависит от типа хранимых значений. В уроке, посвященном обобщенным (generic) типам в Java мы приведем более эффективную реализацию класса Stack. В нашем коде существует и еще одна проблема — это размер стека. В клиентской программе может быть заранее неизвестно, сколько именно объектов должен хранить стек. Однако, массив имеет фиксированный размер. Что делать если произойдет переполнение? Есть два варианта.

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

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

Реализация целочисленного стека фиксированного размера на языке С.

Создадим структуру, представляющую стек.

Теперь реализуем основные методы для взаимодействия со стеком.

Теперь проверим наш стек на примере:

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

stack_c

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *