数据结构中队列的基本操作实现

╰半橙微兮° 2022-08-14 02:45 10阅读 0赞

队列是一种特殊的线性表，在这种线性表中，删除运算限定在表的一段进行，而插入运算限定在表的另一端进行，通常，约定把允许插入的一端称为队尾，把允许删除的一端称为队首。队列进出的原则是先进队的先出队，即先进先出原则。队列在计算机程序设计中经常被用到，如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、总结：上述主要描述的是队列的链式存储，只要记住队列的特性，队首删除，队尾插入，就会很轻松的写出队列的基本操作，后续还会继续介绍循环队列以及一些特殊的队列。