37.2° Blog

注意：

• 第一个元素入队时的处理
• 最后一个元素出队时的处理

1.实现

1.1 定义

typedef int ElemType;
#define MaxSize 50
typedef struct LinkNode
{
    ElemType data;
    struct LinkNode* next;
}LinkNode;
typedef struct
{
    LinkNode* front;              // 队列头指针
    LinkNode* rear;               // 队列尾指针
}LinkQueue;

1.2 初始化

// 初始化（带头结点）
void initQueue(LinkQueue& Q)
{
    // 建立头结点
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next = NULL;   // 初始化为空
}

1.3 入队

// 入队（带头结点）
void enQueue(LinkQueue& Q, ElemType e)
{
    LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = e;
    s->next = NULL;     // 创建新结点，插入到链尾
    Q.rear->next = s;   // 新结点插入到rear之后
    Q.rear = s;         // 修改表尾指针
}

1.4 出队

// 出队（带头结点）
bool deQueue(LinkQueue& Q, ElemType& e)
{
    if(Q.front == Q.rear)   // 队空
        return false;
    LinkNode* p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if(Q.rear == p)
        Q.rear = Q.front;   //  若原队列中只有一个结点，删除之后变为空 
    free(p);
    return false;
}

1.5 判空

// 判队空（带头结点）
bool queueEmpty(LinkQueue Q)
{
    if(Q.front == Q.rear)
        return true;
    else 
        return false;
}