Python Language
Stos
Szukaj…
Wprowadzenie
Stos jest pojemnikiem z obiektami, które są wstawiane i usuwane zgodnie z zasadą „ostatnie weszło pierwsze wyszło” (LIFO). W stosach push down dozwolone są tylko dwie operacje: wepchnij przedmiot do stosu i wyrzuć go ze stosu . Stos jest strukturą danych o ograniczonym dostępie - elementy można dodawać i usuwać ze stosu tylko u góry . Oto strukturalna definicja stosu: stos jest albo pusty, albo składa się z góry, a reszta to stos.
Składnia
- stos = [] # Utwórz stos
- stack.append (object) # Dodaj obiekt na górę stosu
- stack.pop () -> obiekt # Zwraca najwyższy obiekt ze stosu, a także go usuwa
- list [-1] -> obiekt # Zajrzyj do najwyższego obiektu, nie usuwając go
Uwagi
Z Wikipedii :
W informatyce stos jest abstrakcyjnym typem danych, który służy jako zbiór elementów, z dwiema głównymi operacjami: push , która dodaje element do kolekcji, i pop , który usuwa ostatnio dodany element, który nie został jeszcze usunięty.
Ze względu na sposób ich elementy są dostępne, stosy są również znane jako last in, first out (LIFO) stosów.
W Pythonie można używać list jako stosów z append() jako push i pop() jako operacji pop. Obie operacje działają w stałym czasie O (1).
deque danych deque Pythona może być również używana jako stos. W porównaniu do list, deque pozwalają na operacje push i pop ze stałą złożonością czasową z obu końców.
Tworzenie klasy Stack za pomocą obiektu List
Za pomocą obiektu list można utworzyć w pełni funkcjonalny ogólny Stos z metodami pomocniczymi, takimi jak podglądanie i sprawdzanie, czy stos jest Pusty. Sprawdź oficjalne dokumenty Pythona dotyczące używania list jako Stack tutaj .
#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
Przykładowy przebieg:
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())
Wynik:
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
Przetwarzanie nawiasów
Stosy są często używane do analizowania. Prostym zadaniem analizy jest sprawdzenie, czy ciąg nawiasów jest zgodny.
Na przykład ciąg ([]) jest zgodny, ponieważ nawiasy zewnętrzne i wewnętrzne tworzą pary. ()<>) nie pasuje, ponieważ ostatni ) nie ma partnera. ([)] również nie pasuje, ponieważ pary muszą znajdować się całkowicie wewnątrz lub na zewnątrz innych par.
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()