Como implementar uma fila com três pilhas?

136

Encontrei essa questão em um livro de algoritmos ( Algorithms, 4th Edition, de Robert Sedgewick e Kevin Wayne).

Fila com três pilhas. Implemente uma fila com três pilhas para que cada operação da fila tome um número constante (no pior caso) de operações da pilha. Atenção: alto grau de dificuldade.

Eu sei como fazer uma fila com 2 pilhas, mas não consigo encontrar a solução com 3 pilhas. Qualquer ideia ?

(Ah, e isso não é lição de casa :))

DuoSRX
fonte
30
Eu acho que é uma variante da Tower of Hanoi .
Gumbo #
14
@ Jason: Essa pergunta não é uma duplicata, pois pede O (1) tempo amortizado, enquanto esta pede O (1) pior caso para cada operação. A solução de duas pilhas do DuoSRX já é O (1) tempo amortizado por operação.
interjay
15
O autor certamente não estava brincando quando disse "Atenção: alto grau de dificuldade".
BoltClock
9
@ Gumbo, infelizmente, a complexidade de tempo da Torre de Hanói não é nem de longe constante!
prusswan
12
Nota: A pergunta no texto foi atualizada para isso: Implemente uma fila com um número constante de pilhas [não "3"] para que cada operação de fila tome um número constante (no pior caso) de operações de pilha. Atenção: alto grau de dificuldade. ( algs4.cs.princeton.edu/13stacks - Seção 1.3.43). Parece que o Prof. Sedgewick aceitou o desafio original.
Mark Peters

Respostas:

44

RESUMO

  • O algoritmo O (1) é conhecido por 6 pilhas
  • O algoritmo O (1) é conhecido por três pilhas, mas usando avaliação lenta, que na prática corresponde a ter estruturas de dados internas extras, portanto não constitui uma solução
  • Pessoas próximas a Sedgewick confirmaram que não têm conhecimento de uma solução de 3 pilhas dentro de todas as restrições da pergunta original

DETALHES

Há duas implementações por trás deste link: http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html

Um deles é O (1) com três pilhas, mas utiliza execução lenta, o que na prática cria estruturas de dados intermediárias extras (fechamentos).

Outro deles é O (1), mas usa SEIS pilhas. No entanto, funciona sem execução lenta.

ATUALIZAÇÃO: O artigo de Okasaki está aqui: http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps e parece que ele realmente usa apenas 2 pilhas para a versão O (1) que tem uma avaliação lenta. O problema é que ele é realmente baseado em avaliações preguiçosas. A questão é se ele pode ser traduzido para um algoritmo de 3 pilhas sem avaliação lenta.

ATUALIZAÇÃO: Outro algoritmo relacionado é descrito no artigo "Stacks versus Deques", de Holger Petersen, publicado na 7ª Conferência Anual de Computação e Combinatória. Você pode encontrar o artigo no Google Livros. Verifique as páginas 225-226. Mas o algoritmo não é realmente uma simulação em tempo real, é uma simulação em tempo linear de uma fila dupla em três pilhas.

gusbro: "Como o @Leonel disse há alguns dias, pensei que seria justo verificar com o Prof. Sedgewick se ele sabia uma solução ou se havia algum erro. Então, escrevi para ele. Acabei de receber uma resposta (embora não de ele mesmo, mas de um colega de Princeton), então eu gostaria de compartilhar com todos vocês. Ele basicamente disse que não conhecia algoritmos usando três pilhas E as outras restrições impostas (como não usar avaliação lenta). 6 pilhas, como já sabemos, olhando para as respostas aqui. Acho que a pergunta ainda está aberta para encontrar um algoritmo (ou provar que um não pode ser encontrado). "

antti.huima
fonte
Eu apenas voei sobre os papéis e programas no seu link. Mas se eu vejo direito, eles não usam pilhas, eles usam listas como tipo básico. E esp. nessas listas são construídas com cabeçalho e resto, portanto, basicamente se parece com a minha solução (e acho que não está certo).
Flr6 /
1
Olá, as implementações estão em uma linguagem funcional em que as listas correspondem a pilhas, desde que os ponteiros não sejam compartilhados e não; a versão de seis pilhas pode ser realmente implementada usando seis pilhas "simples". O problema com a versão de duas / três pilhas é que ela usa estruturas de dados ocultas (fechamentos).
Antti Huima 06/04
Tem certeza de que a solução de seis pilhas não compartilha ponteiros? Em rotate, parece que a frontlista é atribuída a ambos oldfronte f, e estes são modificados separadamente.
interjay
14
O material de origem em algs4.cs.princeton.edu/13stacks foi alterado: 43. Implemente uma fila com um número constante de [não "3"] pilhas para que cada operação de fila tenha um número constante (no pior caso) de pilha operações. Atenção: alto grau de dificuldade. O título do desafio ainda diz "Fila com três pilhas", no entanto :-).
Mark Peters
3
@AnttiHuima O link de seis pilhas está morto, você sabe se isso existe em algum lugar?
Quentin Pradet
12

Ok, isso é realmente difícil, e a única solução que eu consegui me lembrar é a solução Kirks para o teste Kobayashi Maru (de alguma forma enganada): A idéia é que usamos pilhas de pilhas (e usamos isso para modelar uma lista ) Eu chamo as operações en / dequeue e push e pop, então obtemos:

queue.new() : Stack1 = Stack.new(<Stack>);  
              Stack2 = Stack1;  

enqueue(element): Stack3 = Stack.new(<TypeOf(element)>); 
                  Stack3.push(element); 
                  Stack2.push(Stack3);
                  Stack3 = Stack.new(<Stack>);
                  Stack2.push(Stack3);
                  Stack2 = Stack3;                       

dequeue(): Stack3 = Stack1.pop(); 
           Stack1 = Stack1.pop();
           dequeue() = Stack1.pop()
           Stack1 = Stack3;

isEmtpy(): Stack1.isEmpty();

(StackX = StackY não é uma cópia do conteúdo, apenas uma cópia da referência. É apenas para descrevê-lo facilmente. Você também pode usar uma matriz de 3 pilhas e acessá-las via índice; aí, você apenas alteraria o valor da variável index ) Tudo está em O (1) em termos de operação de pilha.

E sim, eu sei que é discutível, porque implicamos mais de três pilhas, mas talvez isso dê a outras pessoas boas idéias.

EDIT: Exemplo de explicação:

 | | | |3| | | |
 | | | |_| | | |
 | | |_____| | |
 | |         | |
 | |   |2|   | |
 | |   |_|   | |
 | |_________| |
 |             |
 |     |1|     |
 |     |_|     |
 |_____________|

Eu tentei aqui com um pouco de arte ASCII para mostrar o Stack1.

Cada elemento é agrupado em uma única pilha de elementos (portanto, temos apenas uma pilha segura de pilhas).

Você vê que, para remover, primeiro exibimos o primeiro elemento (a pilha que contém os elementos 1 e 2). Em seguida, pop o próximo elemento e desembrulhe lá o 1. Depois dizemos que a primeira pilha exibida agora é o nosso novo Stack1. Para falar um pouco mais funcional - estas são listas implementadas por pilhas de 2 elementos em que o elemento superior é cdr e o primeiro / abaixo do elemento superior é car . Os outros 2 estão ajudando pilhas.

O mais complicado é a inserção, pois você precisa de alguma forma mergulhar profundamente nas pilhas aninhadas para adicionar outro elemento. É por isso que o Stack2 está lá. Stack2 é sempre a pilha mais interna. A adição é apenas inserir um elemento e depois inserir um novo Stack2 (e é por isso que não podemos tocar no Stack2 em nossa operação de desenfileiramento).

flolo
fonte
Gostaria de explicar como isso funciona? Talvez traçar pressionando 'A', 'B', 'C', 'D' e depois aparecer 4 vezes?
MAK
1
@ Iceman: No Stack2 está certo. Eles não são perdidos, porque a Pilha sempre se refere à pilha mais interna da Pilha1, portanto, eles ainda estão implícitos na Pilha1.
Flr6
3
Concordo que está enganando :-). Não são 3 pilhas, são 3 referências de pilha. Mas uma leitura agradável.
Mark Peters
1
É um esquema inteligente, mas se eu entendi direito, acabará precisando de n pilhas quando houver n elementos empurrados para a fila. A pergunta pede exatamente 3 pilhas.
MAK
2
@ MAK: Eu sei, é por isso que disse explicitamente que isso é trapaça (eu até gastei reputação em uma recompensa porque também tenho curiosidade pela solução real). Mas pelo menos o comentário prusswan pode ser respondido: O número de pilhas é importante, porque minha solução é realmente válida, quando você pode usar o quanto quiser.
Flr6 /
4

Vou tentar uma prova para mostrar que isso não pode ser feito.


Suponha que exista uma fila Q que seja simulada por 3 pilhas, A, B e C.

Asserções

  • ASRT0: = Além disso, suponha que Q possa simular operações {fila, desenfileiramento} em O (1). Isso significa que existe uma sequência específica de push / pops de pilha para cada operação de fila / desenfileiramento a ser simulada.

  • Sem perda de generalidade, assuma que as operações da fila são determinísticas.

Permita que os elementos enfileirados em Q sejam numerados 1, 2, ..., com base em sua ordem de fila, com o primeiro elemento enfileirado em Q definido como 1, o segundo como 2 e assim por diante.

Definir

  • Q(0) := O estado de Q quando existem 0 elementos em Q (e, portanto, 0 elementos em A, B e C)
  • Q(1) := O estado de Q (e A, B e C) após uma operação na fila em Q(0)
  • Q(n) := O estado de Q (e A, B e C) após n operações na fila em Q(0)

Definir

  • |Q(n)| :=o número de elementos em Q(n)(portanto|Q(n)| = n )
  • A(n) := o estado da pilha A quando o estado de Q é Q(n)
  • |A(n)| := o número de elementos em A(n)

E definições semelhantes para as pilhas B e C.

Trivialmente,

|Q(n)| = |A(n)| + |B(n)| + |C(n)|

---

|Q(n)| é obviamente ilimitado em n.

Portanto, pelo menos um de |A(n)|, |B(n)|ou|C(n)| é ilimitado em n.

WLOG1, suponha que a pilha A seja ilimitada e as pilhas B e C sejam limitadas.

Defina * B_u :=um limite superior de B * C_u :=um limite superior de C *K := B_u + C_u + 1

WLOG2, para um n tal que |A(n)| > K, selecione K elementos de Q(n). Suponha que um desses elementos esteja em A(n + x), para todos x >= 0, ou seja, o elemento esteja sempre na pilha A, não importa quantas operações de fila sejam realizadas.

  • X := esse elemento

Então podemos definir

  • Abv(n) :=o número de itens na pilha A(n)que está acima de X
  • Blo(n) :=o número de elementos na pilha A(n)abaixo de X

    | A (n) | = Abv (n) + Blo (n)

ASRT1 :=O número de pops necessários para remover a fila de X Q(n)é pelo menosAbv(n)

De ( ASRT0) e ( ASRT1),ASRT2 := Abv(n) deve ser delimitado.

Se Abv(n)for ilimitado, se forem necessários 20 desenfileiramentos para desenfileirar X de Q(n), será necessário pelo menosAbv(n)/20 pops. O que é ilimitado. 20 pode ser qualquer constante.

Portanto,

ASRT3 := Blo(n) = |A(n)| - Abv(n)

deve ser ilimitado.


WLOG3, podemos selecionar os elementos K na parte inferior de A(n)e um deles é A(n + x)para todosx >= 0

X(n) := esse elemento, para qualquer dado n

ASRT4 := Abv(n) >= |A(n)| - K

Sempre que um elemento é enfileirado em Q(n)...

WLOG4, suponha que B e C já estejam preenchidos nos limites superiores. Suponha que o limite superior dos elementos acima X(n)tenha sido atingido. Então, um novo elemento entra em A.

WLOG5, suponha que, como resultado, o novo elemento deve entrar abaixo X(n).

ASRT5 := O número de pops necessários para colocar um elemento abaixo X(n) >= Abv(X(n))

De (ASRT4), Abv(n)é ilimitado em n.

Portanto, o número de pops necessários para colocar um elemento abaixo X(n)é ilimitado.


Isso contradiz ASRT1, portanto, não é possível simular uma O(1)fila com 3 pilhas.


Ou seja,

Pelo menos 1 pilha deve ser ilimitada.

Para um elemento que permanece nessa pilha, o número de elementos acima dele deve ser limitado ou a operação de desenfileiramento para remover esse elemento será ilimitada.

No entanto, se o número de elementos acima dele for limitado, ele atingirá um limite. Em algum momento, um novo elemento deve entrar abaixo dele.

Como sempre podemos escolher o elemento antigo dentre um dos poucos elementos mais baixos dessa pilha, pode haver um número ilimitado de elementos acima dele (com base no tamanho ilimitado da pilha ilimitada).

Para inserir um novo elemento abaixo dele, como há um número ilimitado de elementos acima dele, é necessário um número ilimitado de pops para colocar o novo elemento abaixo dele.

E assim a contradição.


Existem 5 declarações WLOG (sem perda de generalidade). Em certo sentido, eles podem ser intuitivamente entendidos como verdadeiros (mas, como são 5, pode levar algum tempo). A prova formal de que nenhuma generalidade é perdida pode ser obtida, mas é extremamente longa. Eles são omitidos.

Admito que essa omissão possa deixar as declarações do WLOG em questão. Com a paranóia de um programador quanto a erros, verifique as instruções do WLOG, se desejar.

A terceira pilha também é irrelevante. O que importa é que há um conjunto de pilhas limitadas e um conjunto de pilhas ilimitadas. O mínimo necessário para um exemplo é 2 pilhas. O número de pilhas deve ser, obviamente, finito.

Por fim, se eu estiver certo de que não há provas, deve haver uma prova indutiva mais fácil disponível. Provavelmente, com base no que acontece após cada fila (acompanhe como isso afeta o pior caso de desenfileiramento, considerando o conjunto de todos os elementos na fila).

Dingfeng Quek
fonte
2
Acho que a prova funciona para essas suposições - mas não tenho certeza de que todas as pilhas precisam estar vazias para a fila ficar vazia ou que a soma dos tamanhos das pilhas deve ser igual ao tamanho da fila.
Mikeb
3
"WLOG1, suponha que a pilha A seja ilimitada e as pilhas B e C sejam limitadas." Você não pode assumir que algumas das pilhas são limitadas, pois isso as tornaria inúteis (elas seriam iguais ao armazenamento adicional O (1)).
interjay
3
Às vezes, as coisas triviais não são tão triviais: | Q | = | A | + | B | + | C | está correto, se você assumir que, para cada entrada em Q, você adiciona uma exata em A, B ou C, mas pode ser que algum deles seja um algoritmo, que sempre adiciona um elemento duas vezes a duas pilhas ou até as três. E se funcionar dessa maneira, você WLOG1 não aguenta mais (por exemplo, imagine C uma cópia de A (não que isso faça algum sentido, mas talvez exista um algoritmo, com uma ordem diferente ou qualquer outra coisa ...)
flolo
@flolo e @mikeb: Vocês dois estão certos. | Q (n) | deve ser definido como | A (n) | + | B (n) | + | C (n) |. E então | Q (n) | > = n. Posteriormente, a prova funcionaria com n e observe que, enquanto | Q (n) | maior, a conclusão se aplica.
Dingfeng Quek
@interjay: Você pode ter 3 pilhas ilimitadas e sem pilhas limitadas. Em vez de "B_u + C_u + 1", a prova pode apenas usar "1". Basicamente, a expressão representa "soma do limite superior em pilhas delimitadas + 1", portanto, o número de pilhas delimitadas não importa.
Dingfeng Quek
3

Nota: Isso pretende ser um comentário para a implementação funcional de filas em tempo real (pior caso de tempo constante) com listas vinculadas individualmente. Não posso adicionar comentários devido à reputação, mas será bom se alguém puder mudar isso para um comentário anexado à resposta por antti.huima. Então, novamente, é um pouco longo para um comentário.

@ antti.huima: Listas vinculadas não são iguais a uma pilha.

  • s1 = (1 2 3 4) --- uma lista vinculada com 4 nós, cada um apontando para o da direita e mantendo os valores 1, 2, 3 e 4

  • s2 = popped (s1) --- s2 agora (2 3 4)

Nesse ponto, s2 é equivalente a popped (s1), que se comporta como uma pilha. No entanto, s1 ainda está disponível para referência!

  • s3 = popped (popped (s1)) --- s3 é (3 4)

Ainda podemos espiar s1 para obter 1, enquanto em uma implementação de pilha adequada, o elemento 1 desapareceu de s1!

O que isto significa?

  • s1 é a referência ao topo da pilha
  • s2 é a referência ao segundo elemento da pilha
  • s3 é a referência ao terceiro ...

As listas vinculadas adicionais criadas agora servem cada uma como referência / ponteiro! Um número finito de pilhas não pode fazer isso.

Pelo que vejo nos documentos / código, todos os algoritmos fazem uso dessa propriedade de listas vinculadas para reter referências.

Edit: Estou me referindo apenas aos algoritmos de lista vinculada 2 e 3 que fazem uso dessa propriedade de listas vinculadas, como as li primeiro (elas pareciam mais simples). Isso não pretende mostrar que eles são ou não são aplicáveis, apenas para explicar que as listas vinculadas não são necessariamente idênticas. Vou ler aquele com 6 quando estiver livre. @ Welbog: Obrigado pela correção.


A preguiça também pode simular a funcionalidade do ponteiro de maneiras semelhantes.


O uso da lista vinculada resolve um problema diferente. Essa estratégia pode ser usada para implementar filas em tempo real no Lisp (ou pelo menos Lisps que insistem em criar tudo, a partir de listas vinculadas): Consulte "Operações da fila em tempo real no Pure Lisp" (vinculado aos links do antti.huima). Também é uma boa maneira de projetar listas imutáveis ​​com tempo de operação O (1) e estruturas compartilhadas (imutáveis).

Dingfeng Quek
fonte
1
Não consigo falar com outros algoritmos na resposta de antti, mas a solução de tempo constante de seis pilhas ( eecs.usma.edu/webs/people/okasaki/jfp95/queue.hm.sml ) não usa essa propriedade de listas , como eu o reimplementei em Java usando java.util.Stackobjetos. O único local em que esse recurso é usado é uma otimização que permite que pilhas imutáveis ​​sejam "duplicadas" em tempo constante, que pilhas Java básicas não podem fazer (mas que podem ser implementadas em Java), pois são estruturas mutáveis.
precisa saber é o seguinte
Se é uma otimização que não reduz a complexidade computacional, não deve afetar a conclusão. Fico feliz em finalmente ter uma solução, agora para verificar: mas eu não gosto de ler SML. Se importa de compartilhar seu código java? (:
Dingfeng Quek
Não é uma solução final, pois usa seis pilhas em vez de três, infelizmente. No entanto, pode ser possível provar que seis pilhas é uma solução mínima ...
Welbog
@Welbog! Você pode compartilhar sua implementação de 6 pilhas? :) Seria legal vê-lo :)
Antti Huima 08/04
1

Você pode fazer isso em tempo constante amortizado com duas pilhas:

------------- --------------
            | |
------------- --------------

Adicionar O(1)e remover é O(1)se o lado que você deseja retirar não estiver vazio eO(n) caso contrário (divida a outra pilha em duas).

O truque é ver que a O(n)operação só será feita toda O(n)vez (se você dividir, por exemplo, ao meio). Portanto, o tempo médio para uma operação éO(1)+O(n)/O(n) = O(1) .

Embora isso possa parecer um problema, se você estiver usando uma linguagem imperativa com uma pilha baseada em array (mais rápida), você só terá amortizado o tempo constante de qualquer maneira.

Thomas Ahle
fonte
Quanto à pergunta original: dividir uma pilha realmente requer uma pilha intermediária extra. Pode ser por isso que sua tarefa incluiu três pilhas.
Thomas Ahle