Apilar en Python

Una pila es una estructura de datos lineal que almacena elementos en forma de último en entrar/primero en salir (LIFO) o 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 empujar y sacar.

Las funciones asociadas con la pila son:

• vacío() – Devuelve si la pila está vacía – Complejidad de tiempo: O (1)
• size() – Devuelve el tamaño de la pila – Complejidad de tiempo: O(1)
• top() / peek() – Devuelve una referencia al elemento superior de la pila – Complejidad de tiempo: O(1)
• push(a) – Inserta el elemento ‘a’ en la parte superior de la pila – Complejidad de tiempo: O(1)
• pop() – Elimina el elemento superior de la pila – Complejidad de 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 de Python. 
Stack en Python se puede implementar de las siguientes maneras: 

• lista
• Colecciones.deque
• cola.LifoCola

Implementación usando la lista:

La lista de estructura de datos incorporada de Python se puede usar como una pila. En lugar de push(), append() se usa para agregar elementos a la parte superior de la pila, mientras que 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 hacer algunas asignaciones de memoria. Esto puede hacer que algunas llamadas append() tarden 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('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
 
print('\nStack 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 collections.deque:

La pila de Python se puede implementar usando la clase deque del módulo de colecciones. Deque es preferible a la lista en los casos en los que necesitamos operaciones de adición y extracción más rápidas desde ambos extremos del contenedor, ya que deque proporciona una complejidad de tiempo O(1) para las operaciones de adición y extracción 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('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
 
print('\nStack 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 Queue 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 los datos de la cola. 

Hay varias funciones disponibles en este módulo: 

• maxsize : número de elementos permitidos en la cola.
• vacío() : devuelve verdadero si la cola está vacía, falso de lo contrario.
• full() : devuelve True si hay elementos de tamaño máximo en la cola. Si la cola se inicializó con maxsize=0 (el valor predeterminado), full() nunca devuelve True.
• get() : elimina y devuelve un elemento de la cola. Si la cola está vacía, espere hasta que haya un artículo disponible.
• get_nowait() : devuelve un elemento si hay uno disponible de inmediato; de lo contrario, genera QueueEmpty.
• put(elemento) – Poner un elemento en la cola. Si la cola está llena, espere hasta que haya un espacio disponible antes de agregar el artículo.
• put_nowait (elemento) : coloca un elemento en la cola sin bloquearlo. Si no hay un espacio libre disponible de inmediato, genere QueueFull.
• qsize() : devuelve la cantidad 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('\nElements popped from the stack')
print(stack.get())
print(stack.get())
print(stack.get())
 
print("\nEmpty: ", stack.empty())

0
Full:  True
Size:  3

Elements popped from the stack
c
b
a

Empty:  True

Implementación usando una lista enlazada simple:

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

• getSize() : obtiene la cantidad de elementos en la pila.
• isEmpty() : devuelve True si la pila está vacía, False en caso contrario.
• peek() : devuelve el elemento superior de la pila. Si la pila está vacía, genera una excepción.
• push(value) – Inserta un valor en la cabeza de la pila.
• pop() : elimina y devuelve un valor en la cabeza 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[:-3]
 
    # Get the current size of the stack
    def getSize(self):
        return self.size
 
    # Check if the stack is empty
    def isEmpty(self):
        return self.size == 0
 
    # Get the top item of the stack
    def peek(self):
 
        # Sanitary check to see if we
        # are peeking an empty stack.
        if self.isEmpty():
            raise Exception("Peeking from an empty stack")
        return self.head.next.value
 
    # Push a value into the stack.
    def push(self, value):
        node = Node(value)
        node.next = self.head.next
        self.head.next = node
        self.size += 1
 
    # Remove a value from the stack and return.
    def pop(self):
        if self.isEmpty():
            raise Exception("Popping from an empty stack")
        remove = self.head.next
        self.head.next = self.head.next.next
        self.size -= 1
        return remove.value
 
 
# Driver Code
if __name__ == "__main__":
    stack = Stack()
    for i in range(1, 11):
        stack.push(i)
    print(f"Stack: {stack}")
 
    for _ in range(1, 6):
        remove = stack.pop()
        print(f"Pop: {remove}")
    print(f"Stack: {stack}")

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