キューはFIFO（First-In-First-Out）構造を持つデータ構造であり、配列ではなく単方向リンクリストを用いて実装することも可能である。この方法ではメモリを動的に確保できるため、事前の容量制限が不要で、拡張性に優れている。

本実装では、先頭ノードを指すheadと末尾ノードを指すtailの2つのポインタを保持し、以下6つの基本操作を提供する：

• enqueue：末尾に要素を追加
• dequeue：先頭から要素を削除して返す
• front：先頭要素を参照（削除なし）
• back：末尾要素を参照（削除なし）
• empty：キューが空か判定
• size：要素数を取得

ノード構造とクラス定義

#include <iostream>
#include <stdexcept>

class LinkedQueue {
private:
    struct Node {
        int data;
        Node* next;
        Node(int val) : data(val), next(nullptr) {}
    };

    Node* head;
    Node* tail;

public:
    LinkedQueue();
    ~LinkedQueue();

    void enqueue(int value);
    int dequeue();
    int front() const;
    int back() const;
    bool empty() const;
    int size() const;
};

コンストラクタとデストラクタ

LinkedQueue::LinkedQueue() : head(nullptr), tail(nullptr) {}

LinkedQueue::~LinkedQueue() {
    while (!empty()) {
        dequeue();
    }
}

エンキュー（enqueue）

新しいノードを末尾に追加。キューが空の場合、headとtailの両方がそのノードを指すようにする。

void LinkedQueue::enqueue(int value) {
    Node* newNode = new Node(value);
    if (empty()) {
        head = tail = newNode;
    } else {
        tail->next = newNode;
        tail = newNode;
    }
}

デキュー（dequeue）

先頭ノードを削除し、その値を返す。削除後にキューが空になる場合、tailもnullptrに更新する必要がある。

int LinkedQueue::dequeue() {
    if (empty()) {
        throw std::underflow_error("Queue is empty");
    }

    Node* temp = head;
    int value = temp->data;
    head = head->next;

    if (head == nullptr) {
        tail = nullptr;
    }

    delete temp;
    return value;
}

その他のユーティリティ関数

int LinkedQueue::front() const {
    if (empty()) {
        throw std::underflow_error("Queue is empty");
    }
    return head->data;
}

int LinkedQueue::back() const {
    if (empty()) {
        throw std::underflow_error("Queue is empty");
    }
    return tail->data;
}

bool LinkedQueue::empty() const {
    return head == nullptr;
}

int LinkedQueue::size() const {
    int count = 0;
    Node* current = head;
    while (current != nullptr) {
        ++count;
        current = current->next;
    }
    return count;
}

使用例

int main() {
    LinkedQueue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    std::cout << "Front: " << q.front() << "\n";
    std::cout << "Back: " << q.back() << "\n";
    std::cout << "Dequeued: " << q.dequeue() << "\n";
    std::cout << "Size: " << q.size() << "\n";
    std::cout << "Empty: " << (q.empty() ? "Yes" : "No") << "\n";

    return 0;
}