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

В информатике стек (stack) - это абстрактный тип данных, который служит набором элементов с двумя основными операциями:

push, которая добавляет элемент в коллекцию;
pop, которая удаляет последний добавленный элемент, который еще не был удален;

Порядок, в котором элементы выходят из стека, порождает его альтернативное имя, LIFO (last in, first out) (последний пришел, первый вышел). Кроме того, операция peek может дать доступ к вершине без изменения стека. Название "стек" для этого типа структуры происходит от аналогии с набором физических элементов, уложенных друг на друга, что позволяет легко убрать элемент с верха стека, в то время как переход к элементу, находящемуся глубже в стеке может потребовать сначала снять несколько других предметов.

Рассматриваемые как линейная структура данных или, более абстрактно, последовательная коллекция, операции push и pop выполняются только на одном конце структуры, называемой вершиной стека. Это позволяет реализовать стек в виде односвязного списка и указателя на верхний элемент. Стек может быть реализован так, чтобы иметь ограниченную емкость. Если стек заполнен и не содержит достаточно места для принятия объекта, который должен быть передан, то считается, что стек находится в состоянии переполнения. Операция pop удаляет элемент из верхней части стека.

Стек необходим для реализации поиска в глубину.

История

Стеки вошли в литературу по информатике в 1946 году, когда Алан М. Тьюринг использовал термины "bury" и "unbury" в качестве средства вызова и возврата из подпрограмм. Подпрограммы уже были реализованы в Z4 Конрада Цузе в 1945 году.

Клаус Самельсон и Фридрих Л. Бауэр из Технического университета Мюнхена предложили эту идею в 1955 году и подали патент в 1957 году, а в марте 1988 года Бауэр получил награду Computer Pioneer Award за изобретение принципа стека. Эта же концепция была разработана независимым австралийцем Чарльзом Леонардом Хамблином в первой половине 1954 года.

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

Несущественные операции

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

Программные стеки

Реализация

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

Массив

Массив может быть использован для реализации (ограниченного) стека следующим образом. Первый элемент (обычно со смещением нуля) является нижним, в результате чего array[0] является первым элементом, помещаемым в стек, а последний элемент удаляется. Программа должна следить за размером (длиной) стека, используя переменную top, которая записывает количество отправленных элементов, поэтому указывает на место в массиве, куда должен быть вставлен следующий элемент (при условии нулевого соглашение об индексе). Таким образом, сам стек может быть эффективно реализован как трехэлементная структура:

structure stack:
    maxsize : integer
    top : integer
    items : array of item

procedure initialize(stk : stack, size : integer):
    stk.items ← new array of size items, initially empty
    stk.maxsize ← size
    stk.top ← 0

Операция push добавляет элемент и увеличивает верхний индекс после проверки на переполнение:

procedure push(stk : stack, x : item):
    if stk.top = stk.maxsize:
        report overflow error
    else:
        stk.items[stk.top] ← x
        stk.top ← stk.top + 1

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

procedure pop(stk : stack):
    if stk.top = 0:
        report underflow error
    else:
        stk.top ← stk.top − 1
        r ← stk.items[stk.top]
        return r

Используя динамический массив, можно реализовать стек, который может увеличиваться или уменьшаться по мере необходимости. Размер стека - это просто размер динамического массива, который является очень эффективной реализацией стека, поскольку добавление элементов или удаление элементов из конца динамического массива требует амортизированного O(1) времени.

Связанный список

Другим вариантом реализации стеков является использование односвязного списка. Стек - это указатель на "голову" списка, возможно, со счетчиком для отслеживания размера списка:

structure frame:
    data : item
    next : frame or nil

structure stack:
    head : frame or nil
    size : integer

procedure initialize(stk : stack):
    stk.head ← nil
    stk.size ← 0

Добавление (операция push) и извлечение (операция pop) элементов происходит в начале списка; переполнение невозможно в этой реализации (если не исчерпана память):

procedure push(stk : stack, x : item):
    newhead ← new frame
    newhead.data ← x
    newhead.next ← stk.head
    stk.head ← newhead
    stk.size ← stk.size + 1

procedure pop(stk : stack):
    if stk.head = nil:
        report underflow error
    r ← stk.head.data
    stk.head ← stk.head.next
    stk.size ← stk.size - 1
    return r

Стеки и языки программирования

Некоторые языки, такие как Perl, LISP, JavaScript и Python, делают операции стека push и pop доступными для своих стандартных типов списков/массивов. Некоторые языки, особенно из семейства Forth (включая PostScript), разработаны вокруг стеков, определенных языком, которые непосредственно видны программисту и управляются им.

Ниже приведен пример манипулирования стеком в Common Lisp (">" - это приглашение интерпретатора Lisp; строки, не начинающиеся с ">" - это ответы интерпретатора на выражения):

> (setf stack (list 'a 'b 'c))  ;; задание переменной "stack"
(A B C)
> (pop stack)  ;; получение верхнего (самого левого) элемента, должно изменять stack
A
> stack        ;; проверяем значение stack
(B C)
> (push 'new stack)  ;; добавляем новый элемент на вершину stack
(NEW B C)

Некоторые из типов контейнеров стандартной библиотеки C++ имеют операции push_back и pop_back с семантикой LIFO; кроме того, шаблонный класс stack адаптирует существующие контейнеры для предоставления ограниченного API только с операциями push/pop. PHP имеет класс SplStack. Библиотека Java содержит класс Stack, который является специализацией Vector. Ниже приведен пример программы на языке Java с использованием этого класса.

import java.util.*;

class StackDemo {
  public static void main(String[]args) {
    Stack stack = new Stack();
    stack.push("A");    // Добавляем "A" в стек
    stack.push("B");    // Добавляем "B" в стек
    stack.push("C");    // Добавляем "C" в стек
    stack.push("D");    // Добавляем "D" в стек
    System.out.println(stack.peek()); // Печатаем вершину стека ("D")
    stack.pop();    // удаляем вершину ("D")
    stack.pop();    // удаляем следующую вершину ("C")
  }
}

Поиск по этому блогу

Alex tools