typedefstruct {
intit[10]; // A pilha em siintmax_size; // Tamanho máximo da pilhainttop; // Índice do último elemento dentro da pilha
} Stack;
voidpush(Stack*stack, intvalue); // Empilha um elementointpop(Stack*stack, intvalue); // Desempilha um elemento e retorna o elemento desempilhadovoidempty(Stack*stack); // Esvazia a pilha (top == -1)boolis_empty(Stack*stack); // Retorna true se a pilha estiver vazia e false se nãoStack*new_Stack(); // Retorna um ponteiro para uma pilha
2 - Filas
Seguem o princípio FIFO (First In First Out)
Inserções (enqueue) ocorrem no final da fila e deleções (dequeue) ocorrem no início da fila
Filas com vetor possuem caráter circular, ou seja para determinar onde se insere um item se usa aritmética modular:
tail = tail % max_size + 1;
Para que a fórmula acima funcione, é preciso que o primeiro índice seja o 1
typedefstruct {
intit[10]; // A fila em siintmax_size; // Tamanho máximo da filainthead; // Início da filainttail; // Final da fila
} Queue;
Queue*new_Queue(); // Retorna um ponteiro para a filaboolqis_empty(Queue*queue); // Retorna true se a fila estiver vazia e false se nãovoidenqueue(Queue*queue, intvalue); // Adiciona um elemento no final da filaintdequeue(Queue*queue); // Remove um elemento no início da filavoidprint_queue(Queue*queue); // Mostra os elementos da fila
3 - Listas encadeadas
Armazena elementos de forma não contígua
Lista composta de nós, cada nó armazena um valor e um ponteiro para o próximo nó na lista
Pode se inserir elementos onde desejar, porém inserções no início possuem complexidade O(1) e inserções no final possuem complexidade O(n)
typedefstruct {
Node*prev;
Node*current;
} SearchContent;
typedefstruct__node {
intdata; // valorstruct__node*next; // ponteiro para o próximo nó na lista
} Node;
typedefstruct {
Node*head; // primeiro nó na lista (não está vazio)
} LinkedList;
LinkedList*new_List(); // Retorna um ponteiro para uma listavoidprint_list(LinkedList*list); // Mostra a listavoidpush_front(LinkedList*list, intvalue); // Adiciona um elemento no início da listavoidpush_back(LinkedList*list, intvalue); // Adiciona um elemento no final da listavoidinsert_in_order(LinkedList*list, intvalue); // Adiciona um elemento na posição correta numa lista ordenada de forma crescenteSearchContent*search(LinkedList*list, intvalue); // Pesquisa por um item em uma lista encadeada ordenadavoidinvert(LinkedList*list); // Inverte uma lista encadeada voidempty_list(LinkedList*list); // Esvazia uma lista encadeada
4 - Lista duplamente encadeada
Similar às listas encadeadas
Porém, cada nó tem a referência para o nó seguinte e para o nó anterior
O nó cabeça (head) é usado como nó auxiliar, ele não armazena valor
A referência seguinte do ultímo nó é o nó cabeça
A referência anterior do nó cabeça é o último nó
Uma lista vazia possui apenas o nó cabeça, com a referência anterior e seguinte sendo o próprio nó cabeça
typedefstruct__double_node {
intdata;
struct__double_node*prev;
struct__double_node*next;
} DoubleNode;
typedefstruct {
DoubleNode*head;
} DoublyLinkedList;
DoublyLinkedList*new_DoublyLinkedList(); // Retorna um ponteiro para uma lista duplamente encadeadaDoubleNode*search_in(DoublyLinkedList*list, intvalue); // Pesquisa um valor em uma lista duplamente encadeada ordenadavoidinsert_in_order_in(DoublyLinkedList*list, intvalue); // Insere um valor de forma ordenada em uma lista duplamente encadeada ordenadavoidremove_from(DoublyLinkedList*list, intvalue); // Remove um valor da lista duplamente encadeadavoidprint_doubly_linked_list(DoublyLinkedList*list); // Mostra o conteúdo da lista duplamente encadeada