Pilas y colas en Python

    Introducci贸n

    Las estructuras de datos organizan el almacenamiento en las computadoras para que podamos acceder y modificar los datos de manera eficiente. Las pilas y las colas son algunas de las primeras estructuras de datos definidas en inform谩tica.

    Sencillos de aprender y f谩ciles de implementar, sus usos son comunes y lo m谩s probable es que los incorpore en su software para diversas tareas.

    Es com煤n que las pilas y las colas se implementen con una matriz o una lista vinculada. Confiaremos en el List estructura de datos para acomodar tanto Pilas como Colas.

    驴C贸mo trabajan?

    Apilar

    Las pilas, como sugiere el nombre, siguen las 脷ltimo en entrar primero en salir (LIFO) principio. Como si apilamos monedas una encima de la otra, la 煤ltima moneda que ponemos en la parte superior es la que es la primera que se saca de la pila m谩s tarde.

    Para implementar una pila, por lo tanto, necesitamos dos operaciones simples:

    • push – agrega un elemento a la parte superior de la pila:
    • pop – elimina el elemento en la parte superior de la pila:

    Cola

    Las colas, como sugiere el nombre, siguen las Primero en entrar primero en salir (FIFO) principio. Como si esperara en una cola las entradas del cine, el primero en hacer fila es el primero en comprar una entrada y disfrutar de la pel铆cula.

    Para implementar una cola, por lo tanto, necesitamos dos operaciones simples:

    • enqueue – agrega un elemento al final de la cola:
    • dequeue – elimina el elemento al principio de la cola:

    Pilas y colas usando listas

    Python incorporado List La estructura de datos viene con m茅todos para simular operaciones tanto de pila como de cola.

    Consideremos una pila de letras:

    letters = []
    
    # Let's push some letters into our list
    letters.append('c')
    letters.append('a')
    letters.append('t')
    letters.append('g')
    
    # Now let's pop letters, we should get 'g'
    last_item = letters.pop()
    print(last_item)
    
    # If we pop again we'll get 't'
    last_item = letters.pop()
    print(last_item)
    
    # 'c' and 'a' remain
    print(letters) # ['c', 'a']
    

    Podemos usar las mismas funciones para implementar una cola. los pop La funci贸n opcionalmente toma el 铆ndice del elemento que queremos recuperar como argumento.

    Entonces podemos usar pop con el primer 铆ndice de la lista, es decir 0, para obtener un comportamiento similar al de una cola.

    Considere una “cola” de frutas:

    fruits = []
    
    # Let's enqueue some fruits into our list
    fruits.append('banana')
    fruits.append('grapes')
    fruits.append('mango')
    fruits.append('orange')
    
    # Now let's dequeue our fruits, we should get 'banana'
    first_item = fruits.pop(0)
    print(first_item)
    
    # If we dequeue again we'll get 'grapes'
    first_item = fruits.pop(0)
    print(first_item)
    
    # 'mango' and 'orange' remain
    print(fruits) # ['c', 'a']
    

    Nuevamente, aqu铆 usamos el append y pop operaciones de la lista para simular las operaciones centrales de una cola.

    Pilas y colas con la biblioteca Deque

    Python tiene un deque (pronunciado ‘deck’) biblioteca que proporciona una secuencia con m茅todos eficientes para trabajar como una pila o una cola.

    deque es la abreviatura de Double Ended Queue: una cola generalizada que puede obtener el primer o el 煤ltimo elemento almacenado:

    from collections import deque
    
    # you can initialize a deque with a list 
    numbers = deque()
    
    # Use append like before to add elements
    numbers.append(99)
    numbers.append(15)
    numbers.append(82)
    numbers.append(50)
    numbers.append(47)
    
    # You can pop like a stack
    last_item = numbers.pop()
    print(last_item) # 47
    print(numbers) # deque([99, 15, 82, 50])
    
    # You can dequeue like a queue
    first_item = numbers.popleft()
    print(first_item) # 99
    print(numbers) # deque([15, 82, 50])
    

    Si desea obtener m谩s informaci贸n sobre deque biblioteca y otros tipos de colecciones que proporciona Python, puede leer nuestro art铆culo Introducci贸n al m贸dulo de colecciones de Python.

    Implementaciones m谩s estrictas en Python

    Si su c贸digo necesita una pila y proporciona un List, no hay nada que impida que un programador llame insert, remove u otras funciones de lista que afectar谩n el orden de su pila. Esto arruina fundamentalmente el punto de definir una pila, ya que ya no funciona como deber铆a.

    Hay ocasiones en las que nos gustar铆a asegurarnos de que solo se puedan realizar operaciones v谩lidas con nuestros datos.

    Podemos crear clases que solo exponen los m茅todos necesarios para cada estructura de datos.

    Para hacerlo, creemos un nuevo archivo llamado stack_queue.py y definir dos clases:

    # A simple class stack that only allows pop and push operations
    class Stack:
    
        def __init__(self):
            self.stack = []
    
        def pop(self):
            if len(self.stack) < 1:
                return None
            return self.stack.pop()
    
        def push(self, item):
            self.stack.append(item)
    
        def size(self):
            return len(self.stack)
    
    # And a queue that only has enqueue and dequeue operations
    class Queue:
    
        def __init__(self):
            self.queue = []
    
        def enqueue(self, item):
            self.queue.append(item)
    
        def dequeue(self):
            if len(self.queue) < 1:
                return None
            return self.queue.pop(0)
    
        def size(self):
            return len(self.queue) 
    

    Los programadores que utilizan nuestro Stack y Queue ahora se les anima a utilizar los m茅todos proporcionados para manipular los datos.

    Ejemplos

    Imagina que eres un desarrollador que trabaja en un nuevo procesador de textos. Tiene la tarea de crear una funci贸n de deshacer, lo que permite a los usuarios retroceder en sus acciones hasta el comienzo de la sesi贸n.

    Una pila es ideal para este escenario. Podemos registrar cada acci贸n que realiza el usuario empuj谩ndola a la pila. Cuando el usuario quiera deshacer una acci贸n, la sacar谩 de la pila. Podemos simular r谩pidamente la funci贸n de esta manera:

    document_actions = Stack()
    
    # The first enters the title of the document
    document_actions.push('action: enter; text_id: 1; text: This is my favourite document')
    # Next they center the text
    document_actions.push('action: format; text_id: 1; alignment: center')
    # As with most writers, the user is unhappy with the first draft and undoes the center alignment
    document_actions.pop()
    # The title is better on the left with bold font
    document_actions.push('action: format; text_id: 1; style: bold')
    

    Las colas tambi茅n tienen usos generalizados en programaci贸n. Piense en juegos como Street Fighter o Super Smash Brothers. Los jugadores de esos juegos pueden realizar movimientos especiales presionando una combinaci贸n de botones. Estas combinaciones de botones se pueden almacenar en una cola.

    Ahora imagina que eres un desarrollador que trabaja en un nuevo juego de lucha. En su juego, cada vez que se presiona un bot贸n, se activa un evento de entrada. Un evaluador not贸 que si los botones se presionan demasiado r谩pido, el juego solo procesa el primero y los movimientos especiales no funcionar谩n.

    Puedes arreglar eso con una cola. Podemos poner en cola todos los eventos de entrada a medida que ingresan. De esta manera, no importa si los eventos de entrada vienen con poco tiempo entre ellos, todos se almacenar谩n y estar谩n disponibles para su procesamiento. Cuando procesamos los movimientos, podemos quitarlos de la cola. Se puede realizar un movimiento especial de la siguiente manera:

    input_queue = Queue()
    
    # The player wants to get the upper hand so pressing the right combination of buttons quickly
    input_queue.enqueue('DOWN')
    input_queue.enqueue('RIGHT')
    input_queue.enqueue('B')
    
    # Now we can process each item in the queue by dequeueing them
    key_pressed = input_queue.dequeue() # 'DOWN'
    
    # We'll probably change our player position
    key_pressed = input_queue.dequeue() # 'RIGHT'
    
    # We'll change the player's position again and keep track of a potential special move to perform
    key_pressed = input_queue.dequeue() # 'B'
    
    # This can do the act, but the game's logic will know to do the special move
    

    Conclusi贸n

    Las pilas y las colas son estructuras de datos simples que nos permiten almacenar y recuperar datos de forma secuencial. En una pila, el 煤ltimo elemento que ingresamos es el primero en salir. En una cola, el primer elemento que ingresamos es el primero en salir.

    Podemos agregar elementos a una pila usando el push operaci贸n y recuperar elementos usando el pop operaci贸n. Con las colas, agregamos elementos usando el enqueue operaci贸n y recuperar elementos usando el dequeue operaci贸n.

    En Python, podemos implementar pilas y colas simplemente usando la funci贸n incorporada List estructura de datos. Python tambi茅n tiene la deque biblioteca que puede proporcionar operaciones de pila y cola de manera eficiente en un objeto. Finalmente, hemos creado nuestras clases de pila y cola para un control m谩s estricto de nuestros datos.

    Hay muchos casos de uso del mundo real para pilas y colas, entenderlos nos permite resolver muchos problemas de almacenamiento de datos de una manera f谩cil y efectiva.

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *