В чем разница между стеком и очередью?

Различия между стеком (Stack) и очередью (Queue)

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

Стек (Stack)

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

Принцип работы:

1. Элементы добавляются в верх стека (push)
2. Элементы удаляются из верха стека (pop)
3. Последний добавленный элемент — первый удаляемый

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)

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

print(stack.pop())   # 3 (последний добавленный)
print(stack.pop())   # 2
print(stack.pop())   # 1
print(stack.pop())   # None (стек пуст)

Визуально:

Push:           Stack:          Pop:
stack.push(1)   [1]             stack.pop() → 3
stack.push(2)   [1, 2]          stack.pop() → 2
stack.push(3)   [1, 2, 3] ← top stack.pop() → 1

Очередь (Queue)

Очередь — это структура данных, которая работает по принципу FIFO (First In, First Out — первый пришёл, первый ушёл).

Принцип работы:

1. Элементы добавляются в конец очереди (enqueue)
2. Элементы удаляются из начала очереди (dequeue)
3. Первый добавленный элемент — первый удаляемый

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        """Добавить элемент в конец очереди"""
        self.items.append(item)
    
    def dequeue(self):
        """Удалить и вернуть элемент из начала очереди"""
        if self.is_empty():
            return None
        return self.items.popleft()
    
    def front(self):
        """Посмотреть первый элемент без удаления"""
        if self.is_empty():
            return None
        return self.items[0]
    
    def is_empty(self):
        """Проверить, пуста ли очередь"""
        return len(self.items) == 0
    
    def size(self):
        """Получить размер очереди"""
        return len(self.items)

# Пример использования
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print(queue.dequeue())  # 1 (первый добавленный)
print(queue.dequeue())  # 2
print(queue.dequeue())  # 3
print(queue.dequeue())  # None (очередь пуста)

Визуально:

Enqueue:            Queue:           Dequeue:
queue.enqueue(1)    [1]              queue.dequeue() → 1
queue.enqueue(2)    [1, 2]           queue.dequeue() → 2
queue.enqueue(3)    [1, 2, 3]        queue.dequeue() → 3
               ↑front        back↑

Таблица сравнения

Практические примеры

Стек: Проверка скобок

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

# Примеры
print(is_balanced("(a + b) * [c]"))  # True
print(is_balanced("(a + b * [c)"))   # False

Очередь: Обработка задач

class TaskProcessor:
    def __init__(self):
        self.task_queue = Queue()
    
    def add_task(self, task):
        """Добавить задачу в очередь"""
        self.task_queue.enqueue(task)
        print(f"Task added: {task}")
    
    def process_next(self):
        """Обработать следующую задачу"""
        task = self.task_queue.dequeue()
        if task:
            print(f"Processing: {task}")
            return task
        else:
            print("No tasks in queue")
            return None

# Пример
processor = TaskProcessor()
processor.add_task("Task 1")
processor.add_task("Task 2")
processor.add_task("Task 3")

processor.process_next()  # Task 1
processor.process_next()  # Task 2
processor.process_next()  # Task 3

Стек: Отмена действий (Undo)

class TextEditor:
    def __init__(self):
        self.text = ""
        self.undo_stack = Stack()
    
    def type(self, char):
        """Добавить символ и сохранить в стек отмены"""
        self.undo_stack.push(self.text)
        self.text += char
        print(f"Text: {self.text}")
    
    def undo(self):
        """Отменить последнее действие"""
        previous_state = self.undo_stack.pop()
        if previous_state is not None:
            self.text = previous_state
            print(f"Undo. Text: {self.text}")

# Пример
editor = TextEditor()
editor.type("H")  # Text: H
editor.type("i")  # Text: Hi
editor.type("!")  # Text: Hi!
editor.undo()     # Undo. Text: Hi
editor.undo()     # Undo. Text: H

Очередь: BFS поиск в графе

from collections import deque

def bfs(graph, start):
    """Поиск в ширину (Breadth-First Search)"""
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []
    
    while queue:
        node = queue.popleft()  # dequeue
        result.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)  # enqueue
    
    return result

# Пример графа
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['B'],
    'E': ['C']
}

print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E']

Использование в Python

Stack (есть встроенное в Python):

# list работает как стек
stack = []
stack.append(1)    # push
stack.append(2)
stack.pop()        # 2

# Или используй collections.deque
from collections import deque
stack = deque()
stack.append(1)    # push
stack.pop()        # 1 (из конца)

Queue (лучше использовать collections.deque):

# НЕ используй list для очереди (медленно)
# queue = []
# queue.append(1)      # O(1)
# queue.pop(0)         # O(n) - медленно!

# ИСПОЛЬЗУЙ collections.deque
from collections import deque
queue = deque()
queue.append(1)        # enqueue - O(1)
queue.popleft()        # dequeue - O(1)

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

Используй Стек когда:

• Проверка скобок/parenthesis matching
• Отмена действий (undo/redo)
• Рекурсия и обход в глубину (DFS)
• Парсинг выражений
• Навигация браузера (back button)

Используй Очередь когда:

• Обработка задач по очереди
• BFS поиск в графе
• Печать документов
• Буферизация данных
• Симуляция реальных очередей

Итог

Стек (LIFO) — последний пришёл, первый ушёл. Используется для отмены, навигации и поиска в глубину. Очередь (FIFO) — первый пришёл, первый ушёл. Используется для обработки задач по порядку и поиска в ширину. Выбор зависит от порядка обработки данных, который требует ваша задача.