DS之链队

DS之链队

链队概述

用链式表示的队列简称链队。一个链队列显然需要两个分别指示队头和队尾的指针(分别称为头指针和尾指针)才能唯一确定。为了操作方便，我们像给线性表的单链表的添加头结点那样也给链队列添加一个头结点，并令头指针指向头结点。因此，空的链队列的判决条件为头指针和尾指针均指向头结点。

链队列的操作即为单链表的插入和删除操作图解

元素x入队列

元素y入队列

元素x出队列

链队的基本操作

1操作前准备

#include 
using namespace std;
#include   
#include   
#define OK 1  
#define ERROR 0  
#define OVERFLOW -2  
#define TRUE 1  
#define FALSE 0  
#define INFEASIBLE -1    
typedef int Status;//重新定义Status为int型  
typedef int QElemType;//重新定义QElemType为int型
typedef struct QNode{//重新定义一个结点结构  
    QElemType   data;  
    struct QNode  *next;  
}QNode, *QueuePtr;  
typedef struct {//定义的一个链队  
    QueuePtr  front;//队头指针     
    QueuePtr  rear;//队尾指针  
}LinkQueue;//定义的一个结构变量 

1初始化队列

<span style="font-size:18px;"> </span>//1初始化队列  
Status InitQueue(LinkQueue &Q)  
{  
    Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));   
    if(!Q.front)  
    {  
        exit(OVERFLOW);  
    }  
    Q.front->next=NULL;  
    return OK;  
} 

2判断链队是否为空

//2判断链队是否为空
Status QueueEmpty(LinkQueue Q)
{
	return (Q.front==Q.rear);
}

3求链队长度

//3求队列长度
Status QueueLength(LinkQueue Q)
{
	int i=0;
	QueuePtr p=Q.front;
	while(p!=Q.rear)
	{
		i++;
		p=p->next;
	}
	return i;
}

4取队头元素

//4取队头元素
Status GetHead(LinkQueue Q,QElemType &e)
{
	if(Q.front==Q.rear)
	{
		return ERROR;
	}
	e=Q.front->next->data;
	return OK;
}

5清空队列

//5清空队列
Status ClearQueue(LinkQueue &Q)
{
	Q.rear=Q.front;
	QueuePtr p=Q.front->next;
	Q.front->next=NULL;
	while(p)
	{
		QueuePtr q=p->next;
		free(p);
		p=q;
	}
	return OK;
}

6销毁队列

//6销毁队列
Status DestroyQueue(LinkQueue &Q)
{
	while(Q.front)
	{
		Q.rear=Q.front->next;
		free(Q.front);
		Q.front=Q.rear;
	}
	return OK;
}

7入队列

//7入队列  
Status EnQueue(LinkQueue &Q,QElemType e)  
{  
    QueuePtr p=(QueuePtr)malloc(sizeof(QNode));  
    if(!p)   
    {  
        exit(OVERFLOW);  
    }  
    p->data=e;   
    p->next=NULL;  
    Q.rear->next=p;  
    Q.rear=p;  
    return OK;   
}  

8出队列

//8出队列  
Status DeQueue(LinkQueue &Q,QElemType &e)  
{  
   if(Q.front==Q.rear)   
   {  
       return ERROR;  
   }  
   QueuePtr p=(QueuePtr)malloc(sizeof(QNode));  
   p=Q.front->next;  
   e=p->data;  
   Q.front->next=p->next;  
   if(Q.rear==p)   
   {  
       Q.rear=Q.front;  
   }  
   free(p);  
   return OK;  
}