Вступ
У той час як деякі структури даних є універсальними та можуть використовуватися в широкому діапазоні програм, інші є спеціалізованими та призначені для вирішення конкретних проблем. Однією з таких спеціалізованих структур, відомою своєю простотою, але надзвичайною корисністю, є стек.
Отже, що таке стек? За своєю суттю стек — це лінійна структура даних, яка слідує за 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
Ознайомтеся з нашим практичним практичним посібником із вивчення Git з передовими методами, прийнятими в галузі стандартами та включеною шпаргалкою. Припиніть гуглити команди Git і фактично вчитися це!
Ця реалізація зберігає лише дві точки даних – значення, що зберігається у вузлі (data
) і посилання на наступний вузол (next
).
Наша серія з трьох частин про пов’язані списки в Python:
Тепер ми можемо перейти до самого класу стека. Конструктор буде трохи відрізнятися від попереднього. Він міститиме лише одну змінну – посилання на вузол у верхній частині стека:
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
Примітка: Інтерфейс обох Stack
класи однакові – єдина відмінність полягає у внутрішній реалізації методів класу. Це означає, що ви можете легко перемикатися між різними реалізаціями, не турбуючись про внутрішні властивості класів.
Вибір між масивами та пов’язаними списками залежить від конкретних вимог і обмежень програми.
Як реалізувати стек за допомогою вбудованих структур 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 має бути достатньо.
Примітка: У цьому розділі розглядаються вбудовані пропозиції 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/
- : має
- :є
- : ні
- :де
- $UP
- 1
- 14
- 20
- 7
- 8
- 9
- a
- МЕНЮ
- прийнятний
- доступ до
- відповідно
- досягнутий
- активно
- фактичний
- насправді
- додавати
- доданий
- додати
- Додатковий
- адреса
- Додає
- Прийняття
- Оповіщення
- ВСІ
- виділяти
- дозволяти
- вже
- Також
- завжди
- an
- та
- Інший
- будь-який
- крім
- додаток
- застосування
- підхід
- ЕСТЬ
- області
- аргумент
- навколо
- масив
- арсенал
- стаття
- AS
- At
- спроба
- спроба
- знати
- заснований
- основний
- Бій
- BE
- оскільки
- перед тим
- поведінка
- поведінки
- за
- буття
- корисний
- користь
- КРАЩЕ
- передового досвіду
- між
- border
- обидва
- широкий
- браузер
- Створюємо
- вбудований
- але
- by
- Виклики
- CAN
- кришка
- потужність
- випадок
- випадків
- Викликати
- певний
- проблеми
- Зміни
- характеристика
- перевірка
- Перевірки
- вибір
- клас
- класів
- ясно
- код
- Колекції
- комбінований
- Приходити
- загальний
- порівняний
- комплекс
- складність
- обчислювальна
- обчислення
- концепція
- поняття
- висновок
- Вважати
- обмеження
- містити
- містяться
- постійно
- Core
- дорого
- Гуркіт
- створювати
- створений
- вирішальне значення
- Поточний
- В даний час
- дані
- Структура даних
- справу
- присвячених
- глибокий
- глибоке занурення
- визначати
- певний
- заглиблюватися
- залежить
- призначений
- бажаний
- Незважаючи на
- Розробник
- розробників
- різниця
- різний
- обговорювалися
- занурення
- дайвінг
- робить
- байдуже
- домен
- Дон
- зроблений
- зворотний бік
- два
- під час
- динамічний
- динамічно
- кожен
- легко
- освітній
- фактично
- ефективність
- ефективність
- ефективний
- легко
- елемент
- елементи
- кінець
- закінчується
- забезпечувати
- забезпечення
- Що натомість? Створіть віртуальну версію себе у
- Входить
- Навколишнє середовище
- середовищах
- обладнаний
- помилка
- особливо
- сутність
- істотний
- Навіть
- Кожен
- очевидний
- приклад
- виняток
- виконання
- очікуваний
- Пояснювати
- дослідити
- вирази
- очей
- засоби
- ШВИДКО
- швидше
- Улюблений
- кінчики пальців
- Перший
- фіксованою
- Сфокусувати
- слідує
- для
- На щастя
- Вперед
- знайдений
- від
- Повний
- функція
- функціональність
- фундаментальний
- отримати
- отримання
- Git
- Давати
- даний
- йде
- надавати
- Рости
- Зростання
- керівництво
- Половина
- рука
- обробляти
- практичний
- Відбувається
- відбувається
- збруя
- Мати
- голова
- допомога
- hover
- Як
- How To
- Однак
- HTTPS
- ICON
- if
- картина
- здійснювати
- реалізація
- реалізації
- реалізації
- implements
- in
- включені
- невідповідності
- Augmenter
- неймовірно
- дійсно
- індекс
- екземпляр
- інтерфейс
- внутрішній
- в
- сутнісний
- вводити
- Вступ
- інтуїтивний
- питання
- питання
- IT
- ЙОГО
- сам
- робота
- просто
- тримати
- відомий
- мова
- мови
- великий
- останній
- вести
- вивчення
- Залишати
- залишити
- дозволяти
- Важіль
- використання
- LG
- лежить
- світло
- як
- МЕЖА
- пов'язаний
- список
- списки
- трохи
- ll
- Волосся
- подивитися
- made
- зробити
- РОБОТИ
- Робить
- управління
- управління
- багато
- математичний
- максимальний
- Може..
- сенс
- засоби
- пам'ять
- повідомлення
- повідомлення
- метод
- методика
- може бути
- Модулі
- монітор
- контрольований
- більше
- більш ефективний
- найбільш
- рухатися
- рухатися вперед
- багато
- множинний
- взаємний
- природа
- обов'язково
- Необхідність
- необхідний
- потреби
- негативний
- Нові
- наступний
- немає
- вузол
- зараз
- нюанси
- об'єкти
- Спостерігає
- of
- пропонувати
- Пропозиції
- on
- один раз
- ONE
- тільки
- на
- операція
- операції
- оптимізація
- оптимізований
- or
- Інше
- інші
- інакше
- наші
- з
- над
- загальний
- Подолати
- параметр
- особливо
- Люди
- Виконувати
- може бути
- дозволи
- людина
- місце
- розміщення
- plato
- Інформація про дані Платона
- PlatoData
- безліч
- точка
- точок
- поп
- попсовий
- популярний
- володіє
- потенціал
- влада
- потужний
- Практичний
- практики
- наявність
- запобігати
- Попередження
- попередній
- раніше
- в першу чергу
- первинний
- принцип
- Принципи
- Проблема
- проблеми
- програма
- Програмування
- мови програмування
- забезпечувати
- цілей
- Штовхати
- Python
- досить
- підвищення
- діапазон
- RE
- досяг
- Реальний світ
- визнавати
- визнаючи
- Рекурсивний
- зменшити
- посилання
- вважати
- винаходити
- чудовий
- видалення
- представляти
- вимагати
- Вимога
- результат
- повертати
- повернення
- Умови повернення
- кільце
- міцний
- Котити
- s
- Безпека
- то ж
- сценарії
- подряпати
- розділ
- побачити
- мабуть
- SELF
- окремий
- Серія
- служити
- комплект
- тінь
- загальні
- лист
- Короткий
- Повинен
- сторона
- значення
- означати
- аналогічний
- простий
- простота
- просто
- з
- один
- Розмір
- М'який
- Рішення
- деякі
- Простір
- спеціальний
- спеціалізований
- конкретний
- стек
- Stackabuse
- Стеки
- стандартів
- старт
- стан
- Крок
- Стоп
- зберігання
- зберігати
- магазинів
- просто
- стратегії
- сила
- структура
- структур
- такі
- підтримка
- Підтриманий
- Опори
- Переконайтеся
- Навколо
- SVG
- SWIFT
- перемикач
- Приймати
- приймає
- ніж
- Що
- Команда
- їх
- Їх
- самі
- потім
- Там.
- отже
- Ці
- вони
- річ
- речі
- думати
- це
- ті
- три
- через
- час
- до
- занадто
- інструмент
- інструменти
- топ
- верхній
- традиційний
- перехід
- переводити
- правда
- намагатися
- намагається
- два
- підґрунтя
- розуміння
- Unexpected
- Використання
- використання
- використовуваний
- використання
- утиліта
- значення
- Цінності
- змінна
- величезний
- Ve
- різнобічний
- Універсальність
- життєво важливий
- хотіти
- шлях..
- способи
- we
- Web
- веб-браузер
- Що
- Що таке
- Колесо
- коли
- Чи
- який
- в той час як
- ВООЗ
- чому
- широкий
- Широкий діапазон
- волі
- з
- в
- без
- Work
- робочий
- світ
- турбуватися
- обернути
- років
- ще
- Ти
- вашу
- зефірнет