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

Автор

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

Давайте розглянемо стек та його втілення в Python.

Що таке стек?

Стек можна уявити як стопку книг або стільців у реальному світі. Він працює за принципом “останній прийшов – перший пішов” (LIFO). Це одна з найпростіших структур даних. Розглянемо приклад з життя.

Припустимо, маємо стопку книг:

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

Операції зі стеком

Основні операції зі стеком:

1. push(дані)

Додає дані до стеку.

2. pop()

Видаляє верхній елемент зі стеку.

Нижче показано ілюстрації операцій додавання та видалення.

Напишемо кілька додаткових функцій для отримання інформації про стек.

Ось вони:

peek()

Повертає верхній елемент стеку, не видаляючи його.

is_empty()

Повертає true, якщо стек порожній, і false – якщо ні.

Досить теорії про стеки. Перейдемо до їх реалізації.

Сподіваюся, Python вже встановлено на вашому комп’ютері. Якщо ні, можна скористатися онлайн-компілятором.

Реалізація стеку

Стек досить легко реалізувати, порівняно з іншими структурами даних. Є кілька способів зробити це в Python.

Розглянемо їх по черзі.

#1. Список

Створимо стек, використовуючи список у класі. Розглянемо цей процес крок за кроком.

Крок 1: Створюємо клас Stack.

class Stack:
    pass

Крок 2: Дані будемо зберігати у списку. Додаємо пустий список до класу Stack.

class Stack:
    def __init__(self):
        self.elements = []

Крок 3: Потрібен метод для додавання елементів. Створюємо метод push, що приймає дані і додає їх до списку.

class Stack:
    def __init__(self):
        self.elements = []

    def push(self, data):
        self.elements.append(data)
        return data

Крок 4: Аналогічно, створюємо метод pop, що видаляє верхній елемент. Можемо використовувати метод pop списку.

class Stack:
    ## ...
    def pop(self):
        return self.elements.pop()

Основні операції стеку готові. Додамо ще декілька для отримання додаткової інформації.

Крок 5: Верхній елемент можна отримати за допомогою від’ємного індексу. Елемент коду [-1] поверне останній елемент списку, що і буде верхнім елементом стеку.

class Stack:
    ## ...

    def peek(self):
        return self.elements[-1]

Крок 6: Якщо довжина списку дорівнює 0, стек порожній. Напишемо метод, який це перевіряє.

class Stack:
    ## ...
    def is_empty(self):
        return len(self.elements) == 0

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

Але як використовувати цей стек? Створимо об’єкт класу Stack. Це досить просто.

class Stack:
    ## ...

if __name__ == '__main__':
    stack = Stack()

Об’єкт стеку створено. Перевіримо, як він працює.

  • Перевіряємо, чи порожній стек, за допомогою методу is_empty. Має повернути True.
  • Додаємо числа 1, 2, 3, 4, 5 до стеку за допомогою методу push.
  • Метод is_empty повинен повернути False. Перевіряємо.
  • Виводимо верхній елемент за допомогою методу peek.
  • Видаляємо елемент зі стеку за допомогою методу pop.
  • Перевіряємо верхній елемент методом peek. Має повернутися 4.
  • Видаляємо всі елементи зі стеку.
  • Метод is_empty повинен повернути True. Перевіряємо.

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

Вже написали? Якщо ні, не хвилюйтесь, перегляньте код нижче:

class Stack:
    def __init__(self):
        self.elements = []

    def push(self, data):
        self.elements.append(data)
        return data

    def pop(self):
        return self.elements.pop()

    def peek(self):
        return self.elements[-1]

    def is_empty(self):
        return len(self.elements) == 0

if __name__ == '__main__':
    stack = Stack()

    ## checking is_empty method -> true
    print(stack.is_empty())

    ## pushing the elements
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    stack.push(5)

    ## again checking is_empty method -> false
    print(stack.is_empty())

    ## printing the topmost element of the stack -> 5
    print(stack.peek())

    ## popping the topmost element -> 5
    stack.pop()

    ## checking the topmost element using peek method -> 4
    print(stack.peek())

    ## popping all the elements
    stack.pop()
    stack.pop()
    stack.pop()
    stack.pop()

    ## checking the is_empty method for the last time -> true
    print(stack.is_empty())

Ура! Ми реалізували стек з нуля, використовуючи тип даних списку. Якщо ви запустите цей код, отримаєте наступний результат:

True
False
5
4
True

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

Можете переглянути інші статті, що стосуються списків.

Поглянемо на вбудований deque з модуля collections, який також може працювати як стек.

#2. deque з collections

Deque – це двостороння черга. Можна додавати та видаляти елементи з обох кінців, тому його можна використовувати як стек. Він може працювати за принципом стека LIFO.

Реалізовано deque на базі двозв’язаного списку. Додавання та видалення елементів виконується з однаковою швидкістю. Доступ до середнього елемента займає O(n). Для стека це не важливо, бо ми не звертаємося до середніх елементів.

Перед тим, як реалізувати стек за допомогою черги, розглянемо методи, які будемо використовувати:

  • append(data) – для додавання даних у стек.
  • pop() – для видалення верхнього елемента стека.

Для peek та is_empty методів немає аналогів. Для peek можна вивести весь стек, а для перевірки на порожність використати метод len.

Реалізуємо стек за допомогою deque з модуля collections:

from collections import deque

## creating deque object
stack = deque()

## checking whether stack is empty or not -> true
print(len(stack) == 0)

## pushing the elements
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)

## again checking whether stack is empty or not -> false
print(len(stack) == 0)

## printing the stack
print(stack)

## popping the topmost element -> 5
stack.pop()

## printing the stack
print(stack)

## popping all the elements
stack.pop()
stack.pop()
stack.pop()
stack.pop()

## checking the whether stack is empty or not for the last time -> true
print(len(stack) == 0)

Ось і все. Ми реалізували стек за допомогою deque. Запустивши код, отримаємо наступний результат:

True
False
deque([1, 2, 3, 4, 5])
deque([1, 2, 3, 4])
True

Ми розглянули два способи реалізації стека. Чи є інші? Так! Розглянемо останній спосіб реалізації стека в цьому посібнику.

#3. LifoQueue

З назви LifoQueue можна зрозуміти, що він працює за принципом LIFO. Отже, його можна використовувати як стек. Це з вбудованої черги модуля. LifoQueue надає кілька корисних методів, які використовуються при реалізації стека. Розглянемо їх:

  • put(data) – додає дані до черги.
  • get() – видаляє верхній елемент із черги.
  • empty() – перевіряє, чи порожня черга.
  • qsize() – повертає довжину черги.

Реалізуємо стек за допомогою LifoQueue з модуля queue.

from queue import LifoQueue

## creating LifoQueue object
stack = LifoQueue()

## checking whether stack is empty or not -> true
print(stack.empty())

## pushing the elements
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)

## again checking whether stack is empty or not -> false
print(stack.empty())

## popping all the elements
print(stack.get())
print(stack.get())
print(stack.get())

## checking the stack size
print("Size", stack.qsize())

print(stack.get())
print(stack.get())

## checking the whether stack is empty or not for the last time -> true
print(stack.empty())

Запустивши код, отримаємо наступний результат:

True
False
5
4
3
Size 2
2
1
True

Застосування стека

Тепер, коли ви достатньо знаєте про стеки, можна застосувати їх для розв’язання задач програмування. Розглянемо одну з таких задач.

Маємо вираз. Напишіть програму, яка перевіряє, чи правильно збалансовані дужки, квадратні дужки та фігурні дужки у виразі.

Розглянемо кілька прикладів.

Вхід: “[{}]([])”

Вихід: збалансовано

Вхід: “{[}]([])”

Вихід: не збалансовано

Стек можна використати для розв’язання цієї проблеми. Розглянемо кроки розв’язку:

  • Створити стек для зберігання символів.
  • Якщо довжина виразу непарна, вираз незбалансований.
  • Перебираємо символи виразу:
    • Якщо поточний символ є відкриваючою дужкою ( або { або [, додаємо його до стеку.
    • Інакше, якщо поточний символ є закриваючою дужкою ) або } або ], витягуємо символ зі стеку.
    • Якщо витягнутий символ відповідає відкриваючій дужці, продовжуємо. Інакше дужки не збалансовані.
  • Після перебору, якщо стек порожній, то рівняння збалансоване. Інакше – ні.

Для перевірки відповідності дужок, використаємо тип даних set.

## stack
class Stack:
    def __init__(self):
        self.elements = []

    def push(self, data):
        self.elements.append(data)
        return data

    def pop(self):
        return self.elements.pop()

    def peek(self):
        return self.elements[-1]

    def is_empty(self):
        return len(self.elements) == 0

def balance_check(expression):
    ## checking the length of the expression
    if len(expression) % 2 != 0:
        ## not balanced if the length is odd
        return False

    ## for checking
    opening_brackets = set('([{')
    pairs = set([ ('(',')'), ('[',']'), ('{','}') ])

    ## stack initialization
    stack = Stack()

    ## iterating through the given expression
    for bracket in expression:

        ## checking whether the current bracket is opened or not
        if bracket in opening_brackets:
            ## adding to the stack
            stack.push(bracket)
        else:
            ## popping out the last bracket from the stack
            popped_bracket = stack.pop()

            ## checking whether popped and current bracket pair
            if (popped_bracket, bracket) not in pairs:
                return False

    return stack.is_empty()

if __name__ == '__main__':
    if balance_check('[{}]([])'):
        print("Balanced")
    else:
        print("Not Balanced")

    if balance_check('{[}]([])'):
        print("Balanced")
    else:
        print("Not Balanced")

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

Висновок

От і все! Сподіваюся, вам сподобався цей посібник так само, як і мені. На цьому все.

Вдалого програмування 🙂 👨‍💻