Для чего нужен Stack?

Для чего нужен Stack?

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

Основной принцип работы

Адд элементы:           Вытаскиваем элементы:

Push(3) →  [3]         Pop() → 3   [ ]
Push(2) →  [3,2]       Pop() → 2   [3]
Push(1) →  [3,2,1]     Pop() → 1   [3,2]
             ↑
        Вершина (Top)

Реализация Stack на Python

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        """Добавить элемент в стек"""
        self.items.append(item)
    
    def pop(self):
        """Извлечь элемент из стека"""
        if self.is_empty():
            return None
        return self.items.pop()
    
    def peek(self):
        """Посмотреть верхний элемент без удаления"""
        if self.is_empty():
            return None
        return self.items[-1]
    
    def is_empty(self):
        """Проверить, пуст ли стек"""
        return len(self.items) == 0
    
    def size(self):
        """Получить размер стека"""
        return len(self.items)
    
    def __str__(self):
        return str(self.items)

# Использование
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack)  # [1, 2, 3]
print(stack.pop())  # 3
print(stack.peek())  # 2

Основные применения Stack

1. Управление вызовом функций (Call Stack)

Это самое фундаментальное применение. Когда программа вызывает функцию, информация о ней помещается в стек вызовов:

def function_a():
    print("A start")
    function_b()
    print("A end")

def function_b():
    print("B start")
    function_c()
    print("B end")

def function_c():
    print("C start")
    print("C end")

function_a()

# Порядок выполнения:
# Call Stack:  []→[A]→[A,B]→[A,B,C]→[A,B]→[A]→[]
# Output:
# A start
# B start
# C start
# C end
# B end
# A end

2. Проверка баланса скобок

def is_balanced_brackets(expression):
    """Проверить, сбалансированы ли скобки"""
    stack = Stack()
    pairs = {')': '(', '}': '{', ']': '['}
    
    for char in expression:
        if char in '({[':
            stack.push(char)
        elif char in ')}]':
            if stack.is_empty() or stack.pop() != pairs[char]:
                return False
    
    return stack.is_empty()

# Примеры
print(is_balanced_brackets("(()[])"))  # True
print(is_balanced_brackets("([)]"))   # False
print(is_balanced_brackets("({[]})")) # True

3. Обратное преобразование выражений (Reverse Polish Notation)

def infix_to_postfix(expression):
    """Преобразование инфиксного выражения в постфиксное"""
    stack = Stack()
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    output = []
    
    for token in expression.split():
        if token.isdigit():
            output.append(token)
        elif token in precedence:
            while (not stack.is_empty() and 
                   stack.peek() in precedence and
                   precedence[stack.peek()] >= precedence[token]):
                output.append(stack.pop())
            stack.push(token)
        elif token == '(':
            stack.push(token)
        elif token == ')':
            while not stack.is_empty() and stack.peek() != '(':
                output.append(stack.pop())
            stack.pop()  # Убрать '('
    
    while not stack.is_empty():
        output.append(stack.pop())
    
    return ' '.join(output)

# Примеры
print(infix_to_postfix("3 + 4 * 5"))      # 3 4 5 * +
print(infix_to_postfix("( 3 + 4 ) * 5"))  # 3 4 + 5 *

4. Вычисление постфиксного выражения

def evaluate_postfix(expression):
    """Вычислить постфиксное выражение"""
    stack = Stack()
    
    for token in expression.split():
        if token.isdigit():
            stack.push(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            
            if token == '+':
                result = a + b
            elif token == '-':
                result = a - b
            elif token == '*':
                result = a * b
            elif token == '/':
                result = a // b
            
            stack.push(result)
    
    return stack.pop()

# Примеры
print(evaluate_postfix("3 4 +"))      # 7
print(evaluate_postfix("3 4 5 * +"))  # 23

5. Отмена/Повтор операций (Undo/Redo)

class TextEditor:
    def __init__(self):
        self.text = ""
        self.undo_stack = Stack()
        self.redo_stack = Stack()
    
    def insert(self, text):
        """Добавить текст"""
        self.undo_stack.push(self.text)
        self.text += text
        self.redo_stack = Stack()  # Очистить redo при новой операции
    
    def delete(self, count):
        """Удалить последние N символов"""
        self.undo_stack.push(self.text)
        self.text = self.text[:-count]
        self.redo_stack = Stack()
    
    def undo(self):
        """Отмена"""
        if not self.undo_stack.is_empty():
            self.redo_stack.push(self.text)
            self.text = self.undo_stack.pop()
    
    def redo(self):
        """Повтор"""
        if not self.redo_stack.is_empty():
            self.undo_stack.push(self.text)
            self.text = self.redo_stack.pop()
    
    def get_text(self):
        return self.text

# Использование
editor = TextEditor()
editor.insert("Hello")
print(editor.get_text())  # "Hello"
editor.insert(" World")
print(editor.get_text())  # "Hello World"
editor.undo()
print(editor.get_text())  # "Hello"
editor.redo()
print(editor.get_text())  # "Hello World"

6. Поиск в глубину (DFS - Depth First Search)

def dfs_iterative(graph, start):
    """Поиск в глубину с использованием стека"""
    stack = Stack()
    visited = set()
    stack.push(start)
    
    while not stack.is_empty():
        vertex = stack.pop()
        if vertex not in visited:
            print(vertex, end=' ')
            visited.add(vertex)
            # Добавить соседей в стек
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.push(neighbor)

# Граф
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

dfs_iterative(graph, 'A')  # A C F E B D

7. Парсинг и компиляция

Стеки используются в парсерах для отслеживания вложенности синтаксических структур:

def parse_html(html):
    """Простой парсер HTML"""
    stack = Stack()
    
    i = 0
    while i < len(html):
        if html[i] == '<':
            j = html.find('>', i)
            tag = html[i+1:j]
            
            if tag.startswith('/'):
                # Закрывающий тег
                if not stack.is_empty() and stack.pop() == tag[1:]:
                    print(f"Closed tag: {tag[1:]}")
            else:
                # Открывающий тег
                stack.push(tag)
                print(f"Opened tag: {tag}")
            
            i = j + 1
        else:
            i += 1
    
    if stack.is_empty():
        print("HTML is well-formed")
    else:
        print("HTML has unclosed tags")

parse_html("<div><p>Hello</p></div>")

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

Когда НЕ использовать Stack

• Когда нужен доступ в середину структуры (используй List)
• Когда нужен произвольный доступ по индексу (используй Array)
• Когда нужен FIFO порядок (используй Queue)

Stack — одна из самых важных и универсальных структур данных. От управления функциями в процессоре до парсинга HTML, стеки везде. Понимание стека критично для любого разработчика.