Структуры данных - это набор значений данных, отношений между ними, а также функций или операций, которые могут быть применены к данным. Сейчас доступно множество структур данных. Но сегодня мы сосредоточимся на структурах данных стека. Я буду обсуждать следующие темы:
- Почему структуры данных?
- Типы структур данных
- Что такое структура данных стека?
- Создание структуры данных стека
- Вставить элементы в стек
- Поп-элементы из стека
- Применение структуры данных стека
Почему структуры данных?
Чтобы ответить на этот вопрос, вам придется подумать на широком уровне. Подумайте, как карты Google показывают лучший маршрут всего за доли секунды, как они возвращают вам результат поиска за микросекунды. Он не работает только со 100 веб-сайтами, он работает с более чем миллиардом сайтов и по-прежнему так быстро показывает результаты.
Что ж, хотя используемый алгоритм играет решающую роль, используемая структура данных или контейнер является основой этого алгоритма. В любом приложении организация и хранение данных таким образом или в структуре, которая лучше всего подходит для их использования, является ключом к эффективному доступу и обработке данных.
Типы структур данных
Есть несколько стандартных структур данных, которые можно использовать для эффективной работы с данными. Мы даже можем настроить их или создать совершенно новые, подходящие для нашего приложения.
Что такое структура данных стека?
Рассмотрим несколько примеров из реальной жизни:
- Отгрузка в грузе
- Тарелки на подносе
- Стопка монет
- Стопка ящиков
- Маневрирование поездов на железнодорожной станции
Все эти примеры следуют Последний вошел - первым ушел стратегия. Рассмотрим тарелки на подносе. Когда вы хотите выбрать тарелку, вы вынуждены брать тарелку сверху, тогда как когда тарелки хранились на подносе, они должны быть в обратном порядке. Приведенные выше примеры, следующие за Последний пришел - первый ушел (LIFO) принцип известен как Стек .
Помимо дополнительных операций, я могу сказать, что основными возможными операциями в стеке являются:
- Вставьте или вставьте элемент в верхнюю часть стека
- Извлечь или удалить элемент из вершины стека
Создание структуры данных стека
Стек классов: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
- max_size - максимальное количество элементов, ожидаемых в стеке.
- Элементы стека хранятся в списке Python.
- Top указывает на самый верхний индекс стека, который изначально берется -1, чтобы отметить пустой стек.
Исходный статус стека можно увидеть на рисунке, где max_size = 5.
Вставить элемент в стек
Теперь, если вы хотите ввести или отправить элемент в стек, вы должны помнить, что
- Вверху будет указан индекс, в который будет вставлен элемент.
- И что ни один элемент не будет вставлен, когда стек заполнен, т.е. когда max_size = top.
Так каким должен быть алгоритм ??
# возвращает максимальный размер стека def get_max_size (self): return self .__ max_size # возвращает значение типа bool независимо от того, заполнен стек или нет, True, если полный стек и False в противном случае def is_full (self): return self.get_max_size () - 1 == self .__ top # подталкивает элемент вверху стека def push (self, data): if (self.is_full ()): print ('stack is already full') else: self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data # Вы можете использовать приведенный ниже __str __ () для печати элементов объекта DS во время отладки def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = '' .join (msg) msg = 'Данные стека (сверху вниз):' + msg return msgТеперь, когда вы выполните следующее:
stack1 = Стек (4)
# Нажмите все необходимые элементы.
stack1.push («А»)
stack1.push («B»)
stack1.push («C»)
stack1.push («E»)
печать (stack1.is_full ())
печать (стек1)
Вывод:
стек уже заполнен
Правда
Данные стека (сверху вниз): D C B A
Поп-элементы из стека
Теперь, когда вы вставили элементы в стек, вы хотите их вставить, поэтому вам нужно позаботиться о следующем:
- Стек не пуст, т.е. вверху! = -1
- Когда вы удаляете данные, верхняя часть должна указывать на предыдущую вершину стека.
Итак, каков будет алгоритм ??
# возвращает значение типа bool, является ли стек пустым или нет, True, если пуст, и False, в противном случае def is_empty (self): return self .__ top == - 1 # возвращает всплывающее значение def pop (self): if (self.is_empty ()): print ('ничего не выскакивать, уже пусто') else: a = self .__ elements [self .__ top] self .__ top = self .__ top-1 вернуть # отображать все элементы стека сверху вниз def display (self): для i в диапазоне (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()Теперь, учитывая ранее созданный стек, попробуйте вытолкнуть элементы
печать (stack1.pop ())
печать (stack1.pop ())
печать (стек1)
печать (stack1.pop ())
печать (stack1.pop ())
печать (stack1.pop ())
оператор goto c ++
Вывод:
D
C
Данные стека (сверху вниз): B A
B
К
нечего лопнуть, уже пусто
Применение структуры данных стека
- Пример 1:
Стек используется для реализации алгоритма сопоставления скобок для оценки арифметических выражений, а также для реализации вызовов методов.
Ответ на который 5.
- Пример 2:
Буфер обмена в Windows использует два стека для выполнения операций отмены и повторения (ctrl + z, ctrl + y). Вы бы работали с текстовыми редакторами Windows, такими как MS-Word, Блокнот и т. Д. Вот текст, написанный в MS-Word. Обратите внимание, как текст изменился при нажатии Ctrl-Z и Ctrl-Y.
Вот код, имитирующий операцию отмены-повтора. Просмотрите код и посмотрите, как в этой реализации используется стек.
# создание стека классов class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1 def is_full (self): if (self .__ top == self .__ max_size-1): return True return False def is_empty (self): if (self .__ top == - 1): return True return False def push (self, data): if (self.is_full ()): print ('Стек заполнен !!') else: self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self): if (self.is_empty ()): print ('Стек пуст! ! ') else: data = self .__ elements [self .__ top] self .__ top- = 1 return data def display (self): if (self.is_empty ()): print (' Стек пуст ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size # Вы можете использовать приведенный ниже __str __ () для печати элементов Объект DS во время отладки def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg =' Данные стека (сверху вниз): '+ msg return ms g # функция для выполнения операции удаления или возврата def remove (): глобальный буфер обмена, undo_stack data = clipboard [len (clipboard) -1] clipboard.remove (data) undo_stack.push (data) print ('Remove:', clipboard) # функция для реализации операции отмены def undo (): глобальный буфер обмена, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Нет данных для отмены') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Undo:', clipboard) # функция для реализации операции повтора def redo (): global clipboard, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Нет данных to redo ') else: data = redo_stack.pop () if (данные не в буфере обмена): print (' Нет данных для повтора ') redo_stack.push (data) else: clipboard.remove (data) undo_stack.push ( data) print ('Повторить:', буфер обмена) clipboard = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (clipboard)) redo_stack = Stack (len (буфер обмена)) удалить () отменить () повторить ()Вывод:
Удалить: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’]
Отменить: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’]
Повторить: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’]
На этом мы подошли к концу статьи о структуре данных стека в Python. Если вы успешно поняли и запустили коды самостоятельно, вы больше не новичок в структуре данных стека.
Есть вопрос к нам? Пожалуйста, укажите это в комментариях к этой статье, и мы свяжемся с вами как можно скорее.
Чтобы получить более глубокие знания о Python и его различных приложениях, вы можете зарегистрироваться в режиме реального времени. с круглосуточной поддержкой и пожизненным доступом.