和线性表类似，队列也可以有两种存储表示
用链表表示的队列简称为链队列，一个链队列显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。
链队列的操作即为单链表的插入和删除操作的特殊情况，只是需要修改尾指针或头指针
一般情况下，删除队列头元素时仅需修改头结点中的指针，但当队列中最后一个元素被删除后，队列表尾指针也丢失了，因此需对队尾指针重新赋值（指向头结点）
一：初始化操作
初始化队列，构造一个空队列
typedef struct LinkNode{ //链式队列结点 ElemType data; struct LinkNode *next;}LinkNode;
typedef struct{ //链式队列 LinkNode *front, *rear //队列的队头和队尾指针}LinkQueue;
//初始化队列(带头结点)void InitQueue(LinkQueue &Q){ //初始化 front、rear都指向头结点 Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode)); Q.front -> next = NULL;}
viod testLinkQueue(){ LinkQueue Q; //声明一个队列 InitQueue(Q); //初始化队列}
//判断队列是否为空bool IsEmpty(LinkQueue Q){ if(Q.front == Q.rear){ return true; }else{ return false; }}
复制代码
入队操作：
typedef struct LinkNode{ //链式队列结点 ElemType data; struct LinkNode *next;}LinkNode;
typedef struct{ //链式队列 LinkNode *front, *rear //队列的队头和队尾指针}LinkQueue;
//新元素入队(带头结点)void EnQueue(LinkQueue &Q, ElemType x){ LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = x; s->next = NULL; Q.rear->next = s; //新结点插入到rear之后 Q.rear = s; //修改表尾指针}
复制代码
出队操作
typedef struct LinkNode{ //链式队列结点 ElemType data; struct LinkNode *next;}LinkNode;
typedef struct{ //链式队列 LinkNode *front, *rear //队列的队头和队尾指针}LinkQueue;
//队头元素出队操作(带头结点)bool DEQueue(LinkQueue &Q, ElemType &x){ if(Q.front == Q.rear){ return //空队列 } LinkNode *p = Q.front->next; x = p->data; //用变量x返回队头元素 Q.front->nexy = p->nexy; //修改头结点的next指针 if(Q.rear == p){ //此次是最后一个结点出队 Q.rear = Q.front //修改rear指针 } free(p); //释放结点空间 return true;}
复制代码
评论