Pular para o conteúdo principal

Estrutura de Dados.


Pilha
• É uma lista linear em que todas as inserções, retiradas e, geralmente, todos os acessos são feitos em apenas um extremo da lista.

• Os itens são colocados um sobre o outro. O item inserido mais recentemente está no topo e o inserido menos recentemente no fundo.

• O modelo intuitivo é o de um monte de pratos em uma prateleira, sendo conveniente retirar ou adicionar pratos na parte superior.

• Esta imagem está freqüentemente associada com a teoria de autômato, na qual o topo de uma pilha é considerado como o receptáculo de uma cabeça de leitura/gravação que pode empilhar e
desempilhar itens da pilha.


• Propriedade: o último item inserido é o primeiro item que pode ser retirado da lista. São chamadas listas lifo (“last-in, first-out”).

• Existe uma ordem linear para pilhas, do “mais recente para o menos recente”.

• É ideal para estruturas aninhadas de profundidade imprevisível.

• Uma pilha contém uma seqüência de obrigações adiadas. A ordem de remoção garante que as estruturas mais internas serão processadas antes das mais externas.


• As pilhas ocorrem em estruturas de natureza recursiva (como árvores). Elas são utilizadas para implementar a recursividade.


Conjunto de operações:
1. FPVazia(Pilha). Faz a pilha ficar vazia.
2. Vazia(Pilha). Retorna true se a pilha está vazia; caso contrário,
retorna false.
3. Empilha(x, Pilha). Insere o item x no topo da pilha.
4. Desempilha(Pilha, x). Retorna o item x no topo da pilha, retirando-o
da pilha.
5. Tamanho(Pilha). Esta função retorna o número de itens da pilha.


• As duas representações mais utilizadas são as implementações por meio de arranjos e de apontadores.



Fila
• É uma lista linear em que todas as inserções são realizadas em um extremo da lista, e todas as retiradas e, geralmente, os acessos são realizados no outro extremo da lista.

• O modelo intuitivo de uma fila é o de uma fila de espera em que as pessoas no início da fila são servidas primeiro e as pessoas que chegam entram no fim da fila.

• São chamadas listas fifo (“first-in”, “first-out”).

• Existe uma ordem linear para filas que é a “ordem de chegada”.

• São utilizadas quando desejamos processar itens de acordo com a ordem “primeiro-que-chega, primeiro-atendido”.

• Sistemas operacionais utilizam filas para regular a ordem na qual tarefas devem receber processamento e recursos devem ser alocados a processos.


Conjunto de operações:
1. FFVazia(Fila). Faz a fila ficar vazia.
2. Enfileira(x, Fila). Insere o item x no final da fila.
3. Desenfileira(Fila, x). Retorna o item x no início da fila, retirando-o
da fila.
4. Vazia(Fila). Esta função retorna true se a fila está vazia; senão
retorna false.


• Os itens são armazenados em posições contíguas de memória.

• A operação Enfileira faz a parte de trás da fila expandir-se.

• A operação Desenfileira faz a parte da frente da fila contrair-se.

• A fila tende a caminhar pela memória do computador, ocupando espaço na parte de trás e descartando espaço na parte da frente.

• Com poucas inserções e retiradas, a fila vai ao encontro do limite do espaço da memória alocado para ela.

• Solução: imaginar o array como um círculo. A primeira posição segue a última.


• As duas representações mais utilizadas são as implementações por meio de arranjos e de apontadores.














Comentários

+ Vistas

Mais uma inovação da Google.

Sabe aqueles filmes em que um cientista possui um laboratório secreto onde faz seus experimentos mais malucos? O Google tem algo parecido, chamado "Google X". A operação foi descoberta e mostrada ao mundo neste domingo (13/11) em uma matéria do New York Times. E é de lá que podem sair duas tecnologias com potencial de mudar a forma como conhecemos os carros atualmente. De acordo com o site Electronista, uma fonte que não quis se identificar afirmou que a empresa planeja construir carros que dispensam a necessidade de motoristas. O Google os fabricaria nos EUA e os venderia para empresas locais que queiram eliminar a figura do condutor de seu quadro de funcionários. A outra invenção do Google X é relacionada à robótica. Máquinas poderiam, por exemplo, substituir os motoristas do Google Street View, encarregados de dirigir pelas cidades enquanto o sistema fotografa as ruas. Na equipe do Google X estão Sebastian Thrun, um dos maiores experts em robótica e inteligência a...

Existe uma fórmula padrão de Calculo de Estoque Mínimo e Máximo?

  Na verdade, não existe uma fórmula única e universal para calcular o estoque mínimo e máximo ideal para uma empresa de varejo, pois diversos fatores influenciam esses valores. No entanto, existem algumas fórmulas e métodos básicos que podem te ajudar a estimar esses níveis de forma eficiente, considerando as características específicas do seu negócio. Fórmula básica para o estoque mínimo: Estoque mínimo = Consumo médio diário x Tempo de reposição Essa fórmula leva em conta a quantidade média de produtos que você vende por dia e o tempo que leva para receber novos produtos do seu fornecedor. O objetivo é garantir que você tenha estoque suficiente para atender à demanda durante esse período de reposição, mesmo que haja imprevistos. Fórmula básica para o estoque máximo: Estoque máximo = Estoque médio + Lote de compra Essa fórmula considera o seu estoque médio, que é a quantidade média de produtos que você costuma ter em estoque, e o tamanho do lote de compra que você costuma fazer. ...

Instalando o novo Gnome 3 no Debian 6

Instalando o novo Gnome 3 no Debian 6 (Atualizado) Vi essa dica em um comentário no site  Br-Linux , e como eu testei e deu muito certo, decidi repassar a dica... Atenção: Faça por sua conta e risco, comigo a instalação ocorreu muito bem, mais isso não impede que em outras situações a instalação não ocorra como esperado.  Para instalar o Gnome 3 no Debian 6, vamos usar os repositórios  unstable e experimental, para isso abra um terminal e como root digite: #nano /etc/apt/sources.list  Adicione as linhas a seguir: #Instavel deb http://sft.if.usp.br/debian/ sid main non-free contrib deb-src http://sft.if.usp.br/debian/ sid main non-free contrib #Experimental deb http://sft.if.usp.br/debian/ experimental main non-free contrib deb-src http://sft.if.usp.br/debian/ experimental main non-free contrib  Agora digite ctrl+o e enter para salvar a configuração, e depois digite: #apt-get update    e para instalar: #apt-get install -t ...