Please enable JavaScript.

Coggle requires JavaScript to display documents.

Stacks e Queues, Stacks(Pilhas), Queues(Filas) - Coggle Diagram

- - - - À medida que os elementos são colocados na pilha, eles são anexados ao final da lista. O método pop remove o elemento final. Neste caso, o custo de cada operação push ou pop é apenas Θ(1).
    - - Esta implementação é ineficiente, porque agora cada operação push ou pop exigirá que todos os elementos atualmente na pilha sejam deslocados uma posição na matriz, por um custo de Θ(n) se houver n elementos
- - - - A operação de enfileiramento será equivalente a uma operação de acréscimo em uma lista. Isso requer apenas tempo Θ(1).
      - A operação de desenfileiramento requer tempo Θ(n), porque todos os elementos devem ser deslocados uma posição para baixo para reter a propriedade de que os n − 1 elementos da fila restantes residem nas primeiras n − 1 posições do array.
    - - As operações de enfileiramento exigirão um tempo Θ(n), porque os n elementos atualmente na fila devem ser deslocados, cada um, uma posição na matriz.
      - As operações de desenfileiramento requerem apenas tempo Θ(1) porque o primeiro elemento da fila (aquele que está sendo removido) é o último elemento da matriz.
    - - Se os elementos da fila não ficarem nas posições extremas do array, como por exemplo no centro do array
      - Tanto as operações de enfileiramento quanto de desenfileiramento podem ser executadas em tempo Θ(1) porque nenhum outro elemento na fila precisa ser movido.
      - Problema da fila flutuante(drifting queue)
        
        Supondo que o primeiro elemento da fila esta na posição 0 e que os elementos sejam adicionados sucessivamente às posições de numeração mais alta na matriz. Quando os elementos são removidos da fila, o índice do primeiro elemento aumenta. Com o tempo, toda a fila irá desviar para as posições numeradas mais altas na matriz. Depois que um elemento é inserido na posição de número mais alto na matriz, a fila fica sem espaço. Isso acontece apesar do fato de que pode haver posições livres na extremidade inferior do array onde os elementos foram previamente removidos da fila.
        
        Solução
        
        O problema da “fila flutuante” pode ser resolvido fingindo que o array é circular e assim permitir que a fila continue diretamente da posição de número mais alto no array para a posição de número mais baixo.
        
        as posições na matriz são numeradas de 0 a tamanho-1, e a posição tamanho-1 é definida para preceder imediatamente a posição 0 (que é equivalente ao tamanho da posição% tamanho).
  - - - Diferenciar lista vazia/cheia
        
        Uma solução óbvia é manter uma contagem explícita do número de elementos na fila, ou pelo menos uma variável booleana que indique se a fila está vazia ou não. Outra solução é fazer com que o array tenha tamanho n + 1 e permitir que apenas n elementos sejam armazenados.