Cómo y por qué hacer cola en dos pilas

Hola Habr!

Esta publicación fue escrita para principiantes en programación olímpica y desarrolladores novatos que se están preparando para someterse a entrevistas algorítmicas. Al final del rompecabezas de bonificación. Si está interesado, le pido un gato :)

Primero, recordemos los conceptos básicos:

Pila

La pila implementa el principio de LIFO (Eng. Último en entrar - primero en salir, "último en llegar, primero en salir").

La pila tiene dos operaciones principales:

• empujar: empujar un elemento sobre la pila
• pop: obtén un elemento de la pila

La pila generalmente se implementa en una matriz (todavía es posible en una lista vinculada). Puede leer más sobre la pila y su implementación aquí.

Cola

Una cola es una estructura de datos con acceso a elementos FIFO (primero en entrar, primero en salir - "primero en llegar, primero en ir")

Una cola tiene dos métodos principales en su interfaz:

• push: coloca un elemento al final de la cola
• pop: obtén un elemento del frente de la cola

Lea más sobre la cola regular aquí .

Por lo general, considere dos enfoques básicos para la implementación de la cola:

1. En la matriz
2. En una lista vinculada

¿Por qué la pila es más fría que la línea?

Imagine que nuestra estructura de datos debería admitir el siguiente conjunto de operaciones:

• Soporte mínimo (min)
• Soporte máximo (max)
• Soporte de mcd (divisor común mayor inglés - máximo divisor común)
• Soporte Lcm (mínimo común múltiplo)

Todas estas operaciones son asociativas (forman un semigrupo), pero ninguna de ellas tiene un elemento inverso (no forma un grupo).

Para la pila, puede simplemente admitir cualquiera de las siguientes operaciones: simplemente almacene un par en su parte superior:

$$

$$(elemento, operaciónResultado)$$

donde el segundo elemento del par es el resultado de la operación aplicada a todos los elementos de la pila.

A continuación se muestra un ejemplo de una implementación de soporte de pila mínima en Python:

class Stack: def __init__(self): self.stack = [] def __bool__(self): return bool(self.stack) def push(self, elem): if self.stack: self.stack.append((elem, min(elem, self.stack[-1][1]))) else: self.stack.append((elem, elem)) def pop(self): return self.stack.pop()[0] def get_min(self): if not self.stack: return math.inf return self.stack[-1][1] 

Ahora piensa en cómo hacer el mismo truco con la cola. Si intenta con una cola clásica organizada en una matriz, es poco probable que algo funcione. Esto se debe al hecho de que la operación mínima no tiene la operación inversa (como la operación de suma tiene la operación de resta, por ejemplo). Como habrás adivinado, hablaré sobre la implementación no tan clásica de una cola en dos pilas.

Cola de dos pilas

La condición principal que debe cumplirse es que todas las operaciones deben realizarse para O (1) amortizado.

Toma dos pilas: s1 y s2.

La operación de inserción siempre se realizará en la pila s1.

La operación pop se organizará de la siguiente manera: si la pila s2 está vacía, transferimos todos los elementos de s1 a s2 mediante llamadas sucesivas a pop y push. Ahora la pila s2 contiene elementos en el orden inverso (el elemento superior es el primer elemento puesto en nuestro turno).

Si s2 no está vacío, estúpidamente sacamos los elementos de él. Tan pronto como s2 esté vacío nuevamente, repetimos la misma operación.

Código de Python:

 class Queue: def __init__(self): self.s1 = Stack() self.s2 = Stack() def push(self, elem): self.s1.push(elem) def pop(self): if not self.s2: while self.s1: self.s2.push(self.s1.pop()) return self.s2.pop() def get_min(self): return min(self.s1.get_min(), self.s2.get_min()) 

Tiempo de trabajo

Operación push : empujamos estúpidamente un artículo en la pila s1. Tiempo de funcionamiento O (1).

Operación pop : para cada elemento, no hacemos más de una transferencia de una pila a otra, por lo tanto, el tiempo de trabajo amortizado será O (1).

Operación get_min : los mínimos son conocidos por las pilas s1 y s2, por lo que solo tomamos el mínimo de los mínimos. Tiempo de funcionamiento O (1).

Bonus Challenge

Dada una secuencia de N números. Se da el número M <N. Se requiere en tiempo lineal para encontrar un segmento de longitud M en el que el producto min * max es máximo.

Conclusión

¡Gracias por leer hasta el final!

Si está interesado en el tema, puede leer cómo hacer una cola persistente en dos pilas aquí , o esperar el lanzamiento de mi próximo tema.

Escriba en los comentarios qué tareas en dos pilas tuvo que resolver en entrevistas o concursos.