Python Language
Empiler
Recherche…
Introduction
Une pile est un conteneur d'objets insérés et retirés selon le principe du dernier entré, premier sorti (LIFO). Dans les piles pushdown, seules deux opérations sont autorisées: enfoncez l'élément dans la pile et sortez-le de la pile . Une pile est une structure de données à accès limité - des éléments peuvent être ajoutés et supprimés de la pile uniquement en haut . Voici une définition structurelle d'une pile: une pile est soit vide, soit constituée d'un sommet et le reste d'une pile.
Syntaxe
- stack = [] # Crée la pile
- stack.append (object) # Ajoute un objet au sommet de la pile
- stack.pop () -> object # Renvoie le plus haut objet de la pile et le supprime également
- list [-1] -> object # Jetez un coup d'oeil sur l'objet le plus haut sans le supprimer
Remarques
De Wikipedia :
En informatique, une pile est un type de données abstrait qui sert de collection d'éléments, avec deux opérations principales: push , qui ajoute un élément à la collection, et pop , qui supprime l'élément le plus récemment ajouté qui n'a pas encore été supprimé.
En raison de la façon dont leurs éléments sont accessibles, les piles sont également connus comme Last In, First Out (LIFO) piles.
En Python, on peut utiliser des listes comme piles avec append() comme push et pop() comme opérations pop. Les deux opérations sont exécutées à temps constant O (1).
La structure de données deque de Python peut également être utilisée comme une pile. Par rapport aux listes, les deque permettent des opérations de push et de pop avec une complexité constante à chaque extrémité.
Création d'une classe Stack avec un objet List
En utilisant un objet list , vous pouvez créer une pile générique entièrement fonctionnelle avec des méthodes d'aide telles que la vérification et la vérification de l'empilement de la pile. Consultez la documentation officielle de Python pour utiliser la list comme Stack ici .
#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
Un exemple d'exécution:
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())
Sortie:
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
Parenthèses parentales
Les piles sont souvent utilisées pour l'analyse. Une tâche d'analyse simple consiste à vérifier si une chaîne de parenthèses correspond.
Par exemple, la chaîne ([]) correspond, car les crochets externes et internes forment des paires. ()<>) ne correspond pas, car le dernier ) n’a pas de partenaire. ([)] ne correspond pas non plus, car les paires doivent être entièrement à l'intérieur ou à l'extérieur des autres paires.
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()