Стек: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показано 25 промежуточных версий 2 участников)
Строка 1: Строка 1:
== TLDR ==
<youtube width="300" height="180">APPYBwkwgaQ</youtube>
<youtube width="300" height="180">A8bTNv3hsP8</youtube>
== Общие сведения ==
== Общие сведения ==
Стек (англ. stack) &mdash; абстрактный контейнер, доступ к элементам которого организован по принципу «последним вошёл — первым вышел» (англ. LIFO, Last In &mdash; First Out). Эта особенность отражена в названии (stack &mdash; стопка): из лежащей на столе стопки листов бумаги можно взять только листок, лежащий на самом верху, а для доступа к листкам в середине стопки нужно сначала снять все находящиеся выше них.
Стек (англ. stack) &mdash; абстрактный контейнер, доступ к элементам которого организован по принципу «последним вошёл — первым вышел» (англ. LIFO, Last In &mdash; First Out). Эта особенность отражена в названии (stack &mdash; стопка): из лежащей на столе стопки листов бумаги можно взять только листок, лежащий на самом верху, а для доступа к листкам в середине стопки нужно сначала снять все находящиеся выше них.
Строка 7: Строка 11:
Стек должен поддерживать три основные операции:
Стек должен поддерживать три основные операции:


{|
{| class="methodlist"
| <tt>void push(T value)</tt> || &mdash; вставка элемента <tt>value</tt> в стек;
| || void || push(T value) || &mdash; вставка элемента <tt>value</tt> в стек;
|-
|-
| <tt>T pop()</tt>            || &mdash; извлечение элемента из стека;
| ||    T || pop()         || &mdash; извлечение элемента из стека;
|-
|-
| <tt>bool isEmpty()</tt>     || &mdash; проверка стека на отсутствие элементов.
| || bool || isEmpty()    || &mdash; проверка стека на отсутствие элементов.
|}
|}


Строка 18: Строка 22:


== Демонстрация работы ==
== Демонстрация работы ==
[[Демонстрация работы стека]]
 
* [http://www.cs.usfca.edu/~galles/visualization/StackLL.html Data Structure Visualizations — Stack (Linked List Implementation)]
* [http://www.cs.usfca.edu/~galles/visualization/StackArray.html Data Structure Visualizations — Stack (Array Implementation)]
* [http://visualgo.net/list.html VisuAlgo &mdash; Linked List, Stack, Queue, Deque]


== Реализация на списке ==
== Реализация на списке ==
Строка 165: Строка 172:
----
----


Ниже приведён полный код реализации стека на массиве. Переполнение стека и попытка извлечения из пустого стека выявляются с помощью конструкции [http://www.cplusplus.com/reference/cassert/assert/ assert] (заголовочный файл <tt><assert.h></tt> либо <tt><cassert></tt>.
Ниже приведён полный код реализации стека на массиве. Переполнение стека и попытка извлечения из пустого стека выявляются с помощью конструкции [http://www.cplusplus.com/reference/cassert/assert/ assert] (заголовочный файл <tt><assert.h></tt> либо <tt><cassert></tt>).


  class Stack {
  class Stack {
Строка 180: Строка 187:
   
   
     void push(int value) {
     void push(int value) {
         assert (top + 1 < MAX_SIZE);
         assert(top + 1 < MAX_SIZE);
         a[top++] = value;
         a[top++] = value;
     }
     }
Строка 196: Строка 203:


== Стек в STL ==
== Стек в STL ==
В стандартной библиотеке шаблонов C++ присутствует шаблон <tt>stack<T></tt>. Для возможности его использования требуется подключить заголовочный файл <tt><stack></tt> и пространство имён <tt>std</tt>:
В стандартной библиотеке шаблонов C++ присутствует шаблон [http://www.cplusplus.com/reference/stack/stack/ <tt>stack<T></tt>]. Для возможности его использования требуется подключить заголовочный файл <tt><stack></tt> и пространство имён <tt>std</tt>:


  #include <iostream>
  #include <iostream>
Строка 202: Строка 209:
  using namespace std;
  using namespace std;
  int main() {
  int main() {
     stack s;
     stack<int> s;
     for (int i = 1; i < 6; i++)
     for (int i = 1; i < 6; i++)
         s.push(i);
         s.push(i);
Строка 213: Строка 220:


STL предоставляет следующий набор методов для стека:
STL предоставляет следующий набор методов для стека:
{|
{| class="methodlist"
| <tt>stack<T>()</tt>         || &mdash; конструктор;
| ||        || stack<T>()       || &mdash; конструктор;
|-
|-
| <tt>void push(const T& x)</tt> || &mdash; добавление элемента;
| ||  void || push(const T& x) || &mdash; добавление элемента;
|-
|-
| <tt>void pop()</tt>           || &mdash; удаление элемента. Обратите внимание на то, что значение удаляемого элемента не возвращается;
| ||  void || pop()            || &mdash; удаление элемента. Обратите внимание на то, что значение удаляемого элемента не возвращается;
|-
|-
| <tt>T& top()</tt>              || &mdash; получение значения элемента на вершине стека. Этот метод не производит удаление элемента;
| ||    T& || top()           || &mdash; получение значения элемента на вершине стека. Этот метод не производит удаление элемента;
|-
|-
| <tt>bool empty()</tt>         || &mdash; проверка на пустоту;
| ||  bool || empty()          || &mdash; проверка на пустоту;
|-
|-
| <tt>size_t size()</tt>        || &mdash; получение количества элементов в стеке. Метод возвращает беззнаковое целое число.
| || size_t || size()           || &mdash; получение количества элементов в стеке. Метод возвращает беззнаковое целое число.
|}
|}


[[Category:Учебный курс &laquo;Алгоритмы и структуры данных&raquo;]]
== Ссылки ==
Теория:
* [http://e-maxx.ru/algo/stacks_for_minima e-maxx.ru — Модификация стека для нахождения минимума]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%82%D0%B5%D0%BA neerc.ifmo.ru/wiki &mdash; Стек]
* [https://brestprog.by/topics/datastructures/ brestprog.by — Простейшие структуры данных: стек, очередь, дек]
* [http://algorithmica.org/tg/basic-data-structures algorithmica.org — Стек]
* [https://usaco.guide/gold/stacks?lang=cpp usaco.guide — Stacks]
* [http://opendatastructures.org/ods-cpp/2_1_Fast_Stack_Operations_U.html opendatastructures.org — ArrayStack]
* [https://opendatastructures.org/ods-cpp/3_1_Singly_Linked_List.html opendatastructures.org — Stack operations via SLList]
* [https://algs4.cs.princeton.edu/lectures/keynote/13StacksAndQueues.pdf algs4.cs.princeton.edu/lectures &mdash; 1.3 Stacks and Queues]
Демонстрация:
* [https://visualgo.net/en/list visualgo.net — Stack]
* [https://www.cs.usfca.edu/~galles/visualization/StackArray.html www.cs.usfca.edu — Stack: Array Implementation]
* [https://www.cs.usfca.edu/~galles/visualization/StackLL.html www.cs.usfca.edu — Stack: Linked List Implementation]
Код:
* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/Stack.java kevin-wayne/algs4/Stack.java]
* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/LinkedStack.java kevin-wayne/algs4/LinkedStack.java]
* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/ResizingArrayStack.java kevin-wayne/algs4/ResizingArrayStack.java]
Задачи:
* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru &mdash; Курс &laquo;Структуры данных&raquo; &mdash; часть 1]
* [[:Категория:Задачи: Стек|Задачи: Стек]]
 
[[Category:Базовые структуры и абстрактные типы данных]]

Текущая версия от 15:21, 24 мая 2023

TLDR

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

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

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

Интерфейс

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

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

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

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

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

Стек может быть реализован на односвязном списке. В этом случае каждый элемент стека хранит значение и указатель на следующий элемент. На вершину стека будет ссылаться указатель 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() — получение количества элементов в стеке. Метод возвращает беззнаковое целое число.

Ссылки

Теория:

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

Код:

Задачи: