Посібник зі стеків у Python

Вступ

У той час як деякі структури даних є універсальними та можуть використовуватися в широкому діапазоні програм, інші є спеціалізованими та призначені для вирішення конкретних проблем. Однією з таких спеціалізованих структур, відомою своєю простотою, але надзвичайною корисністю, є стек.

Отже, що таке стек? За своєю суттю стек — це лінійна структура даних, яка слідує за LIFO Принцип (останній прийшов, перший вийшов).. Подумайте про це як про стопку тарілок у кафетерії; ви берете лише ту тарілку, яка знаходиться зверху, а коли кладете нову тарілку, вона йде на вершину стопки.

Останній доданий елемент є першим елементом, який буде видалено

Але чому розуміння стека є вирішальним? Протягом багатьох років стеки знайшли своє застосування в багатьох областях, від керування пам’яттю у ваших улюблених мовах програмування до функції кнопки «Назад» у веб-браузері. Ця внутрішня простота в поєднанні з широкими можливостями застосування робить стек незамінним інструментом в арсеналі розробника.

У цьому посібнику ми детально зануримося в концепції стеків, їх реалізацію, випадки використання та багато іншого. Ми визначимо, що таке стеки, як вони працюють, а потім розглянемо два найпоширеніші способи реалізації структури даних стека в Python.

Фундаментальні поняття структури стекових даних

За своєю суттю стек оманливо простий, але він має нюанси, які надають йому різноманітні застосування в обчислювальній області. Перш ніж занурюватися в його реалізацію та практичне використання, давайте переконаємось у ґрунтовному розумінні основних концепцій стеків.

Принцип LIFO (останній прийшов, перший вийшов).

LIFO є керівним принципом стека. Це означає, що останній елемент, який увійшов у стек, є першим, хто залишив його. Ця характеристика відрізняє стеки від інших лінійних структур даних, таких як черги.

Основні операції

Кожна структура даних визначається операціями, які вона підтримує. Для стеків ці операції прості, але життєво важливі:

• Штовхати – Додає елемент на вершину стека. Якщо стек заповнений, ця операція може призвести до переповнення стека.

• Pop – Вилучає та повертає найвищий елемент стека. Якщо стек порожній, спроба вискочити може спричинити недоповнення стека.

• Peek (або Top) – Спостерігає за найвищим елементом, не видаляючи його. Ця операція корисна, коли ви хочете перевірити поточний верхній елемент, не змінюючи стан стека.

На даний момент важливість структури даних стека та її основоположних концепцій має бути очевидною. Просуваючись вперед, ми зануримося в його реалізації, проливаючи світло на те, як ці фундаментальні принципи перетворюються на практичний код.

Як реалізувати стек з нуля в Python

Зрозумівши основоположні принципи стеків, настав час засукати рукави та заглибитися в практичну сторону речей. Реалізація стека, незважаючи на те, що вона проста, може бути доступна різними способами. У цьому розділі ми розглянемо два основні методи реалізації стека – використання масивів і пов’язаних списків.

Реалізація стека з використанням масивів

Масиви, буття безперервні місця пам'яті, пропонують інтуїтивно зрозумілі засоби представлення стеків. Вони допускають O(1) часову складність для доступу до елементів за індексом, забезпечуючи швидкі операції push, pop та peek. Крім того, масиви можуть бути більш ефективними для використання пам’яті, оскільки немає додаткових вказівників, як у зв’язаних списках.

З іншого боку, традиційні масиви мають фіксований розмір, тобто після ініціалізації їх неможливо змінити. Це може призвести до a stack overflow якщо не стежити. Це можна подолати за допомогою динамічних масивів (наприклад, Python list), який може змінювати розмір, але ця операція досить дорога.

Закінчивши все це, давайте почнемо реалізацію нашого класу стека за допомогою масивів у Python. Перш за все, давайте створимо сам клас із конструктором, який приймає розмір стека як параметр:

class Stack: def __init__(self, size): self.size = size self.stack = [None] * size self.top = -1

Як бачите, ми зберегли три значення в нашому класі. The size це бажаний розмір стека, stack це фактичний масив, який використовується для представлення структури даних стека, і top є індексом останнього елемента в stack масив (верхня частина стека).

Відтепер ми створимо та пояснимо один метод для кожної з основних операцій зі стеком. Кожен із цих методів буде міститися в Stack клас, який ми щойно створили.

Давайте почнемо з push() метод. Як обговорювалося раніше, операція push додає елемент на вершину стека. Перш за все, ми перевіримо, чи залишилося в стеку місце для елемента, який ми хочемо додати. Якщо стек повний, ми піднімемо Stack Overflow виняток. В іншому випадку ми просто додамо елемент і налаштуємо top та stack відповідно:

def push(self, item): if self.top == self.size - 1: raise Exception("Stack Overflow") self.top += 1 self.stack[self.top] = item

Тепер ми можемо визначити метод видалення елемента з вершини стека – the pop() метод. Перш ніж спробувати видалити елемент, нам потрібно перевірити, чи є елементи в стеку, тому що немає сенсу намагатися витягнути елемент із порожнього стека:

def pop(self): if self.top == -1: raise Exception("Stack Underflow") item = self.stack[self.top] self.top -= 1 return item

Нарешті, ми можемо визначити peek() метод, який просто повертає значення елемента, який зараз знаходиться на вершині стека:

def peek(self): if self.top == -1: raise Exception("Stack is empty") return self.stack[self.top]

І це все! Тепер у нас є клас, який реалізує поведінку стеків за допомогою списків у Python.

Реалізація стека за допомогою пов’язаних списків

Зв'язані списки, будучи динамічні структури даних, може легко рости та зменшуватися, що може бути корисним для впровадження стеків. Оскільки пов’язані списки виділяють пам’ять за потреби, стек може динамічно збільшуватися та зменшуватися без необхідності явного зміни розміру. Ще одна перевага використання пов’язаних списків для реалізації стеків полягає в тому, що операції push і pop вимагають лише простих змін покажчика. Недоліком цього є те, що кожен елемент у зв’язаному списку має додатковий покажчик, який споживає більше пам’яті порівняно з масивами.

Як ми вже обговорювали в «Пов’язані списки Python» статті, перше, що нам потрібно реалізувати перед фактичним пов’язаним списком, це клас для окремого вузла:

class Node: def __init__(self, data): self.data = data self.next = None

Ця реалізація зберігає лише дві точки даних – значення, що зберігається у вузлі (data) і посилання на наступний вузол (next).

Тепер ми можемо перейти до самого класу стека. Конструктор буде трохи відрізнятися від попереднього. Він міститиме лише одну змінну – посилання на вузол у верхній частині стека:

class Stack: def __init__(self): self.top = None

Як і очікувалося, push() метод додає новий елемент (у цьому випадку вузол) на вершину стека:

def push(self, item): node = Node(item) if self.top: node.next = self.top self.top = node

Команда pop() метод перевіряє наявність елементів у стеку та видаляє найвищий, якщо стек не порожній:

def pop(self): if not self.top: raise Exception("Stack Underflow") item = self.top.data self.top = self.top.next return item

Нарешті, peek() метод просто читає значення елемента з вершини стека (якщо він є):

def peek(self): if not self.top: raise Exception("Stack is empty") return self.top.data

Вибір між масивами та пов’язаними списками залежить від конкретних вимог і обмежень програми.

Як реалізувати стек за допомогою вбудованих структур Python

Для багатьох розробників створення стека з нуля, хоч і освітнє, може бути не найефективнішим способом використання стека в реальних програмах. На щастя, багато популярних мов програмування оснащені вбудованими структурами даних і класами, які природно підтримують операції зі стеком. У цьому розділі ми дослідимо пропозиції Python у цьому відношенні.

Python, будучи універсальною та динамічною мовою, не має спеціального класу стека. Однак його вбудовані структури даних, зокрема списки та клас deque з collections модуль, може без зусиль служити стеками.

Використання списків Python як стеків

Списки Python можуть досить ефективно емулювати стек завдяки їх динамічній природі та наявності таких методів, як append() та pop().

• Операція Push – Додати елемент на вершину стека так само просто, як використовувати append() метод:

  stack = []
  stack.append('A')
  stack.append('B')
  

• Поп-операція – Видалити найвищий елемент можна за допомогою pop() метод без аргументів:

  top_element = stack.pop() 

• Операція Peek Доступ до вершини без вискакування можна зробити за допомогою негативного індексування:

  top_element = stack[-1] 

використання деке Клас від Колекції Модулі

Команда deque (скорочення від double-ended queue) — ще один універсальний інструмент для стекових реалізацій. Він оптимізований для швидкого додавання та висування з обох кінців, що робить його дещо ефективнішим для операцій зі стеком, ніж зі списками.

• Ініціалізація:

  from collections import deque
  stack = deque()
  

• Операція Push – Подібно до списків, append() використовується метод:

  stack.append('A')
  stack.append('B')
  

• Поп-операція – Як списки, pop() метод виконує роботу:

  top_element = stack.pop() 

• Операція Peek – Підхід такий самий, як і зі списками:

  top_element = stack[-1] 

Коли використовувати який?

Незважаючи на те, що як списки, так і дві групи можна використовувати як стеки, якщо ви в основному використовуєте структуру як стек (з додаванням і висуванням з одного кінця), deque може бути трохи швидшим завдяки його оптимізації. Однак для більшості практичних цілей і якщо ви не маєте справу з критично важливими для продуктивності програмами, списків Python має бути достатньо.

Потенційні проблеми, пов’язані зі стеком, і способи їх подолання

Хоча стеки неймовірно універсальні та ефективні, як і будь-яка інша структура даних, вони не захищені від потенційних пасток. Дуже важливо усвідомлювати ці проблеми під час роботи зі стеками та мати стратегії для їх вирішення. У цьому розділі ми зануримося в деякі поширені проблеми, пов’язані зі стеком, і дослідимо способи їх подолання.

переповнення стека

Це відбувається, коли робиться спроба помістити елемент у стек, який досяг максимальної ємності. Це особливо проблема в середовищах, де розмір стека фіксований, як-от у певних сценаріях програмування низького рівня або рекурсивних викликах функцій.

Якщо ви використовуєте стеки на основі масивів, подумайте про перехід на динамічні масиви або реалізації зв’язаних списків, які самі змінюють розмір. Іншим кроком у запобіганні переповненню стека є постійний моніторинг розміру стека, особливо перед операціями надсилання, і надання чітких повідомлень про помилки або підказок щодо переповнення стека.

Якщо переповнення стека відбувається через надмірну кількість рекурсивних викликів, розгляньте ітераційні рішення або збільште обмеження рекурсії, якщо це дозволяє середовище.

Стек Underflow

Це трапляється, коли є спроба витягнути елемент із порожнього стека. Щоб цього не сталося, завжди перевіряйте, чи стек порожній, перш ніж виконувати операції висунення або перегляду. Повернути чітке повідомлення про помилку або витончено впоратися з недоповненням без збою програми.

У середовищах, де це прийнятно, розгляньте можливість повернення спеціального значення під час витягування з порожнього стека, щоб позначити недійсність операції.

Обмеження пам'яті

У середовищах з обмеженим обсягом пам’яті навіть динамічна зміна розміру стеків (наприклад, на основі зв’язаних списків) може призвести до виснаження пам’яті, якщо вони стануть занадто великими. Тому слідкуйте за загальним використанням пам’яті програмою та зростанням стека. Можливо, запровадьте м’яке обмеження розміру стека.

Занепокоєння щодо безпеки потоку

У багатопоточних середовищах одночасні операції зі спільним стеком різними потоками можуть призвести до неузгодженості даних або несподіваної поведінки. Потенційними рішеннями цієї проблеми можуть бути:

• Мьютекси та блокування – Використовуйте м’ютекси (об’єкти взаємного виключення) або блокування, щоб гарантувати, що лише один потік може виконувати операції зі стеком у певний момент часу.
• Атомні операції – Використовуйте атомарні операції, якщо вони підтримуються середовищем, щоб забезпечити узгодженість даних під час операцій push і pop.
• Потокові локальні стеки – У сценаріях, коли кожному потоку потрібен свій стек, розгляньте можливість використання локального сховища потоку, щоб надати кожному потоку окремий екземпляр стека.

Незважаючи на те, що стеки дійсно потужні, усвідомлення їх потенційних проблем і активне впровадження рішень забезпечать надійні та безпомилкові програми. Розпізнати ці підводні камені – це половина успіху – інша половина полягає в застосуванні найкращих практик для їх ефективного вирішення.

Висновок

Стеки, незважаючи на свою, здавалося б, просту природу, лежать в основі багатьох фундаментальних операцій у світі комп’ютерів. Від розбору складних математичних виразів до керування викликами функцій, їхня корисність є широкою та важливою. Коли ми ознайомилися з тонкощами цієї структури даних, стало зрозуміло, що її перевага полягає не лише в її ефективності, але й у її універсальності.

Однак, як і з усіма інструментами, його ефективність залежить від того, як його використовують. Просто переконайтеся, що ви повністю розумієте його принципи, потенційні підводні камені та найкращі практики, щоб переконатися, що ви можете використовувати справжню силу стеків. Незалежно від того, чи впроваджуєте ви його з нуля, чи використовуєте вбудовані засоби таких мов, як Python, саме уважне застосування цих структур даних виділить ваші рішення.

• Розповсюдження контенту та PR на основі SEO. Отримайте посилення сьогодні.
• PlatoData.Network Vertical Generative Ai. Додайте собі сили. Доступ тут.
• PlatoAiStream. Web3 Intelligence. Розширення знань. Доступ тут.
• ПлатонЕСГ. вуглець, CleanTech, Енергія, Навколишнє середовище, Сонячна, Поводження з відходами. Доступ тут.
• PlatoHealth. Розвідка про біотехнології та клінічні випробування. Доступ тут.
• джерело: https://stackabuse.com/guide-to-stacks-in-python/