Please enable JavaScript.

Coggle requires JavaScript to display documents.

M5 (Abstract Data Types and Data Structures, Lists, Stacks, and Queues) -…

- - - - Booleano
        
        Verdadeiro e Falso
      - Simple type
        
        int
        
        its value contains no subparts
      - aggregate type
      - composite type
  - - - a member of a type
  - - - the behavior of each operation is determined by its inputs and outputs
  - - - Each operation associated with the adt is implemented by a member function
    - - File Structure
        
        often refers to the organization of data on peripheral storage, such as a disk drive or CD
- - - - Restrição de inserção e remoção em uma extremidade.
      - Menos flexibilidade em comparação com listas.
      - Eficiente para operações específicas.
    - - Muitas aplicações requerem apenas operações limitadas oferecidas por pilhas.
      - Eficiência e facilidade de implementação.
      - freelist é um exemplo de uma pilha.
    - - Elemento acessível é chamado de topo.
      - Inserção é chamada de "push" (empurrar).
      - Remoção é chamada de "pop" (retirar).
    - - Versão simplificada da lista baseada em array.
      - Importante decisão de design: qual extremidade do array representa o topo da pilha.
      - Topo na Posição 0 (Ineficiente)
      - Topo na Posição n − 1 (Eficiente)
    - - Elementos são inseridos e removidos apenas da cabeça da lista.
      - Estrutura simples usando ponteiros.
      - Uso eficiente de inserção e remoção no topo da pilha.
      - Método Push
        
        Adiciona um novo nó à pilha.
        
        Modifica o campo "next" do novo nó para apontar para o antigo topo.
        
        Atualiza o ponteiro "top" para o novo nó.
      - Método Pop
        
        Remove o nó do topo da pilha.
        
        Armazena o valor do nó removido em "temp".
        
        Atualiza "top" para o próximo nó na pilha.
        
        Retorna o valor do nó removido.
  - - - Lista é uma sequência finita e ordenada de elementos
      - Elementos têm um tipo de dado
      - Lista pode ser vazia, e seu comprimento é o número de elementos.
      - Cabeça (head) e cauda (tail) indicam o início e o final da lista.
    - - Inserir e remover elementos em qualquer posição.
      - Acessar e modificar valores dos elementos.
      - Criar e limpar (reinicializar) listas.
      - Acesso ao próximo ou anterior elemento do "atual".
    - - Define uma classe abstrata em C++ como template.
      - Usa conceito de uma posição "atual" para inserção e remoção.
      - Métodos como moveToStart, next, e prev manipulam a posição atual.
      - Flexibilidade do TAD
        
        TAD é flexível, podendo armazenar diferentes tipos de elementos.
        
        Abstração não especifica como operações são implementadas.
        
        Possibilidade de múltiplas implementações com diferentes trade-offs espaço/tempo.
    - - Distinção entre tipos simples e compostos.
      - Possibilidade de tipos heterogêneos em uma lista, se necessário.
    - - Array-Based List Implementation
        
        named AList
        
        Implementação
        
        AList herda da classe abstrata List.
        
        Membros privados incluem listArray, maxSize, listSize e curr.
        
        listArray armazena os elementos da lista.
        
        Tamanho máximo da lista é definido por maxSize.
        
        listSize mantém o número atual de elementos na lista.
        
        curr representa a posição atual na lista.
        
        Construtor AList permite definir o tamanho máximo da lista (parâmetro opcional).
      - Linked Lists
        
        Implementação de Lista Encadeada
        
        Segundo método tradicional para implementar listas.
        
        Usa ponteiros e é conhecida como lista encadeada.
        
        Utiliza alocação dinâmica de memória para novos elementos.
      - Freelists
      - Doubly Linked Lists
  - - - Remoção na parte da frente (dequeue).
      - emelhante a ficar em fila em um cinema.
      - Inserção na parte de trás (enqueue).
    - - Adaptação direta da lista encadeada
      - Uso de um nó de link de cabeçalho para simplificar a implementação.
      - Inicialização da Fila
        
        No início, front e rear apontam para o nó de cabeçalho.
        
        Rear aponta para o verdadeiro último nó de link na fila.
      - Método Enqueue
        
        Adiciona um novo elemento em um nó de link no final da lista encadeada.
        
        Atualiza o ponteiro rear para apontar para o novo nó de link.
      - Método Dequeue
        
        Remove e retorna o primeiro elemento da lista.
        
        Front aponta para o nó de cabeçalho durante a operação.