luowanqian
3/18/2018 - 8:26 AM

Queue

Queue 基于循环数组实现

#ifndef _QUEUE_H
#define _QUEUE_H

struct Queue;

int is_empty(struct Queue *queue);
int is_full(struct Queue *queue);
struct Queue* create_queue(int capacity);
void dispose_queue(struct Queue **pQueue);
void enqueue(struct Queue *queue, int data);
void dequeue(struct Queue *queue);
int front(struct Queue *queue);

#endif //_QUEUE_H
#include "queue.h"
#include <cstdio>
#include <cstdlib>

struct Queue {
    int capacity;
    int head;
    int tail;
    int *array;
};

int is_empty(struct Queue *queue)
{
    if (queue == NULL) {
        fprintf(stderr, "queue is NULL\n");
        exit(1);
    }

    return (queue->head == queue->tail);
}

int is_full(struct Queue *queue)
{
    if (queue == NULL) {
        fprintf(stderr, "queue is NULL\n");
        exit(1);
    }

    int capacity = queue->capacity;

    return ((queue->tail + 1) % (capacity + 1) == queue->head);
}

struct Queue* create_queue(int capacity)
{
    if (capacity < 1) {
        fprintf(stderr, "Queue size is too small.\n");
        exit(1);
    }

    struct Queue *queue = (struct Queue*)malloc(sizeof(struct Queue));
    if (queue == NULL) {
        fprintf(stderr, "Out of space.\n");
        exit(1);
    }

    queue->array = (int *)malloc(sizeof(int) * (capacity + 1));
    if (queue->array == NULL) {
        fprintf(stderr, "Out of space.\n");
        exit(1);
    }
    queue->capacity = capacity;
    queue->head = 0;
    queue->tail = 0;

    return queue;
}

void dispose_queue(struct Queue **pQueue)
{
    if (pQueue == NULL || *pQueue == NULL)
        return;

    free((*pQueue)->array);
    free(*pQueue);
    *pQueue = NULL;
}

void enqueue(struct Queue *queue, int data)
{
    if (is_full(queue)) {
        fprintf(stderr, "The queue is full.\n");
        exit(1);
    }

    queue->array[queue->tail] = data;
    queue->tail = (queue->tail + 1) % (queue->capacity + 1);
}

void dequeue(struct Queue *queue)
{
    if (queue == NULL) {
        fprintf(stderr, "queue is NULL\n");
        exit(1);
    }

    if (is_empty(queue)) {
        fprintf(stderr, "The queue is empty.\n");
        exit(1);
    }

    queue->head = (queue->head + 1) % (queue->capacity + 1);
}

int front(struct Queue *queue)
{
    if (queue == NULL) {
        fprintf(stderr, "queue is NULL\n");
        exit(1);
    }

    if (is_empty(queue)) {
        fprintf(stderr, "The queue is empty.\n");
        exit(1);
    }

    return queue->array[queue->head];
}