Python Language
Apilar
Buscar..
Introducción
Una pila es un contenedor de objetos que se insertan y eliminan de acuerdo con el principio de último en entrar, primero en salir (LIFO). En las pilas de pushdown solo se permiten dos operaciones: empujar el elemento en la pila y sacar el elemento de la pila . Una pila es una estructura de datos de acceso limitado: los elementos se pueden agregar y eliminar de la pila solo en la parte superior . Aquí hay una definición estructural de una pila: una pila está vacía o consiste en una parte superior y el resto que es una pila.
Sintaxis
- stack = [] # Crea la pila
- stack.append (objeto) # Agregar objeto a la parte superior de la pila
- stack.pop () -> object # Devuelve el objeto más superior de la pila y también lo elimina
- list [-1] -> object # Mira el objeto más superior sin quitarlo
Observaciones
De Wikipedia :
En informática, una pila es un tipo de datos abstracto que sirve como una colección de elementos, con dos operaciones principales: push , que agrega un elemento a la colección, y pop , que elimina el elemento agregado más reciente que aún no se eliminó.
Debido a la forma en que se accede a sus elementos, las pilas son también conocidos como último en entrar, primero en salir (LIFO) apila.
En Python se pueden usar listas como pilas con append() como push y pop() como operaciones emergentes. Ambas operaciones se ejecutan en tiempo constante O (1).
La estructura de datos deque de Python también se puede utilizar como una pila. En comparación con las listas, los deque permiten operaciones de inserción y pop con una complejidad de tiempo constante desde ambos extremos.
Creación de una clase de pila con un objeto de lista
Usando un objeto de list , puede crear una pila genérica completamente funcional con métodos auxiliares, como mirar y comprobar si la pila está vacía. Echa un vistazo a los documentos oficiales de Python para utilizar la list como Stack aquí .
#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 ejemplo de ejecución:
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())
Salida:
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
Paréntesis de paréntesis
Las pilas se utilizan a menudo para el análisis. Una tarea de análisis simple es verificar si una cadena de paréntesis coincide.
Por ejemplo, la cadena ([]) coincide, porque los corchetes exterior e interior forman pares. ()<>) no coincide, porque el último ) no tiene pareja. ([)] tampoco coincide, porque los pares deben estar completamente dentro o fuera de otros pares.
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()