Please enable JavaScript.

Coggle requires JavaScript to display documents.

PILHAS, Filas - Coggle Diagram

- - - - Topo na posição 0
        
        Qualquer inserção ou remoção de elemento terá que ser na posição 0
        
        Ineficiente
        
        Cada operação desse tipo teria que mover os n elementos do array uma posição, o que toma um tempo de \(\Theta(n)\)
      - Topo na posição \(n-1\) em um array com n elementos
        
        Os elementos colocados na pilha são postos no final dela
        
        Os elementos são removidos do final da pilha
        
        O custo das operações é \(\Theta(1)\)
      - Os métodos para inserir e retirar um elemento da pilha realizam essas operações no topo dela
  - - - Inicialmente, é necessário modificar o campo do nó indicando o próximo item da pilha
  - - - Nenhuma se destaca quanto à eficiência de tempo
    - - Pilhas baseadas em array precisam declarar o tamanho máximo na criação da pilha
        
        Pode fazer com que parte do espaço seja inutilizado caso não esteja preenchido
      - Pilhas conectadas podem mudar de tamanho, mas requerem que as conexões entre os nós sejam armazenadas na memória
    - - Um array pode armazenar duas pilhas
        
        Cada pilha cresce a partir de cada uma das pontas do array de fora para dentro, em direção ao meio do array
        
        Só funciona bem quando o espaço necessário pelas duas pilhas estão inversamente relacionados
        
        Quando uma pilha cresce, a outra diminui
- - - - Essa informação é chamada de registro de ativação
        
        O registro de ativação precisa ser criado e armazenado na pilha toda vez que a função é chamada
        
        Operação com custo relativamente alto
- - - - Não precisar que os \(n\) elementos da fila estejam nas \(n\) primeiras posições do array
        
        Não ser necessário mover os outros \(n-1\) elementos para preencher o espaço que foi liberado ao remover um elemento, além de um raciocínio semelhante para adicionar um item à fila
        
        Dessa forma, enfileirar e desenfileirar irão tomar um tempo de \(\Theta(1)\), pois nenhum outro elemento precisa ser movido
        
        Isso gera um problema
        
        Conforme mais números são adicionados e outros são retirados, sobram espaços vazios no sentido do início da fila, mas eles não são usados
        
        A fila fica sem espaço caso um elemento seja colocado em seu último espaço
        
        É possível evitar isso simulando um array circular, no qual a última posição se conecta diretamente com a primeira
        
        Uso do operador de módulo
    - - Armazenar os índices dos elementos do início e do final da fila
        
        Para o computador, uma fila vazia e uma fila completamente cheia são indistinguíveis, pois, em ambos os casos, o valor que indica o final da fila é uma unidade menor que o valor que indica o início dela
        
        Soluções
        
        Manter uma variável booleana para indicar se o array está cheio ou não
        
        Fazer um array de tamanho \(n+1\), mas só permitir que \(n\) posições sejam usadas
  - - - Os ponteiros inicial e final irão apontar para esse nó inicialmente
        
        O ponteiro inicial sempre irá apontar para esse nó, enquanto que o ponteiro final irá apontar para o último nó da fila
    - - Coloca um elemento no final da lista e muda o ponteiro final para esse novo elemento
    - - Retira e retorna o primeiro elemento da fila
  - - - Mesmas especificações para suas implementações equivalentes em pilhas
        
        Porém, enquanto 2 pilhas baseadas em array podem ser armazenadas em 1 array, não há como fazer isso de forma conveniente com as filas