数据结构中队列的基本操作实现_队列变为指针

       队列是一种特殊的线性表，在这种线性表中，删除运算限定在表的一段进行，而插入运算限定在表的另一端进行，通常，约定把允许插入的一端称为队尾，把允许删除的一端称为队首。队列进出的原则是先进队的先出队，即先进先出原则。队列在计算机程序设计中经常被用到，如Windows操作系统的消息队列。

       接下来我们看一下队列的数据结构，队列可以采用链式或顺序存储结构来描述，这里采用链式结构来进行表达。由于队列需要在队首以及队尾进行删除和插入操作，所以需要设置两个指针来表示队列，通常队尾指针指向最后进入队列的元素，为了便于表示空队列，专门设置了一个头结点，当队列为空时，头指针和尾指针均指向头结点，队列的基本操作有，构建一个空队列、插入一个元素、删除一个元素、计算队列的长度、销毁队列。队列的结构如下所示：

<span style="font-size:18px;">typedef struct lnode{
    elementype  data;
    lnode* next;
}lnode;
 
typedef struct linkque{
    lnode* front;
    lnode* rear;
}linkque;
</span>

1、构建一个空队列。

<span style="font-size:18px;">
int QueueInti(linkque& q)
{
    //创建一个头结点;
    lnode* head=(lnode*)malloc(sizeof(lnode));
    if(!head)
    {
        return 0;
    }
    q.front=head;
    q.rear=head;
    
    q.front->next=NULL;
 
    retuen 1;    
}
</span>

2、插入一个元素，插入一个元素把该元素插入到队列的尾部，并且修改尾部指针指向刚插入的元素。

int QueueInsert(linkque& q,elementype e)
{
	lnode* p=(lnode*)malloc(sizeof(lnode));
	
	if(!p)
	{
		return 0
	}
 
	p->data=e;
	
	q.rear->next=p;
	
	q.rear=p;
 
	return 1;
}

3、从链式队列q中删除一个元素，如果队列非空，则删除队列q中的队首元素，用e返回其值。队列中设置了头结点，如果队列中只有一个元素，删除后队列变为空队列，需要将队尾指针指向头结点。

int QueueDelete(linkque& q,elementype &e)
{
	if(q.front==q.rare)
	{
		return 0;
	}
	
	lnode* p=q.front->next;
	
	e=p->data;
	
	q.front->next=p->next;
	
	if(q.rare==p) q.rare=q.front;
 
	free(p);
	
	return 1;	
}

4、计算队列的长度，求队列的长度，即计算队列中元素的个数。

int QueueLength(linkque& q)
{
	int i=0;
	
	if(q.front==q.rara) return 0;
	
	lnode* p=q.front->next;	
 
	while(p)
	{
		++i;
		p=p->next;	
	}
	
	return (i);
}
 

5、销毁一个队列，销毁一个队列实际上是从链式队列的头部开始，将所有的节点（包括头结点）的空间都进行回收。如下：

int QueueDestory(linkque& q)
{
	lnode* p;
	
	while(q.front)
	{
		q.rare=q.front->next;
		free(q.front);
 
		q.front=q.rare;		
	}	
 
	return 1;
}

6、总结：上述主要描述的是队列的链式存储，只要记住队列的特性，队首删除，队尾插入，就会很轻松的写出队列的基本操作，后续还会继续介绍循环队列以及一些特殊的队列。