Qual é o sentido de implementar uma pilha usando duas filas?

34

Tenho a seguinte pergunta de lição de casa:

Implemente os métodos de pilha push (x) e pop () usando duas filas.

Isso me parece estranho porque:

  • Uma pilha é uma fila (LIFO)
  • Não vejo por que você precisaria de duas filas para implementá-lo

Eu procurei em torno de:

e encontrou algumas soluções. Foi assim que acabei:

public class Stack<T> {
    LinkedList<T> q1 = new LinkedList<T>();
    LinkedList<T> q2 = new LinkedList<T>();

    public void push(T t) {
        q1.addFirst(t);
    }

    public T pop() {
        if (q1.isEmpty()) {
            throw new RuntimeException(
                "Can't pop from an empty stack!");
        }

        while(q1.size() > 1) {
            q2.addFirst( q1.removeLast() );
        }

        T popped = q1.pop();

        LinkedList<T> tempQ = q1;
        q1 = q2;
        q2 = tempQ;

        return popped;
    }
}

Mas não entendo qual é a vantagem de usar uma única fila; a versão de duas filas parece sem sentido complicada.

Digamos que escolhemos que os impulsos sejam os mais eficientes dos 2 (como fiz acima), pushpermaneceriam os mesmos e popexigiriam simplesmente iteração para o último elemento e retorno. Nos dois casos, o pushseria O(1)e o popseria O(n); mas a versão de fila única seria drasticamente mais simples. Deve exigir apenas um único loop for.

Estou esquecendo de algo? Qualquer visão aqui seria apreciada.

Carcinigenicado
fonte
17
Uma fila normalmente se refere a uma estrutura FIFO enquanto a pilha é uma estrutura LIFO. A interface para o LinkedList em Java é a de um deque (fila dupla) que permite o acesso FIFO e LIFO. Tente alterar a programação para a interface da fila em vez da implementação do LinkedList.
12
O problema mais comum é implementar uma fila usando duas pilhas. Você pode achar interessante o livro de Chris Okasaki sobre estruturas de dados puramente funcionais.
precisa
2
Construindo o que Eric disse, às vezes você pode se encontrar em uma linguagem baseada em pilha (como dc ou um autômato pushdown com duas pilhas (equivalente a uma máquina de turing porque, bem, você pode fazer mais)) onde pode se encontrar com várias pilhas, mas sem fila.
11
@MichaelT: Ou você também pode encontrar-se em execução em uma CPU baseada em pilha
slebetman
11
"Uma pilha é uma fila (LIFO)" ... uhm, uma fila é uma linha de espera. Como a linha para usar um banheiro público. As filas que você espera se comportam de uma maneira LIFO? Pare de usar o termo "fila LIFO", é absurdo.
precisa

Respostas:

44

Não há vantagem: este é um exercício puramente acadêmico.

muito tempo, quando eu era calouro na faculdade, tive um exercício semelhante 1 . O objetivo era ensinar aos alunos como usar a programação orientada a objetos para implementar algoritmos, em vez de escrever soluções iterativas usando forloops com contadores de loop. Em vez disso, combine e reutilize as estruturas de dados existentes para atingir seus objetivos.

Você nunca usará esse código no Real World TM . O que você precisa para tirar este exercício é como "pensar fora da caixa" e reutilizar o código.


Observe que você deve usar a interface java.util.Queue no seu código, em vez de usar a implementação diretamente:

Queue<T> q1 = new LinkedList<T>();
Queue<T> q2 = new LinkedList<T>();

Isso permite que você use outras Queueimplementações, se desejar, além de ocultar 2 métodos LinkedListque podem contornar o espírito da Queueinterface. Isso inclui get(int)e pop()(enquanto seu código é compilado, há um erro lógico, dadas as restrições de sua atribuição. Declarar suas variáveis ​​como em Queuevez de LinkedListirá revelá-las). Leitura relacionada: Noções básicas sobre “programação para uma interface” e Por que as interfaces são úteis?

1 Ainda me lembro: o exercício foi reverter um Stack usando apenas métodos na interface Stack e nenhum método utilitário em java.util.Collectionsou outras classes de utilitário "estático apenas". A solução correta envolve o uso de outras estruturas de dados como objetos de retenção temporários: você precisa conhecer as diferentes estruturas de dados, suas propriedades e como combiná-las para fazê-lo. Perdi a maior parte da minha classe CS101 que nunca havia programado antes.

2 Os métodos ainda estão lá, mas você não pode acessá-los sem conversão de tipo ou reflexão. Portanto, não é fácil usar esses métodos que não são da fila.

Comunidade
fonte
11
Obrigado. Eu acho que isso faz sentido. Também percebi que estou usando operações "ilegais" no código acima (empurrando para a frente de um FIFO), mas não acho que isso mude nada. Invertei todas as operações e ainda funciona como pretendido. Vou esperar um pouco antes de aceitar, pois não quero desencorajar outras pessoas a darem sugestões. Obrigado mesmo assim.
Carcigenicate
19

Não há vantagem. Você percebeu corretamente que o uso de filas para implementar uma pilha leva a uma complexidade de tempo horrível. Nenhum programador (competente) faria algo assim na "vida real".

Mas é possível. Você pode usar uma abstração para implementar outra e vice-versa. Uma pilha pode ser implementada em termos de duas filas e da mesma forma que você pode implementar uma fila em termos de duas pilhas. A vantagem deste exercício é:

  • você recapitula pilhas
  • você recapitulando filas
  • você se acostuma ao pensamento algorítmico
  • você aprende algoritmos relacionados à pilha
  • você começa a pensar em tradeoffs em algoritmos
  • ao perceber a equivalência de filas e pilhas, você conecta vários tópicos do seu curso
  • você ganha experiência prática em programação

Na verdade, este é um ótimo exercício. Eu deveria fazer isso agora mesmo :)

amon
fonte
3
@JohnKugelman Obrigado pela sua edição, mas eu realmente quis dizer "horrível complexidade de tempo". Para uma pilha baseada em lista vinculada push, peeke as popoperações estão em O (1). O mesmo para uma pilha redimensionável baseada em matriz, exceto que pushestá em O (1) amortizado, com O (n) no pior caso. Comparado com isso, uma pilha baseada em fila é muito inferior a O (n) push, O (1) pop e peek, ou alternativamente O (1) push, O (n) pop e peek.
amon
11
"horrível complexidade de tempo" e "imensamente inferior" não são exatamente corretas. A complexidade amortizada ainda é O (1) para push e pop. Existe uma pergunta divertida no TAOCP (vol1?) Sobre isso (basicamente você precisa mostrar que o número de vezes que um elemento pode alternar de uma pilha para outra é constante). O pior desempenho de uma operação é diferente, mas raramente ouço alguém falar sobre o desempenho de O (N) para enviar ArrayLists - não o número geralmente interessante.
Voo
5

Definitivamente, existe um propósito real de criar uma fila com duas pilhas. Se você usar estruturas de dados imutáveis ​​a partir de uma linguagem funcional, poderá enviar para uma pilha de itens pressionáveis ​​e extrair de uma lista de itens que podem aparecer. Os itens pop -able são criados quando todos os itens foram retirados, e a nova pilha pop -able é o reverso da pilha empurrável, onde a nova pilha empurrável está vazia. É eficiente.

Quanto a uma pilha feita de duas filas? Isso pode fazer sentido em um contexto em que você tem várias filas grandes e rápidas disponíveis. É definitivamente inútil como esse tipo de exercício Java. Mas pode fazer sentido se esses são canais ou filas de mensagens. (ou seja: N mensagens na fila, com uma operação O (1) para mover itens (N-1) na frente para uma nova fila.)

Roubar
fonte
Hmm .. isso me fez pensar sobre o uso de registradores de deslocamento como a base da computação e sobre a arquitetura da correia / moinho
slebetman
uau, a CPU Mill é realmente interessante. Uma "Máquina de filas", com certeza.
Rob
2

O exercício é desnecessariamente artificial do ponto de vista prático. O objetivo é forçar você a usar a interface da fila de maneira inteligente para implementar a pilha. Por exemplo, sua solução "Uma fila" exige que você itere sobre a fila para obter o último valor de entrada para a operação "pop" da pilha. No entanto, uma estrutura de dados da fila não permite iterar sobre os valores; você está restrito a acessá-los no FIFO (primeiro a entrar, primeiro a sair).

Destruktor
fonte
2

Como outros já observaram: não há vantagem no mundo real.

De qualquer forma, uma resposta para a segunda parte da sua pergunta, por que não usar apenas uma fila, está além do Java.

Em Java, mesmo a Queueinterface possui um size()método e todas as implementações padrão desse método são O (1).

Isso não é necessariamente verdade para a lista vinculada ingênua / canônica como um programador C / C ++ implementaria, o que manteria os ponteiros para o primeiro e o último elemento e cada elemento um ponteiro para o próximo elemento.

Nesse caso, size()é O (n) e deve ser evitado em loops. Ou a implementação é opaca e fornece apenas o mínimo add()e remove().

Com essa implementação, é necessário contar primeiro o número de elementos transferindo-os para a segunda fila, transferir n-1elementos de volta para a primeira fila e retornar o elemento restante.

Dito isto, provavelmente não seria algo assim se você mora na região de Java.

Thraidh
fonte
Bom ponto sobre o size()método. No entanto, na ausência de um size()método O (1) , é trivial para a pilha acompanhar o próprio tamanho atual. Nada para interromper uma implementação de fila única.
#
Tudo depende da implementação. Se você tiver uma fila, implementada apenas com ponteiros de encaminhamento e ponteiros para o primeiro e o último elemento, ainda poderá escrever e o algoritmo que remove um elemento, salva em uma variável local, adiciona o elemento anteriormente nessa variável à mesma fila até o O primeiro elemento é visto novamente. Isso só funciona se você puder identificar exclusivamente um elemento (por exemplo, via ponteiro) e não apenas algo com o mesmo valor. O (n) e usa apenas add () e remove (). De qualquer forma, é mais fácil otimizar, encontrar um motivo para fazer isso, exceto pensar em algoritmos.
Thraidh
0

É difícil imaginar um uso para essa implementação, é verdade. Mas a maior parte do objetivo é provar que isso pode ser feito .

Em termos de usos reais para essas coisas, no entanto, posso pensar em duas. Um uso para isso é implementar sistemas em ambientes restritos que não foram projetados para isso : por exemplo, os blocos redstone do Minecraft acabam representando um sistema completo de Turing, que as pessoas usaram para implementar circuitos lógicos e até CPUs inteiras. Nos primeiros dias dos jogos guiados por script, muitos dos primeiros robôs de jogos também foram implementados dessa maneira.

Mas você também pode aplicar esse princípio ao contrário, garantindo que algo não seja possível em um sistema quando você não deseja que seja . Isso pode surgir em contextos de segurança: por exemplo, sistemas de configuração poderosos podem ser um ativo, mas ainda há graus de poder que você pode não dar aos usuários. Isso restringe o que você pode permitir que a linguagem de configuração faça, para que não seja subvertida por um invasor, mas, nesse caso, é isso que você deseja.

The Spooniest
fonte