Diferença entre pilha e fila

Contente

Gráfico de comparação
Definição de Pilha
Exemplo
Definição de Fila
Exemplo
Implementação de pilha
Implementação de fila
Operações na pilha
Operações em uma fila
Aplicações da pilha
Aplicações da fila
Conclusão

Stack e Queue são estruturas de dados não primitivas. As principais diferenças entre pilha e fila são que a pilha usa o método LIFO (último a entrar, primeiro a sair) para acessar e adicionar elementos de dados, enquanto a Fila usa o método FIFO (primeiro a entrar, primeiro a sair) para acessar e adicionar elementos de dados.

A pilha possui apenas uma extremidade aberta para empurrar e exibir os elementos de dados, por outro lado, a fila possui ambas as extremidades abertas para enfileirar e desenfileirar os elementos de dados.

Pilha e fila são as estruturas de dados usadas para armazenar elementos de dados e são realmente baseadas em algum equivalente do mundo real. Por exemplo, a pilha é uma pilha de CDs onde você pode retirar e colocar o CD na parte superior da pilha de CDs. Da mesma forma, a fila é uma fila para bilhetes de teatro em que a pessoa que está em primeiro lugar, ou seja, a frente da fila, será atendida primeiro e a nova pessoa que chegar aparecerá na parte de trás da fila (extremidade traseira da fila).

Gráfico de comparação
Definição
Principais diferenças
Implementação
Operações
Aplicações
Conclusão

Gráfico de comparação


Base para comparação	Pilha	Fila
Princípio de trabalho	LIFO (Último a entrar, Primeiro a sair)	FIFO (Primeiro a entrar, Primeiro a sair)
Estrutura	Mesmo fim é usado para inserir e excluir elementos.	Uma extremidade é usada para inserção, isto é, extremidade traseira e outra extremidade é usada para exclusão de elementos, isto é, extremidade dianteira.
Número de ponteiros usados	1	Dois (no caso de fila simples)
Operações realizadas	Push and Pop	Enfileirar e desenfileirar
Exame da condição vazia	Superior == -1	Frente == -1 \|\| Frente == Traseira + 1
Exame da condição completa	Superior == Máximo - 1	Traseira == Máx - 1
Variantes	Não possui variantes.	Possui variantes como fila circular, fila prioritária e fila duplamente encerrada.
Implementação	Mais simples	Comparativamente complexo

Definição de Pilha

Uma pilha é uma estrutura de dados linear não primitiva. É uma lista ordenada em que o novo item é adicionado e o elemento existente é excluído de apenas uma extremidade, chamada como o topo da pilha (TOS). Como toda a exclusão e inserção em uma pilha é feita da parte superior da pilha, o último elemento adicionado será o primeiro a ser removido da pilha. Essa é a razão pela qual a pilha é chamada do tipo LIFO (Last-in-First-Out-Out).

Observe que o elemento freqüentemente acessado na pilha é o elemento superior, enquanto o último elemento disponível está na parte inferior da pilha.

Exemplo

Alguns de vocês podem comer biscoitos (ou Poppins). Se você presumir, apenas um lado da tampa está rasgado e os biscoitos são retirados um a um. É o que chamamos de estalar e, da mesma forma, se você quiser preservar alguns biscoitos por algum tempo depois, os colocará de volta na embalagem com o mesmo fim rasgado que é chamado de empurrar.

Definição de Fila

Uma fila é uma estrutura de dados linear que vem na categoria do tipo não primitivo. É uma coleção de tipos semelhantes de elementos. A adição de novos elementos ocorre em uma extremidade chamada extremidade traseira. Da mesma forma, a exclusão dos elementos existentes ocorre na outra extremidade, chamada Front-end, e é logicamente um tipo de lista Primeiro a entrar, primeiro a sair (FIFO).

Exemplo

No nosso dia-a-dia, encontramos muitas situações em que esperamos pelo serviço desejado, lá temos que entrar na fila de espera para que nossa vez seja atendida. Essa fila de espera pode ser pensada como uma fila.

A pilha segue o mecanismo LIFO, por outro lado, a fila segue o mecanismo FIFO para adicionar e remover elementos.
Em uma pilha, o mesmo fim é usado para inserir e excluir os elementos. Pelo contrário, duas extremidades diferentes são usadas na fila para inserir e excluir os elementos.
Como a pilha tem apenas uma extremidade aberta, esse é o motivo do uso de apenas um ponteiro para se referir à parte superior da pilha. Mas a fila usa dois ponteiros para fazer referência à frente e à extremidade traseira da fila.
A pilha executa duas operações conhecidas como push e pop enquanto na fila é conhecida como enfileiramento e desenfileiramento.
A implementação da pilha é mais fácil, enquanto a implementação da fila é complicada.
A fila possui variantes como fila circular, fila prioritária, fila duplamente terminada etc. Por outro lado, a pilha não possui variantes.

Implementação de pilha

A pilha pode ser aplicada de duas maneiras:

Implementação estática usa matrizes para criar uma pilha. A implementação estática é, no entanto, uma técnica sem esforço, mas não é uma maneira flexível de criação, pois a declaração do tamanho da pilha precisa ser feita durante o design do programa, depois que o tamanho não pode ser variado. Além disso, a implementação estática não é muito eficiente em relação à utilização da memória. Como uma matriz (para implementar a pilha) é declarada antes do início da operação (no tempo de design do programa). Agora, se o número de elementos a serem classificados for muito menor na pilha, a memória alocada estaticamente será desperdiçada. Por outro lado, se houver mais número de elementos a serem armazenados na pilha, não poderemos alterar o tamanho da matriz para aumentar sua capacidade, para que ela possa acomodar novos elementos.
Implementação dinâmica também é chamado de representação de lista vinculada e usa ponteiros para implementar o tipo de pilha da estrutura de dados.

Implementação de fila

A fila pode ser implementada de duas maneiras:

Implementação estática: Se uma fila for implementada usando matrizes, o número exato de elementos que queremos armazenar na fila deve ser garantido antes, porque o tamanho da matriz precisa ser declarado no tempo de design ou antes do início do processamento. Nesse caso, o início da matriz se tornará a frente da fila e o último local da matriz atuará como a parte traseira da fila. A relação a seguir fornece todos os elementos existentes na fila quando implementados usando matrizes:
frente - traseira + 1
Se "traseira <frente", então não haverá elemento na fila ou a fila estará sempre vazia.
Implementação dinâmica: Implementando filas usando ponteiros, a principal desvantagem é que um nó em uma representação vinculada consome mais espaço de memória que um elemento correspondente na representação da matriz. Como existem pelo menos dois campos em cada nó, um para o campo de dados e outro para armazenar o endereço do próximo nó, enquanto na representação vinculada apenas o campo de dados existe. O mérito de usar a representação vinculada se torna óbvio quando é necessário inserir ou excluir um elemento no meio de um grupo de outros elementos.

Operações na pilha

As operações básicas que podem ser operadas na pilha são as seguintes:

EMPURRAR: quando um novo elemento é adicionado ao topo da pilha é conhecido como operação PUSH. Pressionar um elemento na pilha chama a adição do elemento, pois o novo elemento será inserido na parte superior. Após cada operação de envio, a parte superior é aumentada em um. Se a matriz estiver cheia e nenhum elemento novo puder ser adicionado, ela será denominada condição STACK-FULL ou STACK OVERFLOW. OPERAÇÃO DE PRESSÃO - função em C:
Considerando que a pilha é declarada como
pilha int, superior = -1;
impulso vazio ()
{
item int;
if (top <4)
{
f ("Digite o número");
digitalizar ("% d", & item);
topo = topo + 1;
pilha = item;
}
outro
{
f ("A pilha está cheia");
}
}
POP: Quando um elemento é excluído da parte superior da pilha, ele é conhecido como operação POP. A pilha é diminuída em um, após cada operação pop. Se não houver nenhum elemento na pilha e o pop for executado, isso resultará na condição STACK UNDERFLOW, o que significa que sua pilha está vazia. OPERAÇÃO POP - funções em C:
Considerando que a pilha é declarada como
pilha int, superior = -1;
pop vazio ()
{
item int;
if (superior> = 4)
{
item = pilha;
top = top - 1;
f ("Número excluído é =% d", item);
}
outro
{
f ("A pilha está vazia");
}
}

Operações em uma fila

As operações básicas que podem ser executadas na fila são:

Enfileirar: Para inserir um elemento em uma fila. Função de operação de enfileiramento em C:
A fila é declarada como
fila de int, Frente = -1 e traseira = -1;
void add ()
{
item int;
se (traseira <4)
{
f ("Digite o número");
digitalizar ("% d", & item);
if (frente == -1)
{
frente = 0;
traseira = 0;
}
outro
{
traseira = traseira + 1;
}
fila = item;
}
outro
{
f ("A fila está cheia");
}
}
Retirar da fila: Para excluir um elemento da fila.Função de operação de enfileiramento em C:
A fila é declarada como
fila de int, Frente = -1 e traseira = -1;
cancelar nulo ()
{
item int;
if (frente! = -1)
{
item = fila;
if (frente == traseira)
{
frente = -1;
traseira = -1;
}
outro
{
frente = frente + 1;
f ("Número excluído é =% d", item);
}
}
outro
{
f ("A fila está vazia");
}
}

Aplicações da pilha

Analisando em um compilador.
Máquina Virtual JAVA.
Desfazer em um processador de texto.
Botão Voltar em um navegador da Web.
Linguagem PostScript para outros.
Implementando chamadas de função em um compilador.

Aplicações da fila

Buffers de dados
Transferência de dados assíncrona (E / S de arquivo, tubos, soquetes).
Alocando solicitações em um recurso compartilhado (er, processador).
Análise de tráfego.
Determine o número de caixas a ter em um supermercado.

Conclusão

Stack e Queue são estruturas de dados lineares que diferem em certos aspectos, como mecanismo de trabalho, estrutura, implementação, variantes, mas ambos são usados para armazenar os elementos na lista e executar operações na lista, como adição e exclusão de elementos. Embora existam algumas limitações da fila simples, que é recuperada usando outros tipos de fila.