Ранее я объяснил, как работает связанный список и его общие методы. В этом выпуске я расскажу о стеке. Я собираюсь использовать Python в примерах, но он также должен быть легким для понимания людьми с другой языковой базой. Давай займемся этим.

Что такое стек?

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

Представьте, что у вас есть стопка тарелок с изображениями животных, и вы хотите получить тарелку из середины стопки, которая представляет собой жирафа. Как бы вы ее получили? Сначала нужно вытащить тарелку на свинью, а затем на медведя. Мы не можем просто получить доступ к случайной позиции стека, например к массиву. Я знаю! Это кажется очень неэффективным способом сделать это.

Тогда зачем использовать стек?

Если вам нужно хранить данные в структуре данных, ее размер должен часто меняться, лучше использовать стек над массивом, потому что массив должен будет создать новый больший размер пустого массива, чтобы соответствовать новым данным, тогда он будет копировать из старого массива в новый пустой массив, который занимает линейное время O (n), тогда как Стек занимает только постоянное время O (1). Поэтому было бы лучше использовать стек, если данные приходят и уходят очень часто.

В отличие от массивов, размер стека динамически изменяется в зависимости от того, сколько элементов содержится в нем, поэтому нам не нужно указывать размер стека и почему нам нужно использовать стек.

Пример из реального мира

  • функция отмены (например, ctrl + z)
  • кнопка "Назад" в веб-браузере, чтобы увидеть свою историю
  • отслеживание пар скобок и скобок в редакторах кода

Общие методы в стеке

В Stack есть четыре распространенных метода: Push, Pop, Peek, isEmpty.

Push (элемент): Добавление элемента в верхнюю часть стека.

pop (): Удаление элемента из верхней части стека.

Peek (): Распечатать верхний элемент.

isEmpty (): Возвращает логическое значение, чтобы проверить, пуст ли стек.

Реализация стека

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

Множество

Реализация с массивом довольно проста, просто создайте массив с конструктором. Однако на других языках, таких как Java, вам придется инициализировать размер стека заранее с помощью большое число, например 1000, поэтому массив не будет создавать новый массив при добавлении нового элемента.

Инициализация стека с помощью массива (Java)

class Stack {
  static final int MAX = 1000;
  int arr[] = new int[MAX]; // create a 1000 size of array
}

Стек массивов в Python

class Stack:
    def __init__(self):
        self.items = []
    def is_empty(self):
        return len(self.items) == 0   
    def push(self, element):
        self.items.append(element)
    def pop(self):
        return self.items.pop()
    def peek(self):
        if not is_empty():
           return self.items[len(self.items) - 1]

Разбивка

def __init__ - это конструктор, который инициализирует экземпляр, при инициализации он создает пустой стек.

# constructor
def __init__(self):
        self.items = []
# initialise a empty stack
new_stack = Stack()

def is_empty () вернет логические данные. Верно, если длина стека равна 0, Ложь - длина не 0. Временная сложность: O (1)

def push (element) - это функция void, которая добавляет элемент на вершину стека O (1). Сложность времени: O (1)

def pop () удаляет элемент из вершины стека и возвращает удаленный элемент. Сложность времени: O (1)

def peek () вернет верхний элемент стека, который является последним элементом массива. Поскольку индекс начинается с 0, индекс последнего элемента будет размер массива-1, если стек не пуст. Сложность времени: O (1)

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

# create an empty stack
stack = Stack()
# stack it up with elements
stack.push("rabbit") # first item on the bottom
stack.push("tiger")
stack.push("giraffe")
stack.push("bear")
stack.push("pig") # last item on the top

В результате этого кода ваш стек будет выглядеть так:

Связанный список

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

Class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class Stack:
    def __init__(self):
        self.top = None
    def is_empty(self):
        return self.top is None
    def peek(self):
        return self.top.data
 
    def push(self, data):
        node = Node(data)
        node.next = self.top
        self.top = node
    def pop(self):
        data = self.top.data
        self.top = self.top.next
        return data

Как и на этом изображении выше, когда верхний элемент в стопке выталкивается, в данном случае это «свинья», следующий элемент будет верхним. Точно так же, когда новый элемент помещается в верхнюю часть, новый элемент будет верхним, то есть в данном случае «панда».

В заключение, стек представляет собой полезную структуру данных, поскольку временная сложность общих методов составляет O (1), несмотря на неудобство, связанное с невозможностью произвольного доступа. и это может быть реализовано с помощью массива и связанного списка. Спасибо за чтение, увидимся до следующего раза!

Понравилась эта статья? Если да, то получите больше похожего контента, подписавшись на наш канал YouTube в Decoded!