编辑代码

//4.2.1 链队的定义
typedef struct qnode
{
    ElemType data;
    struct qnode * node;
}QNode;                                     //声明链队数据结点类型

typedef struct
{
    QNode * front;                          //队头指针
    QNode * rear;                           //队尾指针
}LiQueue;                                   //声明链队结点类型

//4.2.2 初始化队列
void InitQueue(LiQueue * &lqu)
{
    lqu = (LiQueue * )malloc(sizeof(LiQueue));
    lqu -> front = lqu -> rear = NULL;      //队头队尾指针置为 NULL
}

//4.2.3 判断队空
int QueueEmpty(LiQueue * lqu)
{
    return(lqu -> rear == NULL)
}

//4.2.4 进队
void EnQueue(LiQueue * &lqu,ElemType x)
{
    QNode * p;
    p = (QNode * )malloc(sizeof(QNode));
    p -> data = x;
    p -> next = NULL;
    if(lqu -> rear == NULL)                 //若链队为空，则新结点即是队头结点也是队尾结点
        lqu -> front = lqu -> rear = p;
    else
    {
        lqu -> rear -> next = p;            //将结点 p 链到队尾，rear 指向它
        lqu -> rear = p;
    }
}

//4.2.5 出队
int DeQueue(LiQueue * &lqu,ElemType &x)
{
    QNode * p;
    if(lqu -> rear == NULL)                 //队列为空
        return 0;
    p = lqu -> front;                       //p 指向第一个数据结点
    if(lqu -> front == lqu -> rear)         //队列中只有一个结点时
        lqu -> front = lqu -> next = NULL;
    else                                    //队列中有多个结点时
        lqu -> front = lqu -> front -> next;
    x = p -> data;
    free(p);
    return 1;
}