Estruturas de Dados: Pilhas e Filas – Designveloper

Porquê Pilhas e Filas?

Não há operação de acesso aleatório, em pilhas e filas (não podemos acessar um elemento diretamente com um ‘índice’). Normalmente temos menos métodos/ações que podemos executar em tais como push(), pop(), peek(), enqueue(), dequeue(), todos os quais lidam exclusivamente com o elemento no início ou no fim da estrutura de Dados.

But…

Question: Isto soa tão limitador já que só podemos acessar o primeiro ou o último elemento da estrutura de dados. Porque é que alguma vez queremos usar algo como isto? Porque não usamos apenas arrays para maior flexibilidade?

Answer: Pilhas e Filas são normalmente ‘estruturas de dados de nível superior’ construídas em cima das de nível inferior (array ou lista ligada) para limitar as operações que podemos fazer nelas. Isso é um benefício se quisermos um acesso restrito.

Devido a esta capacidade limitada numa estrutura de dados é uma vantagem porque podemos controlar quem quer que use esta estrutura de dados que executa apenas as operações certas que são eficientes. Por exemplo, não teremos que nos perguntar se alguém inseriu aleatoriamente um elemento no meio da nossa lista, estragando algumas invariantes. Isso nos salvou de uma série de problemas. Vamos olhar mais de perto para eles.

O que é uma pilha?

Uma pilha é uma estrutura de dados linear com uma ponta que modela uma pilha do mundo real tendo duas operações primárias, a saber, push e pop.

Nesta imagem abaixo, pudemos ver que um membro de dados sendo retirado do topo da pilha e outro sendo adicionado a ela. Há um ponteiro superior apontando para o bloco no topo da pilha. Isto porque os elementos de uma pilha são sempre removidos e adicionados ao topo da pilha. Este comportamento é normalmente conhecido como LIFO (Last In First Out).

Operações da pilha

As 2 operações básicas que podem ser realizadas numa pilha são as seguintes.

• Função Push: Adicionar um elemento no topo da pilha
• Função Pop: Remove o elemento superior (e pode devolvê-lo)

Visualização das operações básicas da pilha

Outras funções adicionais são fornecidas para uma pilha a fim de verificar o seu estado.

• Função Peek: Devolver o elemento superior da pilha sem remover ou apagar o mesmo
• função isEmpty: Verifique se a pilha está vazia ou não
• função isFull: Verifique se a pilha está cheia ou não

Todos os elementos funcionam na parte superior da pilha. Não temos acesso a mais nada além do topo da pilha. Isto é fundamental para entender como funciona.

Análise de complexidade

A seguinte tabela de complexidade assume que implementou uma pilha usando uma lista ligada

Aplicações da pilha

Quando e onde é usada uma pilha? nós usamos muito Stack na programação sem sequer reparar, aqui estão alguns exemplos:

• Pode ser usado para avaliação de expressões (por exemplo: um algoritmo de pátio de manobra para análise e avaliação de expressões matemáticas).
• Pode ser usado para implementar chamadas de função na programação de recursividade.

• Usado por mecanismos de desfazer em editores de texto para desfazer texto que escrevemos (Cmd + Z no Mac OS e Ctrl + Z no Windows)
• Usado no Browser para navegar para trás e forwards
• Pode ser usado para fazer uma Primeira Pesquisa de Profundidade (DFS) num gráfico
• Utilizado nos bastidores para suportar a recorrência, mantendo-se a par das chamadas de funções anteriores

O que é uma Fila de Espera?

Uma fila é também uma estrutura de dados linear que modela filas do mundo real, tendo duas operações primárias, a saber, perguntar (podemos pensar nisso como “enter the queue”) e dequeue (podemos pensar nisso também como “delete from the queue”). Esta estrutura é chamada de “fila” devido ao facto de se assemelhar a uma fila do mundo real – (onde as pessoas estão à espera numa fila).

Tudo a fila tem uma frente e uma traseira (por vezes chamada de “traseira”). Nós inserimos elementos através do verso e os removemos através da frente.

Uma fila é uma estrutura FIFO (First In First Out – o elemento colocado no início pode ser acessado no início) que pode ser comumente encontrada em muitas linguagens de programação.

Operações de fila

As 3 operações básicas que podem ser executadas numa fila são as seguintes.

• Função Enqueue: Adicionar um elemento ao final da fila
• Função de fila: Remover o elemento do início da fila
• Função Peeking: Olhando para o valor na frente da fila sem removê-lo

Análise de complexidade

Como podemos ver na imagem, as operações de consulta e dequeuing levam tempo constante O(1). No entanto, verificar se um elemento está contido dentro da fila é tempo linear O(n) já que potencialmente precisaríamos varrer todos os elementos.

Existe também a remoção de elementos (não o dequeuing) internamente. Requer tempo linear já que no pior dos casos temos que varrer todos os elementos.

Aplicações de filas

• Utilizado para gerenciar threads em multithreading.
• Pode ser usado para manter o controle eficiente dos x elementos mais recentemente adicionados
• Gerenciamento de solicitações de servidor web onde queremos que o primeiro a chegar seja o primeiro a servir. Por exemplo: A qualquer momento, o nosso servidor web só pode servir até um máximo de 50 pessoas simultaneamente.

Se 70 pedidos chegarem num curto período de tempo, então não poderemos processar todos eles. Então o webserver faz apenas 50 pedidos da fila e coloca os 20 pedidos restantes em espera. Quando o servidor web termina de processar uma requisição, ele desfila a próxima para servir e continua fazendo isso até que a fila esteja vazia.

• Breadth-first search (BFS) graph traversal
• Used to implement queue systems (e.g.: priority queues)
• Used in network printer: A impressora só pode servir um único pedido de cada vez. Portanto, se outros pedidos vierem quando a impressora estiver ocupada, o programa que administra a impressora não rejeitará esses pedidos, mas os colocará em uma fila esperando pela execução. O primeiro pedido será servido primeiro (FIFO).

Esperamos que este artigo lhe tenha dado uma imagem das pilhas e filas em mente. Não se esqueça de assinar nosso blog e seguir o Facebook, Twitter e LinkedIn do Designveloper.

E estes são outros artigos que você pode gostar:

• O que é Arquitetura de Aplicações Web?
• Estruturas de Dados e suas Aplicações
• O que é Grande O Notação?