Please enable JavaScript.

Coggle requires JavaScript to display documents.

Mapa Mental 6 - Coggle Diagram

- - - - Ele pode representar ao mesmo tempo uma posição e o tamanho da lista
      - Custos das operações citadas com o top:
        
        No início (index 0): Θ(n)
        
        No final (n-1): Θ(1)
  - - - Eficiência temporal:
        
        Como as operações de inserir e remover de ambas possuem eficiência linear equivalentes
      - Eficiência espacial:
        
        Na implementação por array precisa-se reservar espaço antes que pode acabar desutilizado; enquanto na linked stack cada elemento armazena um ponteiro ligando o próximo. No final, nenhuma é melhor que a outra
      - Casos especiais:
        
        Quando duas stacks estão inversamente correlacionadas, é melhor implementar duas stacks em uma array só, podendo até aumentar/diminuir por ambos os lados da array de maneira eficiente
    - - Esse 1º nó é chamado de top mas ele não seria o real top pois todas as operações acontecem no segundo nó (o qual o top é ligado)
- - - - 1) Criar uma array vazia em que a queue (não-vazia e menor que a array) está dentro. O fato do queue em si não ser do mesmo tamanho da array, permite que a eficiência de operações de inserir e remover sejam ambas de Θ(1)
        
        Se uma das operações for feita em uma das bordas da array, a eficiência passa a ser Θ(n) devido ao reposicionamento de todos os elementos
      - 2) Fazer com que os índices da array sejam baseado em operações de resto (mod ou %), para o array ter um esquema parecido com o de um círculo, fazendo o próximo índice depois do n-1 ser 0
      - (O problema é que após a impliementação via array, você não consegue definir facilmente se a queue está vazia ou cheia)
  - - - Eficiência temporal:
        
        As operações de inserir e remover de ambos os métodos gastam aproximadamente o mesmo tempo
      - Eficiência espacial:
        
        Na implementação por array precisa-se reservar espaço antes que pode acabar desutilizado; enquanto na linked stack cada elemento armazena um ponteiro ligando o próximo. No final, nenhuma é melhor que a outra
      - Outros critérios:
        
        Como visto, a implementação via array é mais complicada e pode trazer problemas na checagem do seu tamanho, enquanto a queue ligada não apresenta esses problemas
    - - (Ambos esse novos elementos não fazem parte da lista em si)