Please enable JavaScript.
Coggle requires JavaScript to display documents.
Stacks, Queues - Coggle Diagram
Stacks
Conceito
A pilha é uma estrutura tipo uma lista na qual os elementos podem ser inseridos ou removidos de apenas uma extremidade. Embora essa restrição torne as pilhas menos flexíveis do que as listas, também torna as pilhas eficientes (para as operações que podem fazer) e fáceis de implementar.
Muitas aplicações requerem apenas a forma limitada de inserir e remover operações que as pilhas fornecem. Nesses casos, é mais eficiente usar a estrutura de dados da pilha mais simples do que a lista genérica.
A pilha tbm é conhecida por uma lista "LIFO", que significa "Last-In, First-Out." Observe que uma implicação da política LIFO é que as pilhas removem elementos por ordem inversa da sua chegada. Funciona com o princípio "último a entrar, primeiro a sair"
O elemento acessível da pilha é chamado de elemento superior. Os elementos não são ditos para serem inserido, eles são empurrados para a pilha. Quando removido, um elemento é dito para ser retirado da pilha
-
Exemplo Prático: Uma analogia com uma pilha de pratos, onde você adiciona um prato no topo e retira o último prato que foi adicionado.
Arrray-Based Stacks
Tal como acontece com a implementação de lista baseada em array, listArray deve ser declarado de tamanho fixo quando a pilha é criada.
A implementação da pilha baseada em array é essencialmente uma versão simplificada do Lista baseada em array.
Em termos de funções de lista, todos os inserem e removem operações seriam então sobre o elemento na posição 0. Esta implementação é ineficiente, porque agora cada operação push ou pop exigirá que todos os elementos atualmente na pilha ser deslocada uma posição na matriz, para um custo de Θ(n) se houver n elementos.
Por outras palavras, à medida que os elementos são empurrados a pilha, eles são anexados à cauda da lista. Método pop remove a cauda elemento. Neste caso, o custo para cada operação push ou pop é de apenas Θ(1).
Métodos push e pop
simplesmente coloca um elemento dentro, ou remove um elemento da posição do array indicado por cima. Como o topo é considerado na primeira posição livre, empurre primeiro insere seu valor na posição superior e depois incrementa o topo, enquanto pop primeiro decrementos top e, em seguida, remove o elemento top.
Linked Stacks
A implementação da pilha linked é bastante simples. Os elementos são inseridos e removidos da cabeça da lista. Um nó de cabeçalho não é usado porque nenhum código de caso especial é necessário para listas de zero ou um elemento.
O único membro de dados é superior, um ponteiro para o primeiro nó de link (superior) da pilha.
Método push primeiro modifica o próximo campo do link recém-criado nó para apontar para o topo da pilha e, em seguida, define o topo para apontar para o novo link node..
Método pop também é bastante simples. Variável temp armazena o valor dos nós superiores, enquanto ltemp links para o nó superior, pois é removido da pilha. A pilha é atualizado definindo o topo para apontar para o próximo link na pilha. O nó superior antigo é em seguida, retornou à loja livre (ou à lista livre), e o valor do elemento é retornado
-
Queues
Array-Based Queues
A fila baseada em array é um pouco complicada de implementar eficazmente. Uma simples conversão da implementação da lista baseada em array não é eficiente.
Uma implementação eficiente pode ser obtida desconsiderando a exigência de que todos os elementos da fila devem estar nas primeiras n posições do array. Ainda exigiremos que a fila seja armazenada em posições de array contíguas, mas o conteúdo da fila será permitido a deriva dentro do array. Agora, as operações enqueue e dequeue podem ser realizado no tempo Θ(1) porque nenhum outro elemento na fila precisa ser movido.
O problema da "fila à deriva" pode ser resolvido fingindo que o array é circular e assim permitir que a fila continue diretamente do número mais alto posição na matriz para a posição de menor número.
Ignorando a posição real do primeiro elemento e ignorando os valores reais dos elementos armazenados na fila, quantos estados diferentes existem? Não poderá haver elementos na fila, um elemento, dois, e assim por diante. No máximo poderá haver n elementos na fila se existirem n posições de array. Isso significa que há n + 1 estados diferentes para a fila (0 a n elementos são possíveis).
Uma solução óbvia é manter uma contagem explícita do número de elementos em
a fila, ou pelo menos uma variável booleana que indica se a fila está vazia ou não. Outra solução é fazer com que o array seja de tamanho n + 1, e só permita n elementos a serem armazenados
Conceito
Como a pilha, a fila é uma estrutura de lista que fornece acesso restrito a
seus elementos. Os elementos da fila só podem ser inseridos na parte de trás (chamado de enqueue operação) e removido da frente (chamada operação dequeue).
Funciona com o princípio "primeiro a entrar, primeiro a sair" (FIFO - First In, First Out). Assim, as filas libertam os seus elementos por ordem de chegada.
-
Linked Queues
-
Na inicialização, a frente e os ponteiros traseiros apontarão para o nó do cabeçalho, e a frente sempre apontará para o nó do cabeçalho enquanto a traseira aponta para o verdadeiro último nó de ligação na fila.
Método enqueue coloca o novo elemento em um nó de link no final da lista vinculada (ou seja, o nó que aponta para trás) e, em seguida, avança para trás para apontar para o novo link node. Método dequeue remove e retorna o primeiro elemento da lista.
-