13.7_link_queue

#include <iostream>
#include <stdlib.h>

typedef int elemtype;
typedef struct link_node{
    elemtype data;
    struct link_node *next;
}link_node;

typedef struct {
    link_node *front,*rear;  //链表头，链表尾，也可以成为队头队尾
}link_queue;         //先进先出

//队列的初始化，使用的是带头结点的链表来实现的
void init_queue(link_queue &Q)
{
    Q.front=Q.rear=(link_node*) malloc(sizeof (link_node));
    Q.front->next=NULL;
}

//入队
void en_queue(link_queue &Q,elemtype x)
{
    link_node *pnew=(link_node*) malloc(sizeof (link_node));
    pnew->data=x;
    pnew->next=NULL;   //要让next为NULL
    Q.rear->next=pnew;   //尾指针的next指向pnew，因为从尾部入队
    Q.rear=pnew;    //rear要只想新的尾部

}

bool de_queue(link_queue &Q,elemtype &x)
{
    if(Q.rear==Q.front)   //队列为空
    {
        return false;
    }
    link_node* q=Q.front->next;   //拿到第一个节点，存入q
    x=q->data;     //获取要出队的元素值
    Q.front->next=q->next;//让第一个节点断链
    if(Q.rear==q)      //链表只剩一个节点时，被删除后，要改变rear
    {
        Q.rear=Q.front;
    }
    free(q);
    return true;
}
//通过链表实现队列
int main() {
    link_queue Q;
    init_queue(Q);
    en_queue(Q,3);
    en_queue(Q,4);
    en_queue(Q,6);
    en_queue(Q,5);
    en_queue(Q,7);
    elemtype element;
    bool ret;
    ret= de_queue(Q,element);
    if(ret)
    {
        printf("DeQueue success element = %d\n",element);
    } else{
        printf("DeQueue failed\n");
    }
    de_queue(Q,element);
    ret= de_queue(Q,element);
    if(ret)
    {
        printf("DeQueue success element = %d\n",element);
    } else{
        printf("DeQueue failed\n");
    }
    return 0;
}