А стек це лінійна структура даних, яка зберігає елементи в a Останній прийшов/перший вийшов (LIFO) або способом «перший прийшов/останній вийшов» (FILO). У стеку новий елемент додається на одному кінці, а елемент видаляється лише з цього кінця. Операції вставки та видалення часто називають push і pop.

Функції, пов’язані зі стеком:

• порожній() – Повертає, чи стек порожній – Часова складність: O(1)
• розмір() – Повертає розмір стеку – Часова складність: O(1)
• top() / peek() – Повертає посилання на найвищий елемент стеку – Часова складність: O(1)
• push(a) – Вставляє елемент «a» у верхній частині стека – Часова складність: O(1)
• поп() – Видаляє найвищий елемент стеку – Часова складність: O(1)

Реалізація:

Існують різні способи реалізації стека в Python. У цій статті розглядається реалізація стека з використанням структур даних і модулів із бібліотеки Python.
Стек у Python можна реалізувати такими способами:

• список
• Collections.deque
• queue.LifoQueue

Реалізація за допомогою списку:

Вбудований список структур даних Python можна використовувати як стек. Замість push(), append() використовується для додавання елементів у верхню частину стека, тоді як pop() видаляє елемент у порядку LIFO.
На жаль, список має кілька недоліків. Найбільша проблема полягає в тому, що він може зіткнутися зі швидкістю, коли він росте. Елементи у списку зберігаються в пам’яті поруч один з одним. Якщо стек стає більшим, ніж блок пам’яті, який наразі його містить, Python потребує певного розподілу пам’яті. Це може призвести до того, що деякі виклики append() триватимуть набагато довше, ніж інші.

# Python program to # demonstrate stack implementation # using list stack = [] # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack ['a', 'b', 'c'] Elements popped from stack: c b a Stack after elements are popped: []>

Реалізація за допомогою collections.deque:

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

Використовуються ті самі методи на deque, що й у списку, append() і pop().

# Python program to # demonstrate stack implementation # using collections.deque from collections import deque stack = deque() # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack:') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack: deque(['a', 'b', 'c']) Elements popped from stack: c b a Stack after elements are popped: deque([])>

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

Модуль Queue також має чергу LIFO, яка в основному є стеком. Дані вставляються в чергу за допомогою функції put(), а get() вилучає дані з черги.

У цьому модулі доступні різні функції:

• максимальний розмір – Кількість елементів, дозволених у черзі.
• порожній() – Повертає True, якщо черга порожня, False в іншому випадку.
• повний() – Повертає True, якщо є максимальний розмір елементів у черзі. Якщо чергу було ініціалізовано з maxsize=0 (за замовчуванням), то full() ніколи не повертає True.
• отримати() – Видалення та повернення елемента з черги. Якщо черга порожня, зачекайте, поки елемент стане доступним.
• get_nowait() – Повернути елемент, якщо він одразу доступний, інакше підняти QueueEmpty.
• поставити (пункт) – Покладіть товар у чергу. Якщо черга заповнена, зачекайте, поки з’явиться вільне місце, перш ніж додавати елемент.
• put_nowait(елемент) – Помістіть елемент у чергу без блокування. Якщо вільного місця немає, підніміть QueueFull.
• qsize() – Повернути кількість елементів у черзі.

# Python program to # demonstrate stack implementation # using queue module from queue import LifoQueue # Initializing a stack stack = LifoQueue(maxsize=3) # qsize() show the number of elements # in the stack print(stack.qsize()) # put() function to push # element in the stack stack.put('a') stack.put('b') stack.put('c') print('Full: ', stack.full()) print('Size: ', stack.qsize()) # get() function to pop # element from stack in # LIFO order print('
Elements popped from the stack') print(stack.get()) print(stack.get()) print(stack.get()) print('
Empty: ', stack.empty())>

0 Full: True Size: 3 Elements popped from the stack c b a Empty: True>

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

Зв’язаний список має два методи addHead(item) і removeHead(), які виконуються в постійному часі. Ці два методи підходять для реалізації стека.

• getSize() – Отримати кількість елементів у стосі.
• пусто() – Повертає True, якщо стек порожній, False в іншому випадку.
• peek() – Поверніть верхній елемент у стосі. Якщо стек порожній, викликайте виняток.
• push(значення) – Вставити значення в голову стека.
• поп() – Видалити та повернути значення в голові стека. Якщо стек порожній, викликайте виняток.

Нижче наведено реалізацію вищезазначеного підходу:

# Python program to demonstrate # stack implementation using a linked list. # node class class Node: def __init__(self, value): self.value = value self.next = None class Stack: # Initializing a stack. # Use a dummy node, which is # easier for handling edge cases. def __init__(self): self.head = Node('head') self.size = 0 # String representation of the stack def __str__(self): cur = self.head.next out = '' while cur: out += str(cur.value) + '->' cur = cur.next return out[:-2] # Отримати поточний розмір стеку def getSize(self): return self.size # Перевірити, чи стек порожній def isEmpty(self): return self.size = = 0 # Отримати верхній елемент стека def peek(self): # Санітарна перевірка, щоб побачити, чи # ми переглядаємо порожній стек. if self.isEmpty(): return None return self.head.next.value # Надішліть значення в стек. def push(self, value): node = Node(value) node.next = self.head.next # Зробити так, щоб новий вузол вказував на поточну голову self.head.next = node #!!! # Оновити заголовок, щоб він був новим вузлом self.size += 1 # Видалити значення зі стеку та повернутися. def pop(self): if self.isEmpty(): raise Exception('Вискакування з порожнього стека') remove = self.head.next self.head.next = remove.next #!!! змінено self.size -= 1 return remove.value # Код драйвера if __name__ == '__main__': stack = Stack() for i in range(1, 11): stack.push(i) print(f' Стек: {stack}') для _ в діапазоні (1, 6): top_value = stack.pop() print(f'Pop: {top_value}') # ім'я змінної змінено print(f'Stack: { стек}')>

Вихід

Stack: 10->9->8->7->6->5->4->3->2->1 Поп: 10 Поп: 9 Поп: 8 Поп: 7 Поп: 6 Стек: 5->4->3->2->1>>

Переваги Stack:

• Стеки — це прості структури даних із чітко визначеним набором операцій, що робить їх легкими для розуміння та використання.
• Стеки ефективні для додавання та видалення елементів, оскільки ці операції мають часову складність O(1).
• Щоб змінити порядок елементів, ми використовуємо структуру даних стека.
• Стеки можна використовувати для реалізації функцій скасування/повторення в програмах.

Недоліки Stack:

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