Стек (Stack) - структура данных LIFO

Стек —  линейная структура данных, которая позволяет удалять только последний добавленный элемент. Можно представить себе стек в образе стопки книг: вы можете доложить или убрать только верхнюю книгу, а чтобы добраться, скажем, до третьей книги, сначала потребуется убрать все книги над ней.
Стек является примером структуры данных «последним вошел, первым вышел», или Last In — First Out (LIFO). Последним вошел, первым вышел —структура данных, в которой элемент, помещенный в структуру последним, является первым элементом, который выходит из нее. Поскольку вы можете получить доступ к содержимому стека лишь по одному элементу за другим, стек также является примером структуры данных с ограниченным доступом, которая вынуждает получать доступ к ее информации только в определенном порядке.
В стеке есть две главные операции: проталкивание (push) и выталкивание (pop). Push означает помещение в стек нового элемента. Pop — удаление из стека последнего элемента. У стеков также могут быть дополнительные операции, например считывание (peek). Peek — это просмотр верхнего элемента
стека без его удаления.

Основные операции:

1. push(item) - добавление элемента на вершину стека (проталкивание)

2. pop() - удаление и возврат верхнего элемента (выталкивание)

3. peek() - просмотр верхнего элемента без удаления

4. is_empty() - проверка на пустоту

5. size() - получение размера стека

Сложности  выполнения:

Сложность операций:

Пример кода:

class ArrayStack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        """Добавление элемента на вершину стека"""
        self.items.append(item)
    
    def pop(self):
        """Удаление и возврат верхнего элемента"""
        if self.is_empty():
            raise IndexError('Удаление из пустого стека')
        return self.items.pop()
    
    def peek(self):
        """Просмотр верхнего элемента без удаления"""
        if self.is_empty():
            raise IndexError('Стек пуст')
        return self.items[-1]
    
    def is_empty(self):
        """Проверка на пустоту"""
        return not self.items
    
    def size(self):
        """Размер стека"""
        return len(self.items)
    
    def __str__(self):
        """Строковое представление"""
        return f"Stack({self.items})"
        
# реализация стека через связные списки


class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        
class LinkedStack:
    def __init__(self):
        self.head = None
        self._size = 0
    
    def push(self, data):
        """Добавление элемента на вершину стека"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self._size += 1
    
    def pop(self):
        """Удаление и возврат верхнего элемента"""
        if self.is_empty():
            raise IndexError('Удаление из пустого стека')
        popped = self.head
        self.head = self.head.next
        self._size -= 1
        return popped.data
    
    def peek(self):
        """Просмотр верхнего элемента"""
        if self.is_empty():
            raise IndexError('Стек пуст')
        return self.head.data
    
    def is_empty(self):
        """Проверка на пустоту"""
        return self.head is None
    
    def size(self):
        """Размер стека"""
        return self._size
    
    def __str__(self):
        """Строковое представление"""
        items = []
        current = self.head
        while current:
            items.append(str(current.data))
            current = current.next
        return f"Stack({' -> '.join(items)})"