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;
}

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.

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