A pila Es una estructura de datos lineal que almacena elementos en un Último en entrar/primero en salir (LIFO) o modo Primero en entrar/Último en salir (FILO). En la pila, se agrega un nuevo elemento en un extremo y se elimina un elemento solo de ese extremo. Las operaciones de inserción y eliminación a menudo se denominan push y pop.

Las funciones asociadas a la pila son:

• vacío() – Devuelve si la pila está vacía – Complejidad del tiempo: O(1)
• tamaño() – Devuelve el tamaño de la pila – Complejidad del tiempo: O(1)
• arriba() / mirar() – Devuelve una referencia al elemento superior de la pila – Complejidad del tiempo: O(1)
• empujar(un) – Inserta el elemento ‘a’ en la parte superior de la pila – Complejidad del tiempo: O(1)
• estallido() – Elimina el elemento superior de la pila – Complejidad del tiempo: O(1)

Implementación:

Hay varias formas de implementar una pila en Python. Este artículo cubre la implementación de una pila utilizando estructuras de datos y módulos de la biblioteca Python.
La pila en Python se puede implementar de las siguientes maneras:

• lista
• Colecciones.deque
• cola.LifoQueue

Implementación usando lista:

La lista de estructuras de datos integrada de Python se puede utilizar como pila. En lugar de push(), append() se usa para agregar elementos a la parte superior de la pila mientras pop() elimina el elemento en orden LIFO.
Desafortunadamente, la lista tiene algunas deficiencias. El mayor problema es que puede tener problemas de velocidad a medida que crece. Los elementos de la lista se almacenan uno al lado del otro en la memoria; si la pila crece más que el bloque de memoria que la contiene actualmente, entonces Python necesita realizar algunas asignaciones de memoria. Esto puede hacer que algunas llamadas append() demoren mucho más que otras.

# Python program to # demonstrate stack implementation # using list stack = [] # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack ['a', 'b', 'c'] Elements popped from stack: c b a Stack after elements are popped: []>

Implementación usando colecciones.deque:

La pila de Python se puede implementar usando la clase deque del módulo de colecciones. Se prefiere Deque a la lista en los casos en los que necesitamos operaciones de agregar y extraer más rápidas desde ambos extremos del contenedor, ya que deque proporciona una complejidad de tiempo O(1) para las operaciones de agregar y extraer en comparación con la lista que proporciona O(n). complejidad del tiempo.

Se utilizan los mismos métodos en deque que se ven en la lista, append() y pop().

# Python program to # demonstrate stack implementation # using collections.deque from collections import deque stack = deque() # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack:') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack: deque(['a', 'b', 'c']) Elements popped from stack: c b a Stack after elements are popped: deque([])>

Implementación utilizando el módulo de cola.

El módulo de cola también tiene una cola LIFO, que es básicamente una pila. Los datos se insertan en la cola usando la función put() y get() saca datos de la cola.

Hay varias funciones disponibles en este módulo:

• tamaño máximo – Número de artículos permitidos en la cola.
• vacío() – Devuelve Verdadero si la cola está vacía, Falso en caso contrario.
• lleno() – Devuelve Verdadero si hay tamaño máximo elementos en la cola. Si la cola se inicializó con maxsize=0 (el valor predeterminado), entonces full() nunca devuelve True.
• conseguir() – Eliminar y devolver un artículo de la cola. Si la cola está vacía, espere hasta que haya un artículo disponible.
• get_nowait() – Devuelve un artículo si hay uno disponible inmediatamente; de ​​lo contrario, genera QueueEmpty.
• poner (artículo) – Poner un artículo en la cola. Si la cola está llena, espere hasta que haya un espacio libre disponible antes de agregar el artículo.
• put_nowait(elemento) – Poner un elemento en la cola sin bloquearlo. Si no hay ningún espacio libre disponible inmediatamente, aumente QueueFull.
• qtamaño() – Devuelve el número de elementos en la cola.

# Python program to # demonstrate stack implementation # using queue module from queue import LifoQueue # Initializing a stack stack = LifoQueue(maxsize=3) # qsize() show the number of elements # in the stack print(stack.qsize()) # put() function to push # element in the stack stack.put('a') stack.put('b') stack.put('c') print('Full: ', stack.full()) print('Size: ', stack.qsize()) # get() function to pop # element from stack in # LIFO order print('
Elements popped from the stack') print(stack.get()) print(stack.get()) print(stack.get()) print('
Empty: ', stack.empty())>

0 Full: True Size: 3 Elements popped from the stack c b a Empty: True>

Implementación utilizando una lista unidireccional:

La lista vinculada tiene dos métodos addHead(item) y removeHead() que se ejecutan en tiempo constante. Estos dos métodos son adecuados para implementar una pila.

• obtenerTamaño() – Obtenga la cantidad de elementos en la pila.
• esta vacio() – Devuelve Verdadero si la pila está vacía, Falso en caso contrario.
• ojeada() – Devuelve el artículo superior de la pila. Si la pila está vacía, genera una excepción.
• empujar (valor) – Introduzca un valor en la cabecera de la pila.
• estallido() – Eliminar y devolver un valor en el encabezado de la pila. Si la pila está vacía, genera una excepción.

A continuación se muestra la implementación del enfoque anterior:

# Python program to demonstrate # stack implementation using a linked list. # node class class Node: def __init__(self, value): self.value = value self.next = None class Stack: # Initializing a stack. # Use a dummy node, which is # easier for handling edge cases. def __init__(self): self.head = Node('head') self.size = 0 # String representation of the stack def __str__(self): cur = self.head.next out = '' while cur: out += str(cur.value) + '->' cur = cur.next return out[:-2] # Obtener el tamaño actual de la pila def getSize(self): return self.size # Comprobar si la pila está vacía def isEmpty(self): return self.size = = 0 # Obtener el elemento superior de la pila def peek(self): # Verificación sanitaria para ver si # estamos mirando una pila vacía. if self.isEmpty(): return Ninguno return self.head.next.value # Inserta un valor en la pila. def push(self, valor): nodo = Nodo(valor) nodo.next = self.head.next # ¡Haga que el nuevo nodo apunte al cabezal actual self.head.next = nodo #!!! # Actualiza el encabezado para que sea el nuevo nodo self.size += 1 # Elimina un valor de la pila y regresa. def pop(self): if self.isEmpty(): rise Exception('Saliendo de una pila vacía') remove = self.head.next self.head.next = remove.next #!!! cambiado self.size -= 1 return remove.value # Código del controlador if __name__ == '__main__': stack = Stack() for i in range(1, 11): stack.push(i) print(f' Pila: {pila}') para _ en rango(1, 6): valor_superior = pila.pop() print(f'Pop: {valor_superior}') # nombre de variable cambiado print(f'Pila: { pila}')>

Producción

Stack: 10->9->8->7->6->5->4->3->2->1 Pop: 10 Pop: 9 Pop: 8 Pop: 7 Pop: 6 Pila: 5->4->3->2->1>

Ventajas de la pila:

• Las pilas son estructuras de datos simples con un conjunto de operaciones bien definido, lo que las hace fáciles de entender y usar.
• Las pilas son eficientes para agregar y eliminar elementos, ya que estas operaciones tienen una complejidad temporal de O(1).
• Para invertir el orden de los elementos utilizamos la estructura de datos de pila.
• Las pilas se pueden utilizar para implementar funciones de deshacer/rehacer en aplicaciones.

Desventajas de la pila:

• La restricción de tamaño en Stack es un inconveniente y si están llenos, no puedes agregar más elementos a la pila.
• Las pilas no proporcionan acceso rápido a elementos distintos del elemento superior.
• Las pilas no admiten búsquedas eficientes, ya que hay que extraer elementos uno por uno hasta encontrar el elemento que está buscando.