循環キューとは

循環キューは線形データ構造の一種で、FIFO（先入れ先出し）原則に基づく操作を提供します。通常のキューと異なり、末尾要素が先頭要素に接続されて環状構造を形成するため、リングバッファとも呼ばれます。

循環キューの利点

従来のキューでは領域が満杯になると追加操作が不可能でしたが、循環キューでは先頭側の未使用領域を再利用できるため、メモリ効率が向上します。

データ構造の定義

typedef struct {
    int read_pos;   // 読取位置
    int write_pos;  // 書込位置
    int buffer_size; // バッファ容量
    int* data;      // データ格納配列
} CircularQueue;

基本操作の実装

初期化処理

CircularQueue* create_queue(int capacity) {
    CircularQueue* q = malloc(sizeof(CircularQueue));
    q->buffer_size = capacity + 1;
    q->read_pos = q->write_pos = 0;
    q->data = malloc(sizeof(int) * q->buffer_size);
    return q;
}

空状態の判定

bool is_empty(CircularQueue* q) {
    return q->write_pos == q->read_pos;
}

満杯状態の判定

bool is_full(CircularQueue* q) {
    return (q->write_pos + 1) % q->buffer_size == q->read_pos;
}

要素の追加

bool enqueue(CircularQueue* q, int value) {
    if (is_full(q)) return false;
    
    q->data[q->write_pos] = value;
    q->write_pos = (q->write_pos + 1) % q->buffer_size;
    return true;
}

要素の取り出し

bool dequeue(CircularQueue* q) {
    if (is_empty(q)) return false;
    
    q->read_pos = (q->read_pos + 1) % q->buffer_size;
    return true;
}

先頭要素の参照

int get_front(CircularQueue* q) {
    return is_empty(q) ? -1 : q->data[q->read_pos];
}

末尾要素の参照

int get_rear(CircularQueue* q) {
    if (is_empty(q)) return -1;
    
    int last_pos = (q->write_pos - 1 + q->buffer_size) % q->buffer_size;
    return q->data[last_pos];
}

メモリ解放

void free_queue(CircularQueue* q) {
    free(q->data);
    free(q);
}

使用例

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main() {
    CircularQueue* q = create_queue(3);
    
    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);
    
    printf("先頭要素: %d\n", get_front(q));
    printf("末尾要素: %d\n", get_rear(q));
    
    dequeue(q);
    enqueue(q, 40);
    
    printf("更新後の末尾: %d\n", get_rear(q));
    
    free_queue(q);
    return 0;
}