队列

队列（queue）是一种先进先出的、操作受限的线性表。

ADT 队列 (Queue)
Data
    同线性表，但元素只能队尾入，对头出。
Operation
    init_queue(*Q) :初始化操作,建立一个空队列Q。
    clear_queue(*Q) :将队列Q清空。
    queue_is_empty(Q) :若队列Q为空，返回true，否则返回false。
    enqueue(*Q,e) :若队列Q存在，插入新元素e到队列Q中并成为对尾元素 。
    dequeue(*Q,*e) :删除队列Q中队头元素，并用e返回其值。
endADT

和栈一样存储方式也分为顺序和链式。

链式队列实现

构建

#define OK      true
#define ERROR   false
typedef bool STATUS;
typedef int Elem_Type;

typedef struct Node
{
    Elem_Type data;
    struct Node *next;
}Node;

typedef struct CH_Queue
{
    Node *head;
    Node *tail;
}CH_Queue;
CH_Queue queue;

初始化

STATUS init_queue(CH_Queue *q)
{
    q->head = NULL; 
    q->tail = NULL;      
}

清空

STATUS clear_queue(CH_Queue *q)
{
    Node *temp = NULL;
    q->tail = NULL;
    while(q->head != NULL)
    {
        temp = q->head;
        q->head = q->head->next;
        free(temp);
    }
}

判空

bool queue_is_empty(CH_Queue q)
{
    if(q.head == NULL)
    {
        return true;
    }
    return false;
}

入队

STATUS enqueue(CH_Queue *q, Elem_Type e)\
{
    Node *temp = (Node *)malloc(sizeof(Node));
    temp->data = e;
    temp->next = NULL;
    if(q->tail == NULL)
    {
        q->head = q->tail = temp;
    }
    else
    {
        q->tail->next = temp;
        q->tail = temp;
    }
    return OK;
}

出队

STATUS dequeue(CH_Queue *q, Elem_Type *e)
{
    Node *temp = q->head;
    *e = q->head->data;
    q->head = q->head->next;
    free(temp);
    return OK;
}

顺序队列实现

由于顺序存储结构移动麻烦且无法动态扩容，因此要使用下标模拟指针从而模拟循环。

构建

#define OK      true
#define ERROR   false
typedef bool STATUS;
typedef int ElemType;
#define MAX_SIZE    100

typedef struct SQQueue
{
    ElemType data[MAX_SIZE];
    int head;
    int tail;
    int size;
}SQQueue;
SQQueue queue;

初始化和清空

STATUS init_queue(SQQueue *q)
{
    q->head = 0; 
    q->tail = 0;
    q->size = 0;      
}

STATUS clear_queue(SQQueue *q)
{
    init_queue(q);
}

判空

bool queue_is_empty(SQQueue q)
{
    if(q.size == 0)
    {
        return true;
    }
    return false;
}

入队

STATUS enqueue(SQQueue *q, ElemType e)
{
    if(q->size >= MAX_SIZE)
        return ERROR;
    if(q->size == 0)
        q->tail -=1;
    (q->size)++;
    q->tail = (q->tail + 1) % MAX_SIZE;
    q->data[q->tail] = e;
    return OK;
}

出队

STATUS dequeue(SQQueue *q, ElemType *e)
{
    if(q->size <= 0)
        return ERROR;
    (q->size)--;
    *e = q->data[q->head];
    q->head = (q->head + 1) % MAX_SIZE;
    return OK;
}