Please enable JavaScript.

Coggle requires JavaScript to display documents.

Stacks // Pilhas, Queues // Filas - Coggle Diagram

- - - - Method top
        
        Atua como um valor de posição atual, como também como um indicador do núm. de elem. presentes na pilha atual.
        
        Porque a posição atual sempre estará na posição de top da pilha.
        
        Nos termos de função de lista, todas as operações de Insert e remove serão aplicadas no elemento de posição 0.
        
        Agora, são operações ineficiêntes, pois para cada operação de push e pop teremos que trabalhar com um deslocamento de posição dos elemetos, no qual tem magnitude de BIG OH(n) para n eleme..
  - - - Um header node não é usado pois é um caso especial do código, no qual é requerido para listas de 0 ou 1 elem..
      - Um único membro de dados é top, um ponteiro para o primeiro(top) link de nó de uma pilha.
        
        Método de push.
        
        Primeiro modifica o próx. campo de um novo link de nó para o ponteiro para o top de uma pilha a então seta o top para o ponteiro com o novo link de nó.
        
        Método pop.
        
        Uma var. tmp amazena o valor do top nó, enquanto ltmp liga para o top node que será removido da pilha.
        
        A pilha sofre uma atualização pelo ajuste do top para um ponteiro para o próx. link da pilha.
        
        O antigo top node é então retornado para se dar um free e desalocar a memória.
    - - Todas as operações para array-based e linked list stack tem suas implementações tomadas por um tempo constante, logo, nenhuma assume vantagem temporal.
        
        Um array-based pilha deve ser declarado inicialmente com um tamanho fixo de espaço, no entanto, caso a pilha não esteja totalmente cheia, acarreta no desperdicio de espaço.
        
        Agora, para uma linked stack pode sim crescer ou encolher de tamanho, porém faz isso com a ressalva de que é necessário uma sobrecarga no campo de link para o próx. elem., uma nova caixa para apontar para outro elemento.
        
        Quando multiplas pilhas são implementadas, é possível tirar vantagem do crescimento unilateral de um array-based stack.
        
        Pode ser feito por meio de um único array que armazena duas pilhas.
        
        Contudo, isso só funciona bem quando a relação de espaço de ambas as pilhas forem inversamente proporcionais.
        
        Em especial, quando um elemento sai de uma pilha para ir a outra pilha
        
        Se ambas as pilhas crescerem igualmente, siginifica que rapidamente o espaço livre no meio delas será preenchido.
- - - - Nós usariamos um link de nó encabeçada, que seguirá por uma simples implementação de uma operação de filas assim evitando algum caso especial quando a fila for vazia.
        
        Na inicialização, o front e o rear apontaram para o mesmo header node,e o front sempre apontará para o header node, enquanto o rear apontará para o último link node na fila.
        
        No método enqueue o novo elemento será linkado no fim da lista encadeada.
        
        O método dequeue removerá e retornará o primeiro elemento da lista.
  - - - Caso escolhermos o elemento posterior da fila que esteja na posição 0,a operação de remoção será da ordem de BIG THETA(1), pois o elemento frontal é o último elemento do array.
        
        Contudo, a operação de inserir elem. será da ordem BIG THETA(n), pois os n elementos terão que sofrer um deslocamento.
      - Supondo que o ele. frontal esteja na posição 0 e que os elementos serão incluidos nas posições sucessivamente mais altas do array.
        
        Quando os ele. são removidos, o índi. frontal aumenta, de certa forma que um elem. será inserido na posição mais alta do arrya, e a fila ficará sem espaço.
        
        Ess problema pode ser resolvido pela implementação de um array circular.
  - - - Os problemas referente ao espaço por ambas implementações são equivalentes.
        
        Ao contrário da implementação das filas por array, não há uma forma de implementar duas filas no mesmo array sem que haja a transferência direta de uma para a outra.