#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;
}