Skip to content

Estructuras de datos en Python: pilas, colas y deques

DS2

Prácticamente , cuando se trata de Python, rara vez hablamos de pilas , colas y deques . Aunque he estado usando Python durante más de 8 años , ¡honestamente, todavía no lo uso en ninguno de mis proyectos del mundo real !

Sin embargo, cubramos estas estructuras de datos en detalle y algunas imágenes .

Alerta de distracción: puede que le guste comprender cómo se desarrollan las matrices en Python desde cero. Consulte aquí para obtener un artículo asombroso.

1. Pilas en detalle

¿Alguna vez usó un botón de retroceso en su navegador ? ¡Las pilas funcionan de manera similar !
Abre facebook .com seguido de instagram .com seguido de twitter . Cuando HIT botón de retroceso, nos aterrizar en Twitter seguido por instagram seguido de facebook .

En resumen, 
primero ENTRAR, último SALIR

Bien, ahora algunas definiciones técnicas estrictas 😛

Una pila es una colección ordenada de elementos donde la adición de un nuevo elemento y la eliminación de los existentes siempre ocurren desde el mismo extremo.

Verifique a continuación, obtenemos una imagen clara .

stack
Crédito : https://upload.wikimedia.org/wikipedia/commons/b/b4/Lifo_stack.png

Push & pop forman 2 operaciones principales, donde push = insert & pop = remove .

El código siguiente implementa Stacks desde cero en Python .

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def top(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

  • Stack (): crea una nueva pila vacía.
  • push (elemento) : agrega un nuevo elemento a la pila.
  • pop () : elimina el elemento superior de la pila. Esto devuelve el elemento pop.
  • top (): Devuelve el elemento más alto de la pila.
  • isEmpty (): comprueba si la pila está vacía.
  • size () : Devuelve el tamaño de la pila.

¡Veamos si esto funciona !

s = Stack()

print (s.isEmpty())
: True

s.push(100)
s.push(200)

s.pop()
 : 200

s.size()
: 1

Eso funciona. ¡Uf !

2. Colas en detalle

¿Alguna vez has ido a un teatro a comprar una entrada ? Si es así, las colas funcionan de la misma manera.
La persona al frente de la cola tiene la oportunidad de obtener sus boletos primero, mientras que uno al final de la cola tendrá una oportunidad al final .

En resumen, su primer ENTRAR, primero en SALIR !

De acuerdo, nuevamente algunas definiciones técnicas estrictas 😛

Una  cola  es una colección ordenada de elementos donde la adición de nuevos elementos ocurre en un extremo y la eliminación de elementos existentes ocurre en el otro extremo. Se denominan delante y detrás respectivamente.

Cuando se agrega un elemento a la cola, comienza en la parte posterior y avanza hacia el frente . Consulte las imágenes a continuación para obtener una imagen clara .

Queues
Crédito : http://www.csit.parkland.edu/~mbrandyberry/CS2Java/Lessons/Stack_Queue/images/QueuePushPop.jpg


Cuando presionamos 1 , comienza desde la parte trasera . Luego, cuando presionamos 2, 3 , el número 1 comienza a moverse hacia el frente . Este proceso se llama poner en cola .

Imagina que queremos eliminar un elemento, esto sucede por orden de llegada . Por lo tanto, 1 aparecerá primero. Este proceso se llama sacar de cola .

¡Echa un vistazo a continuación!

enqDeq
Crédito : https://netmatze.files.wordpress.com/2014/08/queue.png

El siguiente código implementa Colas desde cero en Python .

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)
  • Queue (): crea una nueva cola vacía.
  • enqueue (elemento): agrega un nuevo elemento al final de la cola.
  • dequeue (): elimina el elemento frontal de la cola.
  • isEmpty (): comprueba si la cola está vacía.
  • size () : devuelve el tamaño de la cola.

Vamos a ejecutar el código!

q = Queue()

q.enqueue(2)
q.enqueue(10)

q.dequeue()
: 2 

q.size()
: 1

¡Uf ! Esto también funcionó .

3. Deque en detalle

Ha estado esperando entradas de cine en una cola interior y empieza a llover . Todos los que estaban afuera se apresuraban a refugiarse y se unían a la cola desde el final o desde el principio , solo para dejar de mojarse.

Entonces, cuando la lluvia termine, saldrán del frente de la cola o del final de la cola .
¿Eso tiene sentido? Así es como funciona el deque.

Entrada / Salida desde cualquier extremo de la cola.


Deque es ampliamente conocido como cola de dos extremos.

Verifique a continuación.

DeQ
deque

Podríamos notar, hay opciones de empujar o pop , ya sea desde el frente o al final . Esto supera las limitaciones de las colas que brindan más flexibilidad .

código siguiente implementa Deque desde cero en Python .

class Deque:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def addFront(self, item):
        self.items.append(item)

    def addRear(self, item):
        self.items.insert(0,item)

    def removeFront(self):
        return self.items.pop()

    def removeRear(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items)
  • Deque() , y crea un nuevo vacío.
  • addFront (item): agrega un nuevo elemento al frente de la deque.
  • addRear (elemento): agrega un nuevo elemento en la parte posterior de la etiqueta.
  • removeFront (): elimina el elemento frontal de la deque.
  • removeRear () : elimina el elemento trasero de la deque.
  • isEmpty () : prueba para ver si el deque está vacío.
  • size (): devuelve el número de elementos en la deque.


4. Diálogo final

Esa fue una manera fácil de entender pilas, colas y deque. Cada una de las estructuras de datos tiene sus propias implantaciones y hemos cubierto en términos sencillos cómo podemos crear todas estas estructuras de datos desde cero .

Asegúrese de leer otros artículos asombrosos en el blog .

Gracias por leer !


Es posible que no desee perderse estas emocionantes publicaciones:

Tags: