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), push
permaneceriam os mesmos e pop
exigiriam simplesmente iteração para o último elemento e retorno. Nos dois casos, o push
seria O(1)
e o pop
seria 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.
Respostas:
Não há vantagem: este é um exercício puramente acadêmico.
Há 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
for
loops 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:
Isso permite que você use outras
Queue
implementações, se desejar, além de ocultar 2 métodosLinkedList
que podem contornar o espírito daQueue
interface. Isso incluiget(int)
epop()
(enquanto seu código é compilado, há um erro lógico, dadas as restrições de sua atribuição. Declarar suas variáveis como emQueue
vez deLinkedList
irá 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.Collections
ou 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.
fonte
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 é:
Na verdade, este é um ótimo exercício. Eu deveria fazer isso agora mesmo :)
fonte
push
,peek
e aspop
operações estão em O (1). O mesmo para uma pilha redimensionável baseada em matriz, exceto quepush
está 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.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.)
fonte
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).
fonte
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
Queue
interface possui umsize()
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ínimoadd()
eremove()
.Com essa implementação, é necessário contar primeiro o número de elementos transferindo-os para a segunda fila, transferir
n-1
elementos 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.
fonte
size()
método. No entanto, na ausência de umsize()
método O (1) , é trivial para a pilha acompanhar o próprio tamanho atual. Nada para interromper uma implementação de fila única.É 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.
fonte