Python Language
стек
Поиск…
Вступление
Стек представляет собой контейнер объектов, которые вставляются и удаляются в соответствии с принципом последнего выхода (LIFO). В стеках сбрасывания разрешены только две операции: нажмите элемент в стек и вытащите элемент из стека . Стек представляет собой структуру данных с ограниченным доступом - элементы могут быть добавлены и удалены из стека только сверху . Вот структурное определение стека: стек либо пуст, либо состоит из вершины, а остальное - стека.
Синтаксис
- stack = [] # Создать стек
- stack.append (object) # Добавить объект в начало стека
- stack.pop () -> object # Возвращает самый верхний объект из стека, а также удаляет его
- list [-1] -> object # Заглянуть в самый верхний объект, не удаляя его
замечания
Из Википедии :
В информатике стек представляет собой абстрактный тип данных, который служит в качестве набора элементов с двумя основными операциями: push , который добавляет элемент в коллекцию и pop , который удаляет последний добавленный элемент, который еще не был удален.
В связи с тем , как их элементы , доступ, стеки также известны как Last-In, First-Out (LIFO) суммируется.
В Python можно использовать списки как стеки с append() как push и pop() качестве поп-операций. Обе операции выполняются в постоянное время O (1).
Структура данных deque Python также может использоваться как стек. По сравнению с списками, deque s позволяет выполнять операции push и pop с постоянной сложностью по времени с обоих концов.
Создание класса Stack с помощью объекта списка
Используя объект list вы можете создать полностью функциональный общий стек со вспомогательными методами, такими как просмотр и проверка, если стек пуст. Ознакомьтесь с официальными документами python для использования list как Stack здесь .
#define a stack class
class Stack:
def __init__(self):
self.items = []
#method to check the stack is empty or not
def isEmpty(self):
return self.items == []
#method for pushing an item
def push(self, item):
self.items.append(item)
#method for popping an item
def pop(self):
return self.items.pop()
#check what item is on top of the stack without removing it
def peek(self):
return self.items[-1]
#method to get the size
def size(self):
return len(self.items)
#to view the entire stack
def fullStack(self):
return self.items
Пример:
stack = Stack()
print('Current stack:', stack.fullStack())
print('Stack empty?:', stack.isEmpty())
print('Pushing integer 1')
stack.push(1)
print('Pushing string "Told you, I am generic stack!"')
stack.push('Told you, I am generic stack!')
print('Pushing integer 3')
stack.push(3)
print('Current stack:', stack.fullStack())
print('Popped item:', stack.pop())
print('Current stack:', stack.fullStack())
print('Stack empty?:', stack.isEmpty())
Выход:
Current stack: []
Stack empty?: True
Pushing integer 1
Pushing string "Told you, I am generic stack!"
Pushing integer 3
Current stack: [1, 'Told you, I am generic stack!', 3]
Popped item: 3
Current stack: [1, 'Told you, I am generic stack!']
Stack empty?: False
Параллельные партисы
Стеки часто используются для синтаксического анализа. Простая задача синтаксического анализа состоит в проверке соответствия строк круглых скобок.
Например, строка ([]) соответствует, потому что внешние и внутренние скобки образуют пары. ()<>) не соответствует, потому что последний ) не имеет партнера. ([)] также не соответствует, потому что пары должны быть либо полностью внутри, либо вне других пар.
def checkParenth(str):
stack = Stack()
pushChars, popChars = "<({[", ">)}]"
for c in str:
if c in pushChars:
stack.push(c)
elif c in popChars:
if stack.isEmpty():
return False
else:
stackTop = stack.pop()
# Checks to see whether the opening bracket matches the closing one
balancingBracket = pushChars[popChars.index(c)]
if stackTop != balancingBracket:
return False
else:
return False
return not stack.isEmpty()