Como e por que fazer fila em duas pilhas

Olá Habr!

Este post foi escrito para iniciantes em programação de olimpíadas e desenvolvedores iniciantes que estão se preparando para passar por entrevistas algorítmicas. No final do quebra-cabeça bônus. Se estiver interessado, peço um gato :)

Primeiro, vamos relembrar o básico:

Stack

A pilha implementa o princípio do LIFO (Eng. Último a entrar - primeiro a sair, "último a chegar, primeiro a sair").

A pilha possui duas operações principais:

• push - empurra um item para a pilha
• pop - obtém um elemento da pilha

A pilha geralmente é implementada em uma matriz (ainda possível em uma lista vinculada). Você pode ler mais sobre a pilha e sua implementação aqui.

Fila

Uma fila é uma estrutura de dados com acesso a elementos FIFO (primeiro a entrar, primeiro a sair - “primeiro a chegar, primeiro a ir”)

Uma fila possui dois métodos principais em sua interface:

• push - coloca um item no final da fila
• pop - obtém um elemento da frente da fila

Leia mais sobre a fila regular aqui .

Geralmente, considere duas abordagens básicas para a implementação da fila:

1. Na matriz
2. Em uma lista vinculada

Por que a pilha é mais fria que a linha

Imagine que nossa estrutura de dados deva suportar o seguinte conjunto de operações:

• Suporte mínimo (min)
• Suporte máximo (máximo)
• Suporte para Gcd (maior divisor comum em inglês - maior divisor comum)
• Suporte Lcm (mínimo múltiplo comum)

Todas essas operações são associativas (formam um semigrupo), mas nenhuma delas possui um elemento inverso (não forma um grupo).

Para a pilha, você pode simplesmente suportar qualquer uma das seguintes operações: basta armazenar algumas no topo:

$$

$$(elemento, operationResult)$$

onde o segundo elemento do par é o resultado da operação aplicada a todos os elementos da pilha.

Abaixo está um exemplo de uma implementação mínima de suporte à pilha no 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] 

Agora pense em como fazer o mesmo truque com a fila? Se você tentar com uma fila clássica organizada em uma matriz, é improvável que algo dê certo. Isso se deve ao fato de que a operação mínima não possui a operação inversa (como a operação de adição possui a operação de subtração, por exemplo). Como você deve ter adivinhado, falarei sobre a implementação não tão clássica de uma fila em duas pilhas.

Fila de duas pilhas

A principal condição a ser atendida é que todas as operações sejam executadas para O (1) amortizado.

Pegue duas pilhas: s1 e s2.

A operação de push sempre será feita na pilha s1.

A operação pop será organizada da seguinte forma: se a pilha s2 estiver vazia, transferimos todos os elementos de s1 para s2 por chamadas sucessivas para pop e push. Agora a pilha s2 contém elementos na ordem inversa (o elemento superior é o primeiro elemento colocado por nossa vez).

Se s2 não estiver vazio, obtemos estupidamente os elementos dele. Assim que s2 estiver vazio novamente, repetimos a mesma operação.

Código 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()) 

Tempo de trabalho

Operação push : estupidamente colocamos um item na pilha s1. Tempo de operação O (1).

Operação pop : Para cada elemento, não fazemos mais do que uma transferência de uma pilha para outra, portanto, o tempo de trabalho amortizado será O (1).

Operação get_min : os mínimos são conhecidos pelas pilhas s1 e s2, portanto, apenas tiramos o mínimo dos mínimos. Tempo de operação O (1).

Desafio de bônus

Dada uma sequência de N números. É fornecido o número M <N. É necessário em tempo linear encontrar um segmento de comprimento M no qual o produto min * max é máximo.

Conclusão

Obrigado por ler até o fim!

Se você está interessado no tópico, pode ler como criar uma fila persistente em duas pilhas aqui ou aguardar o lançamento do meu próximo tópico.

Escreva nos comentários quais tarefas em duas pilhas você teve que resolver em entrevistas ou concursos.