Реализация стека

Решение

Описание структуры данных

Стек (Stack) — это абстрактный тип данных, реализующий принцип LIFO (Last In, First Out). Последний добавленный элемент — первый удаляемый.

Подход 1: Реализация на Python с использованием списка

class Stack:
    """Реализация стека на базе динамического массива (list)."""
    
    def __init__(self):
        """Инициализируем пустой стек."""
        self.items = []
    
    def push(self, x):
        """
        Добавляет элемент на вершину стека.
        Сложность: O(1) в среднем, O(n) в худшем случае (при расширении массива)
        """
        self.items.append(x)
    
    def pop(self):
        """
        Удаляет и возвращает элемент с вершины стека.
        Сложность: O(1)
        
        Исключение: IndexError если стек пуст
        """
        if self.isEmpty():
            raise IndexError("pop from empty stack")
        return self.items.pop()
    
    def peek(self):
        """
        Возвращает элемент с вершины без удаления.
        Сложность: O(1)
        
        Исключение: IndexError если стек пуст
        """
        if self.isEmpty():
            raise IndexError("peek from empty stack")
        return self.items[-1]
    
    def isEmpty(self):
        """
        Проверяет, пуст ли стек.
        Сложность: O(1)
        """
        return len(self.items) == 0
    
    def size(self):
        """Возвращает количество элементов в стеке."""
        return len(self.items)
    
    def __str__(self):
        """Строковое представление стека."""
        return f"Stack({self.items})"


# Пример использования
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print(stack.peek())  # 3
print(stack.pop())   # 3
print(stack.pop())   # 2
print(stack.isEmpty())  # False
print(stack.pop())   # 1
print(stack.isEmpty())  # True

Подход 2: Реализация с использованием связного списка

class Node:
    """Узел связного списка."""
    def __init__(self, value):
        self.value = value
        self.next = None


class LinkedListStack:
    """Реализация стека на базе связного списка."""
    
    def __init__(self):
        self.top = None  # Указатель на вершину стека
    
    def push(self, x):
        """
        Добавляет элемент на вершину.
        Сложность: O(1)
        """
        new_node = Node(x)
        new_node.next = self.top
        self.top = new_node
    
    def pop(self):
        """
        Удаляет и возвращает элемент с вершины.
        Сложность: O(1)
        """
        if self.isEmpty():
            raise IndexError("pop from empty stack")
        value = self.top.value
        self.top = self.top.next
        return value
    
    def peek(self):
        """
        Возвращает элемент с вершины.
        Сложность: O(1)
        """
        if self.isEmpty():
            raise IndexError("peek from empty stack")
        return self.top.value
    
    def isEmpty(self):
        """
        Проверяет, пуст ли стек.
        Сложность: O(1)
        """
        return self.top is None
    
    def size(self):
        """Возвращает количество элементов."""
        count = 0
        current = self.top
        while current:
            count += 1
            current = current.next
        return count

Подход 3: На JavaScript/TypeScript

class Stack<T> {
    private items: T[] = [];
    
    push(x: T): void {
        this.items.push(x);
    }
    
    pop(): T {
        if (this.isEmpty()) {
            throw new Error("pop from empty stack");
        }
        return this.items.pop()!;
    }
    
    peek(): T {
        if (this.isEmpty()) {
            throw new Error("peek from empty stack");
        }
        return this.items[this.items.length - 1];
    }
    
    isEmpty(): boolean {
        return this.items.length === 0;
    }
    
    size(): number {
        return this.items.length;
    }
    
    clear(): void {
        this.items = [];
    }
}

// Использование
const stack = new Stack<number>();
stack.push(1);
stack.push(2);
const top = stack.peek();  // 2
const popped = stack.pop();  // 2
const isEmpty = stack.isEmpty();  // false

Анализ сложности

*Амортизированная сложность push в Python списке

Использование встроенного модуля

В Python можно использовать collections.deque для более эффективной работы:

from collections import deque

stack = deque()
stack.append(1)      # push
stack.append(2)
print(stack[-1])     # peek -> 2
print(stack.pop())   # pop -> 2
print(len(stack) == 0)  # isEmpty -> False

Практические применения стека

1. Обратный порядок:

   • Развернуть строку
   • Обратный обход графа

2. Синтаксический анализ:

   • Проверка сбалансированности скобок
   • Вычисление выражений (RPN)

3. Управление памятью:

   • Call stack в процессах
   • Undo/Redo функционал

4. Алгоритмы:

   • DFS (глубинный поиск)
   • Обработка истории навигации

Тестирование

def test_stack():
    stack = Stack()
    
    # Test 1: Пустой стек
    assert stack.isEmpty() == True
    
    # Test 2: Push и peek
    stack.push(1)
    assert stack.peek() == 1
    assert stack.isEmpty() == False
    
    # Test 3: Несколько элементов
    stack.push(2)
    stack.push(3)
    assert stack.peek() == 3
    assert stack.size() == 3
    
    # Test 4: Pop
    assert stack.pop() == 3
    assert stack.pop() == 2
    assert stack.pop() == 1
    assert stack.isEmpty() == True
    
    # Test 5: Исключение при pop пустого стека
    try:
        stack.pop()
        assert False, "Should raise IndexError"
    except IndexError:
        pass
    
    print("All tests passed!")

test_stack()

Сравнение реализаций

На списке (Python list):

• Плюсы: просто, быстро для push/pop, встроенная функциональность
• Минусы: может требовать перераспределения памяти

На связном списке:

• Плюсы: O(1) для всех операций гарантированно, гибкость
• Минусы: дополнительная память на указатели, медленнее на практике

На deque:

• Плюсы: оптимизирован, быстрый
• Минусы: избыточен если не нужны операции с обоих концов

Оптимизации

class OptimizedStack:
    """Стек с дополнительными оптимизациями."""
    
    def __init__(self, initial_capacity=10):
        self.items = [None] * initial_capacity
        self.top_index = -1  # индекс вершины
    
    def push(self, x):
        """Push с автоматическим расширением."""
        if self.top_index + 1 >= len(self.items):
            # Расширяем массив в 2 раза
            self.items.extend([None] * len(self.items))
        
        self.top_index += 1
        self.items[self.top_index] = x
    
    def pop(self):
        if self.isEmpty():
            raise IndexError("pop from empty stack")
        value = self.items[self.top_index]
        self.top_index -= 1
        return value
    
    def peek(self):
        if self.isEmpty():
            raise IndexError("peek from empty stack")
        return self.items[self.top_index]
    
    def isEmpty(self):
        return self.top_index == -1

Ключевые моменты

• LIFO принцип: Последний вошёл — первый вышел
• O(1) операции: Все основные операции константные
• Обработка ошибок: Правильно обрабатываем случаи с пустым стеком
• Универсальность: Работает с любыми типами данных (генерики в TypeScript/Java)
• Практичность: Один из самых используемых структур данных