Стек и Очередь. Примеры на Python
https://t.me/solidityset
Пример 1
# Создаем пустой стек
stack = []
# Операция Push - добавляем элементы
print("=== Добавление элементов ===")
stack.append("Первый")
print(f"После добавления 'Первый': {stack}")
stack.append("Второй")
print(f"После добавления 'Второй': {stack}")
stack.append("Третий")
print(f"После добавления 'Третий': {stack}")
# Операция Peek - смотрим, что на вершине
print(f"\nЭлемент на вершине: {stack[-1]}")
# Операция Pop - удаляем элементы
print("\n=== Удаление элементов ===")
removed = stack.pop()
print(f"Удален: {removed}")
print(f"Текущий стек: {stack}")
removed = stack.pop()
print(f"Удален: {removed}")
print(f"Текущий стек: {stack}")
# Проверка на пустоту
print(f"\nСтек пуст? {len(stack) == 0}")
Пример 2
=== Добавление элементов ===
После добавления 'Первый': ['Первый']
После добавления 'Второй': ['Первый', 'Второй']
После добавления 'Третий': ['Первый', 'Второй', 'Третий']
Элемент на вершине: Третий
=== Удаление элементов ===
Удален: Третий
Текущий стек: ['Первый', 'Второй']
Удален: Второй
Текущий стек: ['Первый']
Стек пуст? False
Пример 3
def check_brackets(expression):
"""
Проверяет, правильно ли расставлены скобки в выражении
Например: "(())" - правильно, "(()" - неправильно
"""
stack = []
# Пары открывающих и закрывающих скобок
pairs = {'(': ')', '[': ']', '{': '}'}
for char in expression:
# Если открывающая скобка - кладем в стек
if char in pairs.keys():
stack.append(char)
# Если закрывающая скобка
elif char in pairs.values():
# Стек пуст - значит нет пары для закрывающей скобки
if not stack:
return False
# Проверяем, соответствует ли закрывающая скобка последней открывающей
last_opening = stack.pop()
if pairs[last_opening] != char:
return False
# В конце стек должен быть пуст
return len(stack) == 0
# Тестирование
test_cases = ["(())", "(()", "{[()]}", "([)]", ""]
for test in test_cases:
result = check_brackets(test)
print(f"'{test}' - {'✓ Правильно' if result else '✗ Неправильно'}")
Пример 4
Начало очереди Конец очереди
(здесь удаляем) (сюда добавляем)
↓ ↓
┌─────┬─────┬─────┬─────┐
│ A │ B │ C │ D │
└─────┴─────┴─────┴─────┘
Пример 5
from collections import deque
# Создаем пустую очередь
# deque - это специальная структура данных для эффективной работы с очередями
queue = deque()
# Операция Enqueue - добавляем элементы в конец
print("=== Добавление в очередь ===")
queue.append("Клиент 1")
print(f"Добавлен 'Клиент 1': {list(queue)}")
queue.append("Клиент 2")
print(f"Добавлен 'Клиент 2': {list(queue)}")
queue.append("Клиент 3")
print(f"Добавлен 'Клиент 3': {list(queue)}")
# Смотрим, кто первый в очереди
print(f"\nПервый в очереди: {queue[0]}")
# Операция Dequeue - обслуживаем (удаляем) клиентов из начала
print("\n=== Обслуживание клиентов ===")
served = queue.popleft() # popleft удаляет из начала
print(f"Обслужен: {served}")
print(f"Осталось в очереди: {list(queue)}")
served = queue.popleft()
print(f"Обслужен: {served}")
print(f"Осталось в очереди: {list(queue)}")
# Добавляем нового клиента
queue.append("Клиент 4")
print(f"\nДобавлен 'Клиент 4': {list(queue)}")
# Проверка на пустоту
print(f"\nОчередь пуста? {len(queue) == 0}")
Пример 6
=== Добавление в очередь ===
Добавлен 'Клиент 1': ['Клиент 1']
Добавлен 'Клиент 2': ['Клиент 1', 'Клиент 2']
Добавлен 'Клиент 3': ['Клиент 1', 'Клиент 2', 'Клиент 3']
Первый в очереди: Клиент 1
=== Обслуживание клиентов ===
Обслужен: Клиент 1
Осталось в очереди: ['Клиент 2', 'Клиент 3']
Обслужен: Клиент 2
Осталось в очереди: ['Клиент 3']
Добавлен 'Клиент 4': ['Клиент 3', 'Клиент 4']
Очередь пуста? False
Пример 7
from collections import deque
import time
class CashRegister:
"""Класс, имитирующий работу кассы в магазине"""
def __init__(self):
self.queue = deque()
self.served_count = 0
def add_customer(self, name):
"""Добавить покупателя в очередь"""
self.queue.append(name)
print(f"👤 {name} встал в очередь. Людей в очереди: {len(self.queue)}")
def serve_customer(self):
"""Обслужить покупателя"""
if not self.queue:
print("❌ Очередь пуста, никого обслуживать")
return
customer = self.queue.popleft()
self.served_count += 1
print(f"✓ Обслужен: {customer}. Осталось в очереди: {len(self.queue)}")
def show_queue(self):
"""Показать текущую очередь"""
if not self.queue:
print("Очередь пуста")
else:
print(f"Очередь: {' ← '.join(list(self.queue))}")
def get_stats(self):
"""Показать статистику"""
print(f"\n📊 Статистика: обслужено {self.served_count} чел., в очереди {len(self.queue)} чел.")
# Симуляция работы кассы
print("🏪 Открытие магазина\n")
cash_register = CashRegister()
# Приходят покупатели
cash_register.add_customer("Анна")
cash_register.add_customer("Борис")
cash_register.add_customer("Виктор")
print("\n--- Текущее состояние ---")
cash_register.show_queue()
# Обслуживаем
print("\n--- Начинаем обслуживание ---")
cash_register.serve_customer()
cash_register.serve_customer()
# Приходит еще один покупатель
print()
cash_register.add_customer("Галина")
cash_register.show_queue()
cash_register.serve_customer()
cash_register.serve_customer()
# Статистика
cash_register.get_stats()
Пример 8
class QueueUsingStacks:
"""Очередь, реализованная с помощью двух стеков"""
def __init__(self):
self.stack_input = [] # Стек для добавления
self.stack_output = [] # Стек для удаления
def enqueue(self, item):
"""Добавить элемент в очередь"""
# Просто кладем в первый стек
self.stack_input.append(item)
print(f"➕ Добавлен: {item}")
def dequeue(self):
"""Удалить элемент из очереди"""
# Если стек для удаления пуст - перекладываем элементы
if not self.stack_output:
if not self.stack_input:
print("❌ Очередь пуста!")
return None
# Перекладываем все элементы из input в output
print("🔄 Перекладываем элементы между стеками...")
while self.stack_input:
self.stack_output.append(self.stack_input.pop())
# Теперь можем удалить элемент из стека output
item = self.stack_output.pop()
print(f"➖ Удален: {item}")
return item
def peek(self):
"""Посмотреть первый элемент без удаления"""
if not self.stack_output:
if not self.stack_input:
return None
while self.stack_input:
self.stack_output.append(self.stack_input.pop())
return self.stack_output[-1] if self.stack_output else None
def is_empty(self):
"""Проверить, пуста ли очередь"""
return len(self.stack_input) == 0 and len(self.stack_output) == 0
def show_state(self):
"""Показать состояние стеков"""
print(f" Стек Input: {self.stack_input}")
print(f" Стек Output: {self.stack_output}")
# Тестирование
print("=== Реализация очереди через два стека ===\n")
queue = QueueUsingStacks()
# Добавляем элементы
queue.enqueue("A")
queue.enqueue("B")
queue.enqueue("C")
queue.show_state()
print("\n--- Удаляем элементы ---")
queue.dequeue() # Должен удалиться A (первый добавленный)
queue.show_state()
print()
queue.dequeue() # Должен удалиться B
queue.show_state()
print("\n--- Добавляем новый элемент ---")
queue.enqueue("D")
queue.show_state()
print()
queue.dequeue() # Должен удалиться C
queue.dequeue() # Должен удалиться D
Пример 9
class BrowserHistory:
"""Упрощенная модель истории браузера"""
def __init__(self):
self.history_stack = []
self.current_page = "Домашняя страница"
def visit(self, url):
"""Посетить новую страницу"""
# Сохраняем текущую страницу в историю
self.history_stack.append(self.current_page)
self.current_page = url
print(f"📄 Открыта страница: {url}")
def back(self):
"""Вернуться назад"""
if not self.history_stack:
print("❌ Нельзя вернуться назад - это первая страница")
return
previous_page = self.history_stack.pop()
print(f"⬅️ Возврат на: {previous_page}")
self.current_page = previous_page
def current(self):
"""Показать текущую страницу"""
print(f"Вы сейчас на: {self.current_page}")
# Демонстрация
browser = BrowserHistory()
browser.current()
browser.visit("google.com")
browser.visit("github.com")
browser.visit("stackoverflow.com")
browser.current()
print("\n--- Нажимаем кнопку Назад ---")
browser.back()
browser.current()
browser.back()
browser.current()
Пример 10
class TextEditor:
"""Текстовый редактор с функцией отмены"""
def __init__(self):
self.text = ""
self.history = [] # Стек для истории изменений
def write(self, new_text):
"""Добавить текст"""
# Сохраняем текущее состояние в историю перед изменением
self.history.append(self.text)
self.text += new_text
print(f"✍️ Написано: '{new_text}'")
print(f" Текст сейчас: '{self.text}'")
def undo(self):
"""Отменить последнее действие"""
if not self.history:
print("❌ Нечего отменять")
return
# Восстанавливаем предыдущее состояние
self.text = self.history.pop()
print(f"↩️ Отмена. Текст сейчас: '{self.text}'")
def show(self):
"""Показать текущий текст"""
print(f"📝 Текущий текст: '{self.text}'")
# Демонстрация
editor = TextEditor()
editor.write("Привет, ")
editor.write("мир!")
editor.write(" Как дела?")
print("\n--- Отмена последнего действия ---")
editor.undo()
print("\n--- Еще одна отмена ---")
editor.undo()
editor.show()
Пример 11
def function_A():
print(" → Вход в function_A")
function_B()
print(" ← Выход из function_A")
def function_B():
print(" → Вход в function_B")
function_C()
print(" ← Выход из function_B")
def function_C():
print(" → Вход в function_C")
print(" ← Выход из function_C")
print("Стек вызовов:\n")
function_A()
Пример 12
def validate_html_tags(html):
"""Проверка правильности вложенности HTML-тегов"""
stack = []
i = 0
while i < len(html):
# Ищем открывающий тег
if html[i] == '<':
# Находим конец тега
end = html.find('>', i)
tag = html[i+1:end]
# Закрывающий тег
if tag.startswith('/'):
tag_name = tag[1:]
if not stack or stack[-1] != tag_name:
return False, f"Ошибка: неожиданный закрывающий тег </{tag_name}>"
stack.pop()
# Открывающий тег (игнорируем самозакрывающиеся)
elif not tag.endswith('/'):
stack.append(tag)
i = end + 1
else:
i += 1
if stack:
return False, f"Ошибка: не закрыт тег <{stack[-1]}>"
return True, "HTML валиден!"
# Тесты
test_cases = [
"<div><p>Текст</p></div>", # Правильно
"<div><p>Текст</div></p>", # Неправильно - теги перепутаны
"<div><p>Текст</p>", # Неправильно - не закрыт div
"<img src='pic.jpg' />", # Правильно - самозакрывающийся тег
]
for html in test_cases:
valid, message = validate_html_tags(html)
status = "✓" if valid else "✗"
print(f"{status} '{html}'")
print(f" {message}\n")
Пример 13
from collections import deque
class Queue:
"""
Очередь на основе collections.deque
Демонстрирует все основные операции
"""
def __init__(self):
self.items = deque()
def enqueue(self, item):
"""
Добавить элемент в конец очереди
Время выполнения: O(1)
"""
self.items.append(item)
print(f"➕ Добавлен в очередь: {item}")
def dequeue(self):
"""
Удалить и вернуть элемент из начала очереди
Время выполнения: O(1)
"""
if self.is_empty():
print("❌ Очередь пуста!")
return None
item = self.items.popleft() # popleft - удаляет из начала
print(f"➖ Удален из очереди: {item}")
return item
def front(self):
"""
Посмотреть первый элемент без удаления
Время выполнения: O(1)
"""
if self.is_empty():
return None
return self.items[0]
def is_empty(self):
"""
Проверить, пуста ли очередь
Время выполнения: O(1)
"""
return len(self.items) == 0
def size(self):
"""
Получить количество элементов в очереди
Время выполнения: O(1)
"""
return len(self.items)
def display(self):
"""Показать все элементы очереди"""
if self.is_empty():
print("Очередь пуста")
else:
print(f"Очередь (начало → конец): {list(self.items)}")
def clear(self):
"""Очистить очередь"""
self.items.clear()
print("🗑️ Очередь очищена")
# ============================================
# Демонстрация работы очереди
# ============================================
print("=== Создание и наполнение очереди ===\n")
queue = Queue()
# Операция Enqueue - добавление элементов
queue.enqueue("Задача 1")
queue.enqueue("Задача 2")
queue.enqueue("Задача 3")
queue.enqueue("Задача 4")
print("\n--- Состояние очереди ---")
queue.display()
print(f"Размер очереди: {queue.size()}")
print(f"Первый в очереди: {queue.front()}")
# Операция Dequeue - удаление элементов
print("\n=== Обработка задач (Dequeue) ===\n")
queue.dequeue() # Удалится "Задача 1"
queue.dequeue() # Удалится "Задача 2"
print("\n--- Состояние после обработки ---")
queue.display()
print(f"Размер очереди: {queue.size()}")
# Добавляем новые элементы
print("\n=== Добавление новых задач ===\n")
queue.enqueue("Задача 5")
queue.enqueue("Задача 6")
queue.display()
# Обрабатыва все оставшиеся задачи
print("\n=== Обработка всех оставшихся задач ===\n")
while not queue.is_empty():
queue.dequeue()
queue.display()
# Попытка удалить из пустой очереди
print("\n=== Попытка удалить из пустой очереди ===\n")
queue.dequeue()
Пример 14
from collections import deque
from datetime import datetime
class Order:
"""Класс для представления заказа"""
def __init__(self, order_id, customer, items):
self.order_id = order_id
self.customer = customer
self.items = items
self.timestamp = datetime.now().strftime("%H:%M:%S")
def __str__(self):
return f"Заказ #{self.order_id} ({self.customer}) - {', '.join(self.items)} [{self.timestamp}]"
class OrderProcessingSystem:
"""Система обработки заказов с использованием очереди"""
def __init__(self):
self.queue = deque()
self.processed_orders = []
self.order_counter = 1
def place_order(self, customer, items):
"""Разместить новый заказ"""
order = Order(self.order_counter, customer, items)
self.queue.append(order)
self.order_counter += 1
print(f"📥 Новый заказ: {order}")
return order
def process_next_order(self):
"""Обработать следующий заказ"""
if not self.queue:
print("❌ Нет заказов для обработки")
return None
order = self.queue.popleft()
self.processed_orders.append(order)
print(f"✅ Обработан: {order}")
return order
def show_pending_orders(self):
"""Показать ожидающие заказы"""
if not self.queue:
print("Нет ожидающих заказов")
return
print(f"\n📋 Ожидающие заказы ({len(self.queue)}):")
for i, order in enumerate(self.queue, 1):
print(f" {i}. {order}")
def show_statistics(self):
"""Показать статистику"""
print(f"\n📊 Статистика:")
print(f" • Обработано заказов: {len(self.processed_orders)}")
print(f" • В очереди: {len(self.queue)}")
print(f" • Всего заказов: {self.order_counter - 1}")
# Демонстрация работы системы
print("🏪 Система обработки заказов ресторана\n")
system = OrderProcessingSystem()
# Поступают заказы
system.place_order("Анна", ["Пицца", "Сок"])
system.place_order("Борис", ["Бургер", "Картофель фри"])
system.place_order("Виктор", ["Салат", "Вода"])
# Показываем очередь
system.show_pending_orders()
# Обрабатываем заказы
print("\n--- Начинаем обработку ---\n")
system.process_next_order()
system.process_next_order()
# Приходит новый заказ
print()
system.place_order("Галина", ["Суп", "Хлеб"])
# Показываем текущую очередь
system.show_pending_orders()
# Обрабатываем оставшиеся заказы
print("\n--- Обработка оставшихся заказов ---\n")
while system.queue:
system.process_next_order()
# Итоговая статистика
system.show_statistics()
P.S. Примеры были написаны для канала SoliditySet в рамках цикла постов про алгоритмы