抽象数据类型(ADT)-队列

队列定义

队列也是一种特殊的线性表，它只允许在表的一端进行插入，另一端进行删除，遵循先进先出(FIFO, First In First Out)的原则，可以进行插入的一端称为队首，可进行删除的一端称为队尾。向队列中加入数据叫入队，从队列中取出数据叫做出队。数据结构及操作如图所示：

队列实现

队列需要实现的接口有创建队列，销毁队列，判断队列是否为空，入队，出队，取队尾元素值。实现方法可以通过循环列表和链表实现，这里我们用两种方法分别实现下。同样，我们用 define ELEMENT_TYPE int 来区别不同的元素类型。

循环列表实现队列

循环列表实现时需要首先申请一个元素列表，用于存储队列元素，同时记录队首索引（front）和队尾索引（rear），再记录一个队列元素个数最大值和元素总数。

#define QUEUE_OK    (0)
#define QUEUE_FAIL    (-1)

typedef struct {
    ELEMENT_TYPE *queueArray;
    int capacity;
    int size;
    int front;
    int rear;
}ttQueue;

ttQueue* createQueue(int capacity);
void disposeQueue(ttQueue* queue);
bool queueEmpty(ttQueue* queue);
int enqueue(ttQueue* queue, ELEMENT_TYPE data);
ELEMENT_TYPE dequeue(ttQueue* queue);
ELEMENT_TYPE queueFront(ttQueue* queue);

接口实现：

ttQueue* createQueue(int capacity) 
{
    if (capacity <= 0)
        return NULL;
    ttQueue* queue = (ttQueue*) malloc(sizeof(ttQueue));
    if (queue == NULL)
        return queue;
    queue->queueArray = (ELEMENT_TYPE*) malloc(sizeof(ELEMENT_TYPE) * capacity);
    if (queue->queueArray == NULL) {
        free(queue);
        return NULL;
    }
    queue->capacity = capacity;
    queue->size = 0;
    queue->front = 0;
    queue->rear = 0;
    return queue;
}

void disposeQueue(ttQueue* queue)
{
    if (queue == NULL)
        return ;
    if (queue->queueArray != NULL)
        free(queue->queueArray);
    free(queue);
}

bool queueEmpty(ttQueue* queue)
{
    if (queue == NULL)
        return false;
    return queue->size == 0;
}

static int queueNext(int index, int capacity)
{
    return (index + 1) % capacity;
}

static bool queueFull(ttQueue* queue)
{
    return queue->size == queue->capacity;
}

int enqueue(ttQueue* queue, ELEMENT_TYPE data)
{
    if (queue == NULL || 
        queue->queueArray == NULL || 
        queue->size > queue->capacity || 
        queue->front > queue->capacity || 
        queue->rear > queue->capacity)
        return QUEUE_FAIL;
    if (queueFull(queue)) 
        return QUEUE_FAIL;
    queue->queueArray[queue->front] = data;
    queue->front = queueNext(queue->front, queue->capacity);
    queue->size++;
    return QUEUE_OK;
}

ELEMENT_TYPE dequeue(ttQueue* queue)
{
    if (queue == NULL || 
        queue->queueArray == NULL || 
        queue->size > queue->capacity || 
        queue->front > queue->capacity || 
        queue->rear > queue->capacity)
        return QUEUE_FAIL;
    if (queueEmpty(queue))
        return QUEUE_FAIL;
    ELEMENT_TYPE data = queue->queueArray[queue->rear];
    queue->rear = queueNext(queue->rear, queue->capacity);
    queue->size--;
    return data;
}

ELEMENT_TYPE queueFront(ttQueue* queue)
{
    if (queue == NULL || 
        queue->queueArray == NULL || 
        queue->size > queue->capacity || 
        queue->front > queue->capacity || 
        queue->rear > queue->capacity)
        return QUEUE_FAIL;
    if (queueEmpty(queue))
        return QUEUE_FAIL;
    return queue->queueArray[queue->rear];
}

链表实现队列

链表实现队列时需要在链表头中记录队首元素指针和队尾元素指针，以便进行入队和出队。

typedef struct queue_node{
    struct queue_node* next;
    ELEMENT_TYPE data;
}queueNode;

typedef struct {
    queueNode* first;
    queueNode* last;
    int size;
}ttQueue;

各接口实现：

ttQueue* createQueue(int capacity)
{
    ttQueue* queue = (ttQueue*) malloc(sizeof(ttQueue));
    if (queue == NULL)
        return NULL;
    queue->first = NULL;
    queue->last = NULL;
    queue->size = 0;
    return queue;
}

void disposeQueue(ttQueue* queue)
{
    if (queue == NULL)
        return;
    for (queueNode* node = queue->first; node != NULL; ) {
        queueNode* next = node->next;
        free(node);
        node = next;
    }
    free(queue);
}

bool queueEmpty(ttQueue* queue)
{
    if (queue == NULL)
        return false;
    return queue->size == 0;
}

int enqueue(ttQueue* queue, ELEMENT_TYPE data)
{
    if (queue == NULL)
        return QUEUE_FAIL;
    queueNode* node = (queueNode*) malloc(sizeof(queueNode));
    if (node == NULL)
        return QUEUE_FAIL;
    node->data = data;
    node->next = NULL;
    if (queue->first == NULL) {
        queue->first = node;
        queue->last = node;
    } else {
        queue->last->next = node;
        queue->last = node;
    }
    queue->size++;
    return QUEUE_OK;
}

ELEMENT_TYPE dequeue(ttQueue* queue)
{
    if (queue == NULL || queue->size == 0 || queue->first == NULL)
        return (ELEMENT_TYPE)0;
    queueNode* node = queue->first;
    ELEMENT_TYPE data = node->data;
    queue->first = node->next;
    if (queue->first == NULL)
        queue->last = NULL;
    free(node);
    queue->size--;
    return data;
}

ELEMENT_TYPE queueFront(ttQueue* queue)
{
    if (queue == NULL || queue->size == 0 || queue->first == NULL)
        return (ELEMENT_TYPE)0;
    return queue->first->data;
}

参考：

<数据结构与算法分析-C语言实现> P3