Comment et pourquoi faire la queue sur deux piles

Bonjour, Habr!

Cet article a été écrit pour les débutants en programmation olympiade et les développeurs novices qui se préparent à subir des entretiens algorithmiques. À la fin du puzzle bonus. Si intéressé, je demande un chat :)

Rappelons d'abord les bases:

Pile

La pile met en œuvre le principe de LIFO (Eng. Last in - first out, "last come, first come out").

La pile a deux opérations principales:

• push - poussez un élément sur la pile
• pop - récupère un élément de la pile

La pile est généralement implémentée sur un tableau (toujours possible sur une liste chaînée). Vous pouvez en savoir plus sur la pile et son implémentation ici.

File d'attente

Une file d'attente est une structure de données avec accès aux éléments FIFO (premier entré, premier sorti - «premier arrivé, premier allé»)

Une file d'attente a deux méthodes principales dans son interface:

• push - place un élément à la fin de la file d'attente
• pop - récupère un élément à l'avant de la file d'attente

En savoir plus sur la file d'attente régulière ici .

Envisagez généralement deux approches de base pour la mise en œuvre de la file d'attente:

1. Sur la baie
2. Sur une liste chaînée

Pourquoi la pile est-elle plus froide que la ligne

Imaginez que notre structure de données devrait prendre en charge l'ensemble des opérations suivantes:

• Support minimum (min)
• Assistance maximale (max)
• Gcd support (le plus grand diviseur commun anglais - le plus grand diviseur commun)
• Prise en charge Lcm (multiple le moins commun)

Toutes ces opérations sont associatives (forment un semi-groupe), mais aucune d'entre elles n'a d'élément inverse (ne forme pas de groupe).

Pour la pile, vous pouvez très simplement prendre en charge l'une des opérations suivantes: il suffit d'en stocker un couple sur le dessus:

$$

$$(élément, operationResult)$$

où le deuxième élément de la paire est le résultat de l'opération appliquée à tous les éléments de la pile.

Voici un exemple d'une implémentation de prise en charge de pile minimale 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] 

Maintenant, réfléchissez à la façon de faire la même astuce avec la file d'attente? Si vous essayez avec une file d'attente classique organisée sur un tableau, il est peu probable que quelque chose fonctionne. Cela est dû au fait que l'opération minimale n'a pas l'opération inverse (comme l'opération d'addition a l'opération de soustraction, par exemple). Comme vous l'avez peut-être deviné, je parlerai de l'implémentation pas si classique d'une file d'attente sur deux piles.

File d'attente à deux piles

La principale condition qui doit être remplie est que toutes les opérations doivent être effectuées pour O (1) amorti.

Prenez deux piles: s1 et s2.

L'opération push sera toujours effectuée sur la pile s1.

L'opération pop sera organisée comme suit: si la pile s2 est vide, nous transférons tous les éléments de s1 à s2 par des appels successifs à pop et push. Maintenant, la pile s2 contient des éléments dans l'ordre inverse (l'élément le plus haut est le tout premier élément mis à notre tour).

Si s2 n'est pas vide, nous en retirons bêtement les éléments. Dès que s2 est à nouveau vide, nous répétons la même opération.

Code 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()) 

Temps de travail

Opération push : nous poussons bêtement un élément sur la pile s1. Temps de fonctionnement O (1).

Opération Pop : Pour chaque élément, nous ne faisons pas plus d'un transfert de pile à pile, donc le temps de travail amorti sera O (1).

Opération get_min : Les minima sont connus pour les piles s1 et s2, nous prenons donc le minimum des minima. Temps de fonctionnement O (1).

Défi bonus

Étant donné une séquence de N nombres. On donne le nombre M <N. Il faut en temps linéaire trouver un segment de longueur M sur lequel le produit min * max est maximum.

Conclusion

Merci d'avoir lu jusqu'au bout!

Si le sujet vous intéresse, vous pouvez lire ici comment créer une file d'attente persistante sur deux piles, ou attendre la publication de mon prochain sujet.

Écrivez dans les commentaires quelles tâches sur deux piles vous avez dû résoudre lors d'entrevues ou de concours.