队列（Queue）的C语言实现

队列的实现是一种先进先出的策略。以下使用动态分配内存的数组来实现一个队列。其中，队列的resize过程将不会保留原来队列中的item。

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

//Queue.h
#ifndef STDIO_H
#define STDIO_H
#include <stdio.h>
#endif

#ifndef STDLIB_H
#define STDLIB_H
#include <stdlib.h>
#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.\n");
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.\n");
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.\n");
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.\n");
return 0;
    }
}
int queue_dequeue(queue_t * Q, item_t * item) {
if (Q->array == NULL) {
fprintf(stderr, "Queue is not initialized.\n");
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.\n");
return 0;
    }
}
void queue_info(queue_t * Q) {
static int count = 0;
printf("%d:\n", count++);
if (Q->array == NULL) {
fprintf(stderr, "queue is not initialized.\n-------------------------------\n");
return;
    }
printf("queue head location:%d\n", Q->head);
printf("queue tail location:%d\n", Q->tail);
printf("queue count:%d\n", Q->count);
printf("queue size:%d\n", Q->size);
for (int i = 0; i < Q->size; i++) {
printf("%d:%d ", i, Q->array[i].key);
    }
printf("\n-------------------------------\n");
}

该队列中，当队列不为空时，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.\n");
        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.\n");
        return 0;
    }
}
int deque_head_delete(queue_t * Q, item_t * item) {
if (Q->array == NULL) {
        fprintf(stderr, "Queue is not initialized.\n");
        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.\n");
        return 0;
    }
}
int deque_tail_delete(queue_t * Q, item_t * item) {
    return queue_dequeue(Q, item);
}