A pilha tem apenas uma extremidade aberta para empurrar e estourar os elementos de dados. Por outro lado, a fila tem as duas extremidades abertas para enfileiramento e remoção de fila dos elementos de dados.
Pilha e fila são as estruturas de dados usadas para armazenar elementos de dados e são, na verdade, baseadas em algum equivalente no mundo real. Por exemplo, a pilha é uma pilha de CDs onde você pode tirar e colocar em CD no topo da pilha de CDs. Da mesma forma, A fila é uma fila para ingressos de teatro, onde a pessoa que está em primeiro lugar, ou seja, na frente da fila, será veiculada primeiro e a nova pessoa que chegar aparecerá na parte de trás da fila (extremidade traseira da fila).
Gráfico de comparação
| Base para comparação | Pilha | Fila |
|---|---|---|
| Princípio de trabalho | LIFO (último a entrar primeiro) | FIFO (primeiro a sair primeiro) |
| Estrutura | A mesma extremidade é usada para inserir e excluir elementos. | Uma extremidade é usada para inserção, isto é, extremidade traseira e outra extremidade é usada para exclusão de elementos, isto é, front end. |
| Número de ponteiros usados | 1 | Dois (no caso de fila simples) |
| Operações executadas | Empurrar e Pop | Enfileirar e desencaixar |
| Exame de condição vazia | Superior == -1 | Frente == -1 || Frente == Traseira + 1 |
| Exame da condição completa | Topo == Max - 1 | Traseira == Max - 1 |
| Variantes | Não tem variantes. | Tem variantes como fila circular, fila de prioridade, fila duplamente terminada. |
| 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, chamado como o topo da pilha (TOS). Como toda a exclusão e inserção em uma pilha é feita a partir do topo da pilha, o último elemento adicionado será o primeiro a ser removido da pilha. Essa é a razão pela qual a pilha é chamada de tipo de lista Last-in-First-out (LIFO).
Observe que o elemento geralmente acessado na pilha é o elemento mais alto, enquanto o último elemento disponível está no final da pilha.
Exemplo
Alguns de vocês podem comer biscoitos (ou Poppins). Se você assumir, apenas um lado da capa está rasgado e biscoitos são retirados um a um. Isto é o que é chamado de estourar, e da mesma forma, se você quiser preservar alguns biscoitos por algum tempo depois, você os colocará de volta no pacote através da mesma extremidade rasgada chamada push.
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 de front-end, e é logicamente um tipo de lista First in first out (FIFO).
Exemplo
Em nosso dia a dia nos deparamos com muitas situações em que saímos para esperar o serviço desejado, lá temos que entrar na fila de espera para a nossa vez de ser atendidos. Essa fila de espera pode ser considerada como uma fila.
Principais diferenças entre pilha e fila
- Stack segue o mecanismo LIFO, por outro lado A fila segue o mecanismo FIFO para adicionar e remover elementos.
- Em uma pilha, a mesma extremidade é usada 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, essa é a razão para usar apenas um ponteiro para se referir ao topo da pilha. Mas a fila usa dois ponteiros para se referir à frente e à extremidade traseira da fila.
- Stack executa duas operações conhecidas como push e pop enquanto que na Fila é conhecido como enfileiramento e desenfileiramento.
- A implementação de pilha é mais fácil, enquanto a implementação de fila é complicada.
- A fila tem variantes como fila circular, fila de prioridade, fila com dupla duplicação, etc. Em contraste, a pilha não tem variantes.
Implementação de pilha
A pilha pode ser aplicada de duas maneiras:
- A implementação estática usa matrizes para criar uma pilha. A implementação estática é, entretanto, uma técnica sem esforço, mas não é uma forma flexível de criação, pois a declaração do tamanho da pilha deve ser feita durante o projeto do programa, depois disso o tamanho não pode ser alterado. Além disso, a implementação estática não é muito eficiente em relação à utilização da memória. Já que uma matriz (para implementar 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 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.
- A implementação dinâmica também é chamada 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 é implementada usando arrays, o número exato de elementos que queremos armazenar na fila deve ser assegurado antes, porque o tamanho da matriz deve ser declarado em 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 “rear <front” então não haverá nenhum 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 do que um elemento correspondente na representação da matriz. Já que há 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 que no campo de dados somente de representação vinculada está lá. O mérito de usar a representação vinculada torna-se ó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:
- PUSH : quando um novo elemento é adicionado ao topo da pilha é conhecido como operação PUSH. Empurrar um elemento na pilha chama a adição do elemento, já que o novo elemento será inserido na parte superior. Após cada operação de envio, o topo é aumentado em um. Se a matriz estiver cheia e nenhum elemento novo puder ser adicionado, ela será chamada de condição STACK-FULL ou STACK OVERFLOW. PUSH OPERATION - função em C:
Considerando que a pilha é declarada comoint stack [5], top = -1;void push(){int item;if (top < 4){printf ("Enter the number") ;scan ("%d", & item) ;top = top + 1;stack [top] = item;}else{printf (" Stack is full");}} - 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 comoint stack [5], top = -1;void pop(){int item;if (top >= 4){item = stack [top];top = top - 1;printf ("Number deleted is = %d", item) ;}else{printf (" Stack is empty");}}
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:
Fila é declarada comoint queue [5], Front = -1 and rear = -1;void add (){int item;if ( rear < 4){printf ("Enter the number") ;scan ("%d", & item) ;if (front == -1){front =0 ;rear =0 ;}else{rear = rear + 1;}queue [rear] = item ;}else{printf ("Queue is full") ;}} - Dequeue : Para excluir um elemento da função de operação queue.Enqueuing em C:
Fila é declarada comoint queue [5], Front = -1 and rear = -1;void delete (){int item;if ( front ! = -1){item = queue [ front ] ;if (front == rear){front =-1 ;rear =-1 ;}else{front = front + 1;printf ("Number deleted is = %d", item) ;}}else{printf ("Queue is empty") ;}}
Aplicações de 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 impressoras.
- Implementando chamadas de função em um compilador.
Aplicações de fila
- Buffers de dados
- Transferência de dados assíncrona (arquivo IO, pipes, soquetes).
- Alocar solicitações em um recurso compartilhado (impressora, processador).
- Análise de tráfego
- Determine o número de caixas para ter em um supermercado.
Conclusão
Stack e Queue são estruturas de dados lineares que diferem de certas maneiras, 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 dos elementos. Embora existam algumas limitações da fila simples que é recuperada usando outros tipos de fila.
