キューのC言語実装

キューの実装は、先進的な先出し戦略です.以下では、メモリを動的に割り当てる配列を使用してキューを実装します.ここで、キューのresizeプロシージャは、元のキューのitemを保持しません.

//Item.h
typedef struct ITEM {
    int key;
    void * statellite;
} item_t;

//Queue.h
#ifndef STDIO_H
#define STDIO_H
#include 
#endif

#ifndef STDLIB_H
#define STDLIB_H
#include 
#endif

#ifndef ITEM_H
#define ITEM_H
#include "Item.h"
#endif

typedef struct QUEUE
{
    int head;
    int tail;
    int count;
    int size;
    item_t* array;
} queue_t;

int queue_init(queue_t * Q, int size);
int queue_resize(queue_t * Q, int size);
int queue_free(queue_t * Q);
int queue_empty(queue_t * Q);
int queue_enqueue(queue_t * Q, item_t item);
int queue_dequeue(queue_t * Q, item_t * item);
void queue_info(queue_t * Q);

//Queue.c
#include "Queue.h"

int queue_init(queue_t * Q, int size) {
    Q->head = 0;
    Q->tail = 0;
    Q->count = 0;
    Q->array = (item_t*)calloc(size, sizeof(item_t));
    if (Q->array != NULL) {
        Q->size = size;
        return 1;
    } else {
        Q->size = 0;
        fprintf(stderr, "Queue init fail.
");
        return 0;

    }
}
int queue_resize(queue_t * Q, int size) {
    queue_free(Q);
    return queue_init(Q, size);
}
int queue_free(queue_t * Q) {
    free(Q->array);
    Q->head = 0;
    Q->tail = 0;
    Q->count = 0;
    Q->size = 0;
    Q->array = NULL;
    return 1;
}
int queue_empty(queue_t * Q) {
    if (Q->array == NULL) {
        fprintf(stderr, "Queue is not initialized.
");
        return 1;
    }
    if (Q->count == 0)
        return 1;
    else return 0;
}
int queue_enqueue(queue_t * Q, item_t item) {
    if (Q->array == NULL) {
        fprintf(stderr, "Queue is not initialized.
");
        return 0;
    }
    if (Q->count < Q->size) {
        Q->array[Q->head] = item;
        Q->head = (Q->head + 1) % Q->size;
        Q->count++;
        return 1;
    } else {
        fprintf(stderr, "Queue overflow.
");
        return 0;
    }
}
int queue_dequeue(queue_t * Q, item_t * item) {
    if (Q->array == NULL) {
        fprintf(stderr, "Queue is not initialized.
");
        return 0;
    }
    if (!queue_empty(Q)) {
        *item = Q->array[Q->tail];
        Q->tail = (Q->tail + 1) % Q->size;
        Q->count--;
        return 1;
    } else {
        fprintf(stderr, "Queue underflow.
");
        return 0;
    }
}
void queue_info(queue_t * Q) {
    static int count = 0;
    printf("%d:
", count++);
    if (Q->array == NULL) {
        fprintf(stderr, "queue is not initialized.
-------------------------------
");
        return;
    }
    printf("queue head location:%d
", Q->head);
    printf("queue tail location:%d
", Q->tail);
    printf("queue count:%d
", Q->count);
    printf("queue size:%d
", Q->size);
    for (int i = 0; i < Q->size; i++) {
        printf("%d:%d ", i, Q->array[i].key);
    }
    printf("
-------------------------------
");
}

このキューでは、キューが空でない場合、tailが指す位置は常にitemがキューにあり、キューが空である場合、tailが指す位置は空である.キューが満たされていない場合、headが指す位置は常に空であり、キューが満たされている場合、headが指す位置はキューの末端の要素の位置である.両端キューを実装するには(挿入削除は両端で行えます)、次のコードを追加します.重要なのは、キュー内で上記の特性を維持する方法です.

//functions for deque
int deque_head_insert(queue_t * Q, item_t item) {
    return queue_enqueue(Q, item);
}
int deque_tail_insert(queue_t * Q, item_t item) {
    if (Q->array == NULL) {
        fprintf(stderr, "Queue is not initialized.
");
        return 0;
    }
    if (Q->count < Q->size) {
        if (Q->count != 0) {
            Q->tail = (Q->tail - 1) % Q->size;
            if (Q->tail < 0) {
                Q->tail += Q->size;
            }
            Q->array[Q->tail] = item;
            Q->count++;
            return 1;
        } else {
            Q->count = 1;
            Q->tail = 0;
            Q->head = 1;
            Q->array[Q->tail] = item;
            return 1;
        }
    } else {
        fprintf(stderr, "Queue overflow.
");
        return 0;
    }
}
int deque_head_delete(queue_t * Q, item_t * item) {
    if (Q->array == NULL) {
        fprintf(stderr, "Queue is not initialized.
");
        return 0;
    }
    if (!queue_empty(Q)) {
        Q->head = (Q->head - 1) % Q->size;
        if (Q->head < 0) {
            Q->head += Q->size;
        }
        *item = Q->array[Q->head];
        Q->count--;
        return 1;
    } else {
        fprintf(stderr, "Queue underflow.
");
        return 0;
    }
}
int deque_tail_delete(queue_t * Q, item_t * item) {
    return queue_dequeue(Q, item);
}