Создание стекового типа данных в Python

Первоначально опубликовано на dataqoil.com.

Введение

Стек — это одна из примитивных структур данных, которую мы всегда должны изучать перед погружением в структуру данных и анализ. Это пример ADT (абстрактного типа данных), в котором операции предопределены. Существуют и другие типы ADT, такие как очередь, список и т.д.

Операции

Для любого типа данных наиболее распространенные операции включают вставку данных, удаление данных и получение данных. Для простого стека существует 3 типа операций:

  • Push: Вставка данных на вершину стека.
  • Pop: удаление данных с вершины стека.
  • Top: извлечение данных из верхнего элемента.

Стек работает по принципу LIFO (Last in First Out). Это означает, что в любой момент времени указатель будет находиться на вершине стека, и нам разрешено работать только с данными, на которые указывает указатель. Если в стеке будет использоваться массив, то его размер будет фиксированным, но если мы будем использовать список, то размер будет переменным.

Операция Push

Предположим, что для стека используется массив размером 6 с данными [4 5 6 8 5 2]. Изначально стек будет пуст, а указатель будет указывать на вершину данных стека, которая находится внизу. Теперь на первом шаге, чтобы протолкнуть данные, мы протолкнем 4 в 0-ю позицию. Затем указатель переместится на один шаг вверх. На следующем шаге на 1-ю позицию вставляются следующие данные. И наконец, наш стек будет заполнен.

Давайте напишем это на python.

class Stack:
    def __init__(self, size):
        self.size = size
        self.storage = ["~"]*size
        self.pointer = 0
        print(f"New Stack: {self.storage}")
        print(f"Pointer at {self.pointer}.n")

    def push(self, x):
        self.storage[self.pointer] = x
        print(f"New Stack: {self.storage}")
        print(f"Pointer at {self.pointer+1}.n")

        self.pointer+=1


Вход в полноэкранный режим Выход из полноэкранного режима
data = [4, 5, 6, 8, 5, 2]
stack = Stack(size=6)

for x in data:
    stack.push(x)
Войти в полноэкранный режим Выход из полноэкранного режима
New Stack: ['~', '~', '~', '~', '~', '~']
Pointer at 0.

New Stack: [4, '~', '~', '~', '~', '~']
Pointer at 1.

New Stack: [4, 5, '~', '~', '~', '~']
Pointer at 2.

New Stack: [4, 5, 6, '~', '~', '~']
Pointer at 3.

New Stack: [4, 5, 6, 8, '~', '~']
Pointer at 4.

New Stack: [4, 5, 6, 8, 5, '~']
Pointer at 5.

New Stack: [4, 5, 6, 8, 5, 2]
Pointer at 6.
Войти в полноэкранный режим Выход из полноэкранного режима

Теперь мы поместили данные в наш стек, но что если мы поместим больше данных, чем размер стека? В этом случае произойдет переполнение, а в примере выше мы использовали список в качестве хранилища, и он также выдаст ошибку, если мы попытаемся что-то вставить.

stack.push(0)
Вход в полноэкранный режим Выход из полноэкранного режима
---------------------------------------------------------------------------

IndexError                                Traceback (most recent call last)

<ipython-input-23-c549502547a3> in <module>
----> 1 stack.push(0)


<ipython-input-21-dfbe390820f6> in push(self, x)
      8 
      9     def push(self, x):
---> 10         self.storage[self.pointer] = x
     11         print(f"New Stack: {self.storage}")
     12         print(f"Pointer at {self.pointer+1}.n")


IndexError: list assignment index out of range
Войти в полноэкранный режим Выйти из полноэкранного режима

Что вполне ожидаемо, но в нашем случае ошибка должна выглядеть немного иначе.

class Stack:
    def __init__(self, size):
        self.size = size
        self.storage = ["~"]*size
        self.pointer = 0
        print(f"New Stack: {self.storage}")
        print(f"Pointer at {self.pointer}.n")

    def push(self, x):
        try:
            self.storage[self.pointer] = x
            print(f"New Stack: {self.storage}")
            print(f"Pointer at {self.pointer+1}.n")

            self.pointer+=1
        except IndexError as e:
            print(f"Overflow Occured at pointer: {self.pointer}")

Войти в полноэкранный режим Выход из полноэкранного режима
data = [4, 5, 6, 8, 5, 2, 0]
stack = Stack(size=6)

for x in data:
    stack.push(x)
Войти в полноэкранный режим Выход из полноэкранного режима
New Stack: ['~', '~', '~', '~', '~', '~']
Pointer at 0.

New Stack: [4, '~', '~', '~', '~', '~']
Pointer at 1.

New Stack: [4, 5, '~', '~', '~', '~']
Pointer at 2.

New Stack: [4, 5, 6, '~', '~', '~']
Pointer at 3.

New Stack: [4, 5, 6, 8, '~', '~']
Pointer at 4.

New Stack: [4, 5, 6, 8, 5, '~']
Pointer at 5.

New Stack: [4, 5, 6, 8, 5, 2]
Pointer at 6.

Overflow Occured at pointer: 6
Войти в полноэкранный режим Выход из полноэкранного режима

Операция выгрузки

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

class Stack:
    def __init__(self, size):
        self.size = size
        self.storage = ["~"]*size
        self.pointer = 0
        print(f"New Stack: {self.storage}")
        print(f"Pointer at {self.pointer}.n")

    def push(self, x):
        try:
            self.storage[self.pointer] = x
            print(f"New Stack: {self.storage}")
            print(f"Pointer at {self.pointer+1}.n")

            self.pointer+=1
        except IndexError as e:
            print(f"Overflow Occured at pointer: {self.pointer} n")

    def pop(self):
        self.storage = self.storage[:-1]

        print(f"New Stack: {self.storage}")
        print(f"Pointer at {self.pointer-1}.n")

        self.pointer-=1
Войти в полноэкранный режим Выход из полноэкранного режима
data = [4, 5, 6, 8, 5, 2, 0]
stack = Stack(size=6)

for x in data:
    stack.push(x)
stack.pop()
Войти в полноэкранный режим Выход из полноэкранного режима
New Stack: ['~', '~', '~', '~', '~', '~']
Pointer at 0.

New Stack: [4, '~', '~', '~', '~', '~']
Pointer at 1.

New Stack: [4, 5, '~', '~', '~', '~']
Pointer at 2.

New Stack: [4, 5, 6, '~', '~', '~']
Pointer at 3.

New Stack: [4, 5, 6, 8, '~', '~']
Pointer at 4.

New Stack: [4, 5, 6, 8, 5, '~']
Pointer at 5.

New Stack: [4, 5, 6, 8, 5, 2]
Pointer at 6.

Overflow Occured at pointer: 6 

New Stack: [4, 5, 6, 8, 5]
Pointer at 5.
Войти в полноэкранный режим Выход из полноэкранного режима

Теперь, когда мы выполнили операцию pop, что произойдет, если наш стек пуст, а мы попытались удалить данные? Это случай переполнения стека. Давайте напишем и это.

for i in range(len(data)):
    stack.pop()
Вход в полноэкранный режим Выход из полноэкранного режима
New Stack: [4, 5, 6, 8]
Pointer at 4.

New Stack: [4, 5, 6]
Pointer at 3.

New Stack: [4, 5]
Pointer at 2.

New Stack: [4]
Pointer at 1.

New Stack: []
Pointer at 0.

New Stack: []
Pointer at -1.

New Stack: []
Pointer at -2.
Вход в полноэкранный режим Выход из полноэкранного режима

В приведенном выше коде ошибка не появляется, когда указатель становится -ve. Предположим, что если указатель уже равен 0 и мы пытаемся его удалить, то должна возникнуть ошибка.

class Stack:
    def __init__(self, size):
        self.size = size
        self.storage = ["~"]*size
        self.pointer = 0
        print(f"New Stack: {self.storage}")
        print(f"Pointer at {self.pointer}.n")

    def push(self, x):
        try:
            self.storage[self.pointer] = x
            print(f"New Stack: {self.storage}")
            print(f"Pointer at {self.pointer+1}.n")

            self.pointer+=1
        except IndexError as e:
            print(f"Overflow Occured at pointer: {self.pointer} n")

    def pop(self):
        if self.pointer<1:
            print("Stack Underflow occured.")
        else:
            self.storage = self.storage[:-1]
            print(f"New Stack: {self.storage}")
            print(f"Pointer at {self.pointer-1}.n")

            self.pointer-=1

Вход в полноэкранный режим Выход из полноэкранного режима
data = [4, 5, 6, 8, 5, 2, 0]
stack = Stack(size=6)

for x in data:
    stack.push(x)
stack.pop()

for i in range(len(data)):
    stack.pop()
Войти в полноэкранный режим Выход из полноэкранного режима
New Stack: ['~', '~', '~', '~', '~', '~']
Pointer at 0.

New Stack: [4, '~', '~', '~', '~', '~']
Pointer at 1.

New Stack: [4, 5, '~', '~', '~', '~']
Pointer at 2.

New Stack: [4, 5, 6, '~', '~', '~']
Pointer at 3.

New Stack: [4, 5, 6, 8, '~', '~']
Pointer at 4.

New Stack: [4, 5, 6, 8, 5, '~']
Pointer at 5.

New Stack: [4, 5, 6, 8, 5, 2]
Pointer at 6.

Overflow Occured at pointer: 6 

New Stack: [4, 5, 6, 8, 5]
Pointer at 5.

New Stack: [4, 5, 6, 8]
Pointer at 4.

New Stack: [4, 5, 6]
Pointer at 3.

New Stack: [4, 5]
Pointer at 2.

New Stack: [4]
Pointer at 1.

New Stack: []
Pointer at 0.

Stack Underflow occured.
Stack Underflow occured.
Войти в полноэкранный режим Выход из полноэкранного режима

Теперь немного подправьте его, чтобы сделать более читабельным.

class Stack:
    def __init__(self, size):
        self.size = size
        self.storage = ["~"]*size
        self.pointer = 0
        print(f"New Stack: {self.storage}")
        print(f"Pointer at {self.pointer}.n")

    def push(self, x):
        print("=" * 20+" Push Operation "+"=" * 20)
        try:
            self.storage[self.pointer] = x
            print(f"New Stack: {self.storage}")
            print(f"Pointer at {self.pointer+1}.")

            self.pointer+=1
        except IndexError as e:
            print(f"Overflow Occured at pointer: {self.pointer}")
        print("="*55 + "n")

    def pop(self):
        print("=" * 20+" Pop Operation "+"=" * 20)
        if self.pointer<1:
            print("Stack Underflow occured.")
        else:
            self.storage = self.storage[:-1]
            print(f"New Stack: {self.storage}")
            print(f"Pointer at {self.pointer-1}.")

            self.pointer-=1
        print("="*55 + "n")

Вход в полноэкранный режим Выход из полноэкранного режима
data = [4, 5, 6, 8, 5, 2, 0]
stack = Stack(size=6)

for x in data:
    stack.push(x)
stack.pop()

for i in range(len(data)):
    stack.pop()
Войти в полноэкранный режим Выход из полноэкранного режима
New Stack: ['~', '~', '~', '~', '~', '~']
Pointer at 0.

==================== Push Operation ====================
New Stack: [4, '~', '~', '~', '~', '~']
Pointer at 1.
=======================================================

==================== Push Operation ====================
New Stack: [4, 5, '~', '~', '~', '~']
Pointer at 2.
=======================================================

==================== Push Operation ====================
New Stack: [4, 5, 6, '~', '~', '~']
Pointer at 3.
=======================================================

==================== Push Operation ====================
New Stack: [4, 5, 6, 8, '~', '~']
Pointer at 4.
=======================================================

==================== Push Operation ====================
New Stack: [4, 5, 6, 8, 5, '~']
Pointer at 5.
=======================================================

==================== Push Operation ====================
New Stack: [4, 5, 6, 8, 5, 2]
Pointer at 6.
=======================================================

==================== Push Operation ====================
Overflow Occured at pointer: 6
=======================================================

==================== Pop Operation ====================
New Stack: [4, 5, 6, 8, 5]
Pointer at 5.
=======================================================

==================== Pop Operation ====================
New Stack: [4, 5, 6, 8]
Pointer at 4.
=======================================================

==================== Pop Operation ====================
New Stack: [4, 5, 6]
Pointer at 3.
=======================================================

==================== Pop Operation ====================
New Stack: [4, 5]
Pointer at 2.
=======================================================

==================== Pop Operation ====================
New Stack: [4]
Pointer at 1.
=======================================================

==================== Pop Operation ====================
New Stack: []
Pointer at 0.
=======================================================

==================== Pop Operation ====================
Stack Underflow occured.
=======================================================

==================== Pop Operation ====================
Stack Underflow occured.
=======================================================
Войти в полноэкранный режим Выход из полноэкранного режима

Верхняя операция

Это простая операция. Она выдает значение, которое находится ниже позиции, на которую в данный момент указывает указатель.

class Stack:
    def __init__(self, size):
        self.size = size
        self.storage = ["~"]*size
        self.pointer = 0
        print(f"New Stack: {self.storage}")
        print(f"Pointer at {self.pointer}.n")

    def push(self, x):
        print("=" * 20+" Push Operation "+"=" * 20)
        try:
            self.storage[self.pointer] = x
            print(f"New Stack: {self.storage}")
            print(f"Pointer at {self.pointer+1}.")

            self.pointer+=1
        except IndexError as e:
            print(f"Overflow Occured at pointer: {self.pointer}")
        print("="*55 + "n")

    def pop(self):
        print("=" * 20+" Pop Operation "+"=" * 20)
        if self.pointer<1:
            print("Stack Underflow occured.")
        else:
            self.storage = self.storage[:-1]
            print(f"New Stack: {self.storage}")
            print(f"Pointer at {self.pointer-1}.")

            self.pointer-=1
        print("="*55 + "n")

    def top(self):
        print("=" * 20+" Top Operation "+"=" * 20)
        try:
            print(f"Pointer at {self.pointer}.")
            print(f"Return: {self.storage[self.pointer-1]}")
        except:
            print("Nothing on the top. Stack is empty.")
        print("="*55 + "n")

Вход в полноэкранный режим Выход из полноэкранного режима
data = [4, 5, 6, 8, 5, 2, 0]
stack = Stack(size=6)

for x in data:
    stack.push(x)
    stack.top()
stack.pop()

for i in range(len(data)):
    stack.pop()
    stack.top()
Войти в полноэкранный режим Выход из полноэкранного режима
New Stack: ['~', '~', '~', '~', '~', '~']
Pointer at 0.

==================== Push Operation ====================
New Stack: [4, '~', '~', '~', '~', '~']

Pointer at 1.

==================== Top Operation ====================
Pointer at 1.

Return: 4

==================== Push Operation ====================
New Stack: [4, 5, '~', '~', '~', '~']

Pointer at 2.

==================== Top Operation ====================
Pointer at 2.

Return: 5

==================== Push Operation ====================
New Stack: [4, 5, 6, '~', '~', '~']

Pointer at 3.

==================== Top Operation ====================
Pointer at 3.

Return: 6

==================== Push Operation ====================
New Stack: [4, 5, 6, 8, '~', '~']

Pointer at 4.

==================== Top Operation ====================
Pointer at 4.

Return: 8

==================== Push Operation ====================
New Stack: [4, 5, 6, 8, 5, '~']

Pointer at 5.

==================== Top Operation ====================
Pointer at 5.

Return: 5

==================== Push Operation ====================
New Stack: [4, 5, 6, 8, 5, 2]

Pointer at 6.

==================== Top Operation ====================
Pointer at 6.

Return: 2

==================== Push Operation ====================

Overflow Occured at pointer: 6

==================== Top Operation ====================
Pointer at 6.

Return: 2

==================== Pop Operation ====================
New Stack: [4, 5, 6, 8, 5]

Pointer at 5.

==================== Pop Operation ====================
New Stack: [4, 5, 6, 8]

Pointer at 4.

==================== Top Operation ====================
Pointer at 4.

Return: 8

==================== Pop Operation ====================
New Stack: [4, 5, 6]

Pointer at 3.

==================== Top Operation ====================
Pointer at 3.

Return: 6

==================== Pop Operation ====================
New Stack: [4, 5]

Pointer at 2.

==================== Top Operation ====================
Pointer at 2.

Return: 5

==================== Pop Operation ====================
New Stack: [4]

Pointer at 1.

==================== Top Operation ====================
Pointer at 1.

Return: 4

==================== Pop Operation ====================
New Stack: []

Pointer at 0.

==================== Top Operation ====================
Pointer at 0.

Nothing on the top. Stack is empty.

==================== Pop Operation ====================

Stack Underflow occured.

==================== Top Operation ====================
Pointer at 0.

Nothing on the top. Stack is empty.

==================== Pop Operation ====================

Stack Underflow occured.

==================== Top Operation ====================
Pointer at 0.

Nothing on the top. Stack is empty.

Войти в полноэкранный режим Выход из полноэкранного режима

Заключение

Спасибо, что прочитали этот блог и дошли до конца. В следующем блоге я поделюсь аналогичным подходом для очереди, и это тоже будет интересно попробовать.

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *