DEV Community

Cover image for Dia 9 - Primeira versão da fila circular duplamente encadeada
Matheus Gomes
Matheus Gomes

Posted on

Dia 9 - Primeira versão da fila circular duplamente encadeada

Buscando me aprofundar em C++, comecei a fazer as primeiras tasks do meu sistema operacional (jfcOS). Estou usando esse material de estudo: PingPongOS do Prof. Carlos Maziero.
Ele também tem um livro super interessante sobre SO. Vale a pena dar uma olhada.

Comecei meu projeto fazendo a minha primeira versão de uma fila circular duplamente encadeada. Meu código ainda não atende todas as especificidades relatadas no material. Preciso ajustar para os nós aceitarem qualquer tipo de dados, e ainda não tenho certeza se essa fila deve remover só o primeiro item da fila.

Nos próximos dias irei refinar esse código, utilizar a bateria de testes e o arquivo .h disponibilizado pelo professor.

Segue o código feito no dia de hoje (preciso versionar isso):

#include <iostream>

struct Node {
    int value; // por enquanto só aceita inteiros
    Node* next;
    Node* prev;
};

struct CircularDoublyLinkedList {
    Node* head;
    Node* tail;
    int size;

    void Enqueue(int value);
    int Dequeue();
    void Display();
};

void CircularDoublyLinkedList::Enqueue(int value) {
    Node* newNode = new Node{ value, nullptr, nullptr };

    if (size == 0) {
        head = newNode;
        tail = newNode;
        newNode->next = newNode; // é usado "->" para acessar os campos ao invés de "." quando o valor for um ponteiro.
        newNode->prev = newNode;
    } else {
        newNode->prev = tail;
        newNode->next = head;
        tail->next = newNode;
        head->prev = newNode;
        tail = newNode;
    }
    size++;
}

int CircularDoublyLinkedList::Dequeue() { // por enquanto só remove valores do início da queue
    if (size == 0) {
        std::cout << "A fila está vazia\n";
        return 0;
    }

    int value = head->value;
    Node* removedValue = head;

    if (size == 1) {
        head = nullptr;
        tail = nullptr;
    } else {
        head = head->next;
        head->prev = tail;
        tail->next = head;
    }
    size--;

    delete removedValue;
    return value;

}


void CircularDoublyLinkedList::Display() {
    if (size == 0) {
        std::cout << "A fila está vazia\n";
        return;
 }
    Node* current = head;
    for (int i = 0; i < size; i++) {
        std::cout << current->value << " ";
        current = current->next;
    }
    std::cout << std::endl;
}


int main() {
    CircularDoublyLinkedList list;  
    list.head = nullptr;            
    list.tail = nullptr;            
    list.size = 0;                   

    list.Enqueue(10);
    list.Enqueue(20);
    list.Enqueue(30);

    std::cout << "Valores na fila após Enqueue: ";
    list.Display();

    int removedValue = list.Dequeue();
    std::cout << "Valor removido: " << removedValue << std::endl;

    std::cout << "Valores na fila após Dequeue: ";
    list.Display();

    removedValue = list.Dequeue();
    std::cout << "Valor removido: " << removedValue << std::endl;

    std::cout << "Valores na fila após Dequeue: ";
    list.Display();

    removedValue = list.Dequeue();
    std::cout << "Valor removido: " << removedValue << std::endl;

    removedValue = list.Dequeue();

    return 0;
}
Enter fullscreen mode Exit fullscreen mode

A struct Node representa um nó na lista com next (próximo nó) e prev (nó anterior). CircularDoublyLinkedList representa a fila circular, os ponteiros head e tail são referentes ao primeiro e último nó da fila. size representa o número de elementos.

O método Enqueue e Dequeue adicionam e removem nós. E Display lista os nós da fila.

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More