Стек

определение
Стек — структура данных, которая позволяет быстро добавить элемент в конец и быстро получить последний элемент. Эти операции эффективно поддерживаются динамическим массивом, можно использовать именно его. Поэтому мы не будем подробно разбирать другие представления стека в стандартных библиотеках языков.
Функции, связанные со стеком
  • empty () — возвращает, пуст ли стек — временная сложность: O (1)
  • size() — возвращает размер стека — временная сложность: O(1)
  • top () / peek () — возвращает ссылку на самый верхний элемент стека — временная сложность: O (1)
  • push(a) – вставляет элемент «a» в верхнюю часть стека – временная сложность: O(1)
  • pop() — удаляет самый верхний элемент стека — временная сложность: O(1)
способы реализации стека
  • список list
  • Collections.deque
  • Queue.LifoQueue
  • Создание класса односвязного списка.
Список list
Cписок имеет недостатков при использовании в качестве стека - это реаллокация. При увеличении количества элементов команда вставки может вызвать перезапись массива, что в разы увеличит время выполнения команды.

Читать динамический массив

stack = []

# добавление элементов в стек
stack.append(1)

# извлечение и удаление элементов
element = stack.pop()
Collections.deque
Стек можно реализовать с помощью класса deque из модуля collections.

Deque имеет более быстрые операции добавления и извлечения элементов с обоих концов контейнера.

from collections import deque
 
stack = deque()

# добавление элементов в стек
stack.append(1)

# извлечение и удаление элементов
element = stack.popleft()
Queue.LifoQueue
Модуль Queue имеет структуру данных LifoQueue.

В этом модуле доступны различные функции:

  • maxsize — допустимое количество элементов в очереди.
  • empty() — возвращает True, если очередь пуста, в противном случае — False.
  • full() — возвращает True, если в очереди есть элементы максимального размера .
  • get() — удалить и вернуть элемент из очереди. Если очередь пуста, блокирует на время указанного тайм-аута.
  • get_nowait () — вернуть элемент, если он доступен сразу, в противном случае поднять исключение QueueEmpty.
  • put(item) – поместить предмет в очередь. Если очередь заполнена, подождите, пока освободится свободный слот.
  • put_nowait(item) – Поместить предмет в очередь без блокировки. Если нет свободных мест, поднять исключение QueueFull.
  • qsize() — возвращает количество элементов в очереди. 

from queue import LifoQueue
 
stack = LifoQueue(maxsize=3)

# добавление элементов в стек
stack.put('a')

# извлечение и удаление элементов
element = stack.get()
Создание стека на классе
Реализуем Стэк с использованием класса и реализацией односвязнного списка. Класс будет иметь методы:

  • getSize() — получить количество элементов в стеке.
  • isEmpty() — возвращает True, если стек пуст, иначе False.
  • peek() — возвращает верхний элемент стека. Если стек пуст, создайте исключение.
  • push(value) — поместить значение в начало стека.
  • pop() — удалить и вернуть значение в начале стека. Если стек пуст, создайте исключение. 

from dataclasses import dataclass
from typing import ClassVar


@dataclass(repr=False, eq=False)
class Node:
    value: int
    next: ClassVar = None


@dataclass(repr=False, eq=False)
class Stack:
    head: ClassVar = Node("head")
    size: ClassVar = 0

    def __str__(self):
        cur = self.head.next
        out = ""
        while cur:
            out += str(cur.value) + "->"
            cur = cur.next
        return out[:-3]

    def getSize(self):
        return self.size

    def isEmpty(self):
        return self.size == 0

    def peek(self):
        if self.isEmpty():
            raise Exception("Стэк пустой")
        return self.head.next.value

    def push(self, value):
        node = Node(value)
        node.next = self.head.next
        self.head.next = node
        self.size += 1

    def pop(self):
        if self.isEmpty():
            raise Exception("Стэк пустой")
        remove = self.head.next
        self.head.next = self.head.next.next
        self.size -= 1
        return remove.value


if __name__ == "__main__":
    stack = Stack()
    for i in range(1, 11):
        stack.push(i)
    print(f"Stack: {stack}")

    for _ in range(1, 6):
        remove = stack.pop()
        print(f"Pop: {remove}")
    print(f"Stack: {stack}")
КОГДА ЛУЧШЕ ИСПОЛЬЗОВАТЬ стек
Стэк часто используют для обработки пар элементов.

Например: Дана последовательность из трёх видов пар скобок: ( и ), [ и ], { и }. Необходимо определить правильность скобочной последовательности.