Стек

Общие сведения

Стек (англ. stack) — абстрактный контейнер, доступ к элементам которого организован по принципу «последним вошёл — первым вышел» (англ. LIFO, Last In — First Out). Эта особенность отражена в названии (stack — стопка): из лежащей на столе стопки листов бумаги можно взять только листок, лежащий на самом верху, а для доступа к листкам в середине стопки нужно сначала снять все находящиеся выше них.

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

Интерфейс

Стек должен поддерживать три основные операции:

	void	push(T value)	— вставка элемента value в стек;
	T	pop()	— извлечение элемента из стека;
	bool	isEmpty()	— проверка стека на отсутствие элементов.

Все три метода должны иметь константное время работы (O(1)).

Демонстрация работы

• Data Structure Visualizations — Stack (Linked List Implementation)
• Data Structure Visualizations — Stack (Array Implementation)
• VisuAlgo — Linked List, Stack, Queue, Deque

Реализация на списке

Стек может быть реализован на односвязном списке. В этом случае каждый элемент стека хранит значение и указатель на следующий элемент. На вершину стека будет ссылаться указатель Node *top:

struct Node {
    int val;
    Node *next;
    Node(int v = 0, Node *n = NULL) {
        val = v;
        next = n;
    }
} *top;

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

Stack() {
    top = NULL;
}

Проверка на пустоту

Проверка стека на пустоту (реализация на списке)

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

bool isEmpty() {
    return top == NULL;
}

Вставка элемента

Вставка в стек (реализация на списке)

Для вставки элемента в стек требуется выполнить следующие действия:

• Фактически элемент добавляется в список, поэтому прежде всего нужно выделить память под новый экземпляр Node и задать в нём нужное значение val;
• Вставка элемента происходит в вершину стека, поэтому следующим элементом для вставляемого будет тот, на который в данный момент указывает top;
• Наконец, вершина стека теперь должна указывать на добавленный элемент.

Благодаря наличию конструктора Node(v, n) все вышеописанные операции можно выполнить одной строкой:

void push(int value) {
    top = new Node(value, top);
}

Извлечение элемента

Извлечение из стека (реализация на списке)

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

Удаление элемента из стека подразумевает следующую последовательность операций:

• Так как необходимо вернуть извлечённое значение, но также и освободить память, отведённую под соответствующий элемент списка, требуется сохранить значение top->val во временной переменой для возможности последующего возврата;
• Указатель на вершину стека нужно сместить на следующий элемент, но перед этим нужно сохранить во временной переменной предыдущий адрес вершины, чтобы можно было освободить память;
• Далее можно освободить память и вернуть сохранённое ранее значение.

int pop() {
    if (top == NULL)
        /* обработка ошибки - нет элементов для извлечения */
    int v = top->val;
    Node *tmp = top;
    top = top->next;
    delete tmp;
    return v;
}

---

Ниже приведён полный код реализации стека на односвязном списке. Попытка извлечения из пустого стека выявляется с помощью конструкции assert (заголовочный файл <assert.h> либо <cassert>).

class Stack {

    struct Node {
        int val;
        Node *next;
        Node(int v = 0, Node *n = NULL) {
            val = v;
            next = n;
        }
    } *top;

public:

    Stack() {
        top = NULL;
    }

    void push(int value) {
        top = new Node(value, top);
    }

    int pop() {
        assert(top != NULL);
        int v = top->val;
        Node *tmp = top;
        top = top->next;
        delete tmp;
        return v;
    }

    bool isEmpty() {
        return top == NULL;
    }

};

Реализация на массиве

Стек также можно реализовать на массиве. Основное ограничение, связанное с подобной реализацией, — конечный размер стека, переполнение которого нужно дополнительно отслеживать. Кроме того, при реализации на статических массивах стек будет всегда занимать объём памяти, пропорциональный максимальному количеству элементов (так как внутри стека объявлен массив фиксированного размера).

Вершина стека при реализации на массиве может быть указана индексом int top:

static const int MAX_SIZE = 100;
int a[MAX_SIZE];
int top;

При добавлении элементов индекс top будет увеличиваться, при удалении — уменьшаться, что позволяет не перемещать сами хранимые элементы, а лишь изменять значение индекса. В конструкторе стека top инициализируется значением 0:

Stack() {
    top = 0;
}

Проверка на пустоту

Проверка стека на пустоту (реализация на массиве)

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

bool isEmpty() {
    return top == 0;
}

Вставка элемента

Вставка в стек (реализация на массиве)

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

void push(int value) {
    if (top + 1 == MAX_SIZE)
        /* обработка ошибки - переполнение стека */
    a[top++] = value;
}

Извлечение элемента

Извлечение из стека (реализация на массиве)

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

int pop() {
    if (top == 0)
        /* обработка ошибки - нет элементов для извлечения */
    return a[--top];
}

---

Ниже приведён полный код реализации стека на массиве. Переполнение стека и попытка извлечения из пустого стека выявляются с помощью конструкции assert (заголовочный файл <assert.h> либо <cassert>).

class Stack {

    static const int MAX_SIZE = 100;
    int a[MAX_SIZE];
    int top;

public:

    Stack() {
        top = 0;
    }

    void push(int value) {
        assert(top + 1 < MAX_SIZE);
        a[top++] = value;
    }

    int pop() {
        assert(top > 0);
        return a[--top];
    }

    bool isEmpty() {
        return top == 0;
    }

};

Стек в STL

В стандартной библиотеке шаблонов C++ присутствует шаблон stack<T>. Для возможности его использования требуется подключить заголовочный файл <stack> и пространство имён std:

#include <iostream>
#include <stack>
using namespace std;
int main() {
    stack<int> s;
    for (int i = 1; i < 6; i++)
        s.push(i);
    while (!s.empty()) {
        cout << s.top() << ' ';
        s.pop();
    }            
    return 0;       //результат "5 4 3 2 1 "
}

STL предоставляет следующий набор методов для стека:

		stack<T>()	— конструктор;
	void	push(const T& x)	— добавление элемента;
	void	pop()	— удаление элемента. Обратите внимание на то, что значение удаляемого элемента не возвращается;
	T&	top()	— получение значения элемента на вершине стека. Этот метод не производит удаление элемента;
	bool	empty()	— проверка на пустоту;
	size_t	size()	— получение количества элементов в стеке. Метод возвращает беззнаковое целое число.

Ссылки

Теория:

• e-maxx.ru — Модификация стека для нахождения минимума
• neerc.ifmo.ru/wiki — Стек
• brestprog.by — Простейшие структуры данных: стек, очередь, дек
• algorithmica.org — Стек
• usaco.guide — Stacks
• opendatastructures.org — ArrayStack
• opendatastructures.org — Stack operations via SLList
• algs4.cs.princeton.edu/lectures — 1.3 Stacks and Queues

Демонстрация:

• visualgo.net — Stack
• www.cs.usfca.edu — Stack: Array Implementation
• www.cs.usfca.edu — Stack: Linked List Implementation

Код:

• kevin-wayne/algs4/Stack.java
• kevin-wayne/algs4/LinkedStack.java
• kevin-wayne/algs4/ResizingArrayStack.java

Задачи:

• informatics.mccme.ru — Курс «Структуры данных» — часть 1
• Задачи: Стек