队列

队列（Queue）是有限个同类型数据元素的线性序列，是一种 先进先出 的线性表，新加入的数据元素插在队列尾端，出队列的数据元素在队列首部被删除。

队列的顺序实现

// 顺序队列的类型定义
const int Maxsize = 20;
typedef struct seqqueue
{
    DataType data[Maxsize];
    int front, rear;        // front 指向队列首元素的前一个单元，rear 指向实际的队列尾元素单元。 
} SeqQue;

SeqQue SQ;
// 入队列操作
SQ.rear = SQ.rear + 1;
SQ.data[SQ.rear] = x;
// 出队列操作
SQ.front = SQ.front + 1;

// 循环队列的类型定义
typedef struct cycqueue
{
    DataType data[Maxsize];
    int front,rear;
} CycQue;

CycQue CQ; // 循环队列解决了“假上溢”问题
// 循环队列的入队列操作
CQ.rear = (CQ.rear + 1) % Maxsize;
CQ.data[CQ.rear] = x;
// 出队列操作
CQ.front = (CQ.front + 1) % Maxsize; 
// 队列满条件：为了区分队列空条件，队列少用一个元素空间，当只剩下一个单元时就认为队列满，此时，队列尾指针只差一步将追上队列首指针。 
((CQ.rear + 1) % Maxsize == CQ.front) 成立
// 队列空条件
(CQ.rear == CQ.front) 成立

// 队列的初始化
void InitQueue(CycQue *CQ)
{
    CQ->front = 0;
    CQ->rear = 0;
} 

// 判队列空
int EmptyQueue(CycQue *CQ)
{
    // 队列为空，返回 1 
    if (CQ->rear == CQ->front)
        return 1;
    else
        return 0;
} 

// 入队列
int EnQueue(CycQue *CQ, DataType x)
{
    if ((CQ->rear + 1) % Maxsize == CQ->front) {
        error("队列满");
        return 0;
    } else {
        CQ->rear = (CQ->rear + 1) % Maxsize;
        CQ->data[CQ->rear] = x;
        return 1;
    }
} 

// 出队列
int OutQueue(CycQue *CQ)
{
    if (EmptyQueue(CQ)) {
        error("队列空");
        return 0;
    } else {
        CQ->front = (CQ->front + 1) % Maxsize;
        return 1;
    }
}

// 取队列首元素
DataType GetHear(CycQue *CQ)
{
    if (EmptyQueue(CQ))
        return NULLData; // 返回空数据标志
    else 
        return CQ->data[(CQ->front + 1) % Maxsize]; 
}

队列的链接实现

// 链队列的类型定义
typedef struct LinkQueueNode
{
    DataType data;
    struct LinkQueueNode *next;
} LkQueNode;

typedef struct LkQueue
{
    LkQueNode *front, *rear; // 队列头指针和尾指针。头指针指向链表的头结点，头结点的 next 域指向队列首结点，尾指针指向队列尾结点，即单链表的最后一个结点。 
} LkQue;

LkQue LQ;

// 队列的初始化
void InitQueue(LkQue *LQ)
{
    LkQueNode *temp;
    temp = (LkQueNode *)malloc(sizeof(LkQueNode)); // 生成队列的头结点
    LQ->front = temp;                              // 队列头指针指向队列头结点
    LQ->rear = temp;                               // 队列尾指针指向队列尾结点 
    (LQ->front)->next = NULL; 
} 

// 判队列空 
int EmptyQueue(LkQue *LQ)
{
    if (LQ->rear == LQ->front)
        return 1;
    else 
        return 0;
} 

// 入队列
void EnQueue(LkQue *LQ, DataType x)
{
    LkQueNode *temp;
    temp = (LkQueNode *)malloc(sizeof(LkQueNode));
    temp->data = x;
    temp->next = NULL;
    (LQ->rear)->next = temp; // 新结点入队列
    LQ->rear = temp;         // 置新的队列尾结点 
} 

// 出队列
int OutQueue(LkQue *LQ)
{
    LkQueNode *temp;
    if (EmptyQueue(LQ)) {
        error("队列空");
        return 0;
    } else {
        temp = (LQ->front)->next;       // 使 temp 指向队列的首结点
        (LQ->front)->next = temp->next; // 修改头结点的指针域指向新的首结点
        if (temp->next == NULL) {
            LQ->rear = LQ->front;       // 无首结点时，front 和 rear 都指向头结点 
        } 
        free(temp);
        return 1; 
    }
} 

// 取队列首元素
DataType GetHead(LkQue *LQ)
{
    LkQueNode *temp;
    if (EmptyQueue(LQ)) {
        return NULLData;
    } else {
        temp = (LQ->front)->next;
        return temp->data; // 返回队列首结点元素，即头结点的指针域指向的结点 
    }
}