队列：出队、入队、销毁、清空等

小鱼儿 2022-09-26 04:58 172阅读 0赞

具体的队列算法实现代码。

将N个随机数入队。

实现出队、再次入队、打印队列等方法。

内存泄露是个大问题。

记得free(p);p=NULL

p指针本身是在栈上存储，不过p所指向的空间在堆上，所以需要程序员自行释放，防止内存泄露。

free(p);之后p指针仍然存在，如果堆上原来指向的内存没有被重写，p还是可以的输出的，以防p所指向的内存重写，p相当于野指针，需要p=NULL；

源代码如下：

#include<iostream>
    #include<stdlib.h>
    using namespace std;
    #define OK 1
    typedef int QElemType;
    typedef int Status;
    typedef struct QNode{
    	QElemType data;
    	struct QNode *next;
    };//定义节点
    typedef struct{
    	 struct QNode * rear;//尾指针
    	 struct QNode * front;//头指针
    	 int Length;
    }LinkQueue;//定义队列
    Status InitQueue(LinkQueue &Q);//初始化队列
    Status EnQueue(LinkQueue &Q,QElemType e);//入队在队尾插入元素e
    Status ShowQueue(LinkQueue Q);//打印当前队列元素
    Status GetTop(LinkQueue Q,QElemType &e);//获取当前队头元素，并用e返回
    Status DeQueue(LinkQueue &Q);//出队
    Status IsEmptyQueue(LinkQueue Q);//判断是否为空，队空返回1。
    Status ClearQueue(LinkQueue &Q);//清空队列
    Status DestroyQueue(LinkQueue &Q);//销毁队列
    
    Status InitQueue(LinkQueue &Q){//传地址，修改Q	
    	Q.rear=Q.front=(QNode *)malloc(sizeof(QNode));//指向头结点
    	if(!Q.rear)
    		cout<<"Error Overflow!"<<endl;
    	Q.front->next=NULL;
    	Q.Length=0;
    	return 0;
    }
    Status EnQueue(LinkQueue &Q,QElemType e){
    	//在队尾插入新的节点，需要开辟空间
    	QNode *p=(QNode *)malloc(sizeof(QNode));
    	if(!p) cout<<"分配内存失败"<<endl;
    	p->data=e;
    	p->next=NULL;
    	Q.rear->next=p;
    	Q.rear=p;
    	if(Q.front->next==NULL)
    		Q.front->next=p;
    	Q.Length++;
    	return 0;
    }
    Status ShowQueue(LinkQueue Q){
    	QNode *p;
    	p=Q.front->next;//p指向第一个元素
    	if(Q.front==Q.rear)
    	{
    		cout<<endl<<"当前队列为空！没有元素可以显示"<<endl;
    		return 0;
    	}
    		
    	cout<<endl<<"当前队列共计 "<<Q.Length<<" 个元素"<<endl;
    	cout<<"------------------------------当前队列元素为：-------------------"<<endl;
    	while(p!=Q.rear)
    	{
    	cout<<p->data<<" ";
    	p=p->next;//不能用p++
    	}
    	cout<<p->data<<endl;
    	return 0;
    }
    Status GetTop(LinkQueue Q,QElemType &e){
    	e=Q.front->next->data;
    	return OK;
    }
    Status DeQueue(LinkQueue &Q){
    	if(Q.front==Q.rear)
    		cout<<endl<<"队列为空，没有元素可以删除！"<<endl;
    	else 
    	{
    		Q.front->next=Q.front->next->next;
    		Q.Length--;
    	}	
    	return OK;
    }
    Status IsEmptyQueue(LinkQueue Q){
    	if(Q.front==Q.rear)
    		return 1;
    	else
    		return 0;
    }
    Status DestroyQueue(LinkQueue &Q){
    	 if(Q.front!= NULL) 
    	 { 
    		 Q.rear=Q.front->next;
    		 free(Q.front);
    		 Q.front=Q.rear; //释放一块内存要做两点：1.释放指向它的指针。2.将该指针指向空
    	 }		
        return OK;
    }
    Status ClearQueue(LinkQueue &Q)  
    { // 将Q清为空队列   
      struct QNode *p,*q;  
      Q.rear=Q.front;  
      p=Q.front->next;  
      Q.front->next=NULL;//只留下头结点   
      while(p)  
      {  
        q=p;  
        p=p->next;  
        free(q);  
      }  
      return OK;
    } 
    
    int main(int argc,char *argv[]){
    	LinkQueue Q;//结构体Q	
    	InitQueue(Q);
    	QElemType e;
    	e=rand()%100;
    	int n;//随机插入队列元素的数目。
    	cout<<"请输入队列随机元素数目："<<endl;
    	cin>>n;
    	while(n--)
    	{
    		e=rand()%100;
    		EnQueue(Q,e);//进队n个元素	
    	}
    	
    	GetTop(Q,e);
    	cout<<"当前队头元素为："<<e;
    	ShowQueue(Q);
    	
    	DeQueue(Q);
    	cout<<endl<<"-----------------队头元素出队后：------------------------"<<endl;
    	GetTop(Q,e);
    	cout<<"当前队头元素为：  "<<e;
    	ShowQueue(Q);
    	if(!IsEmptyQueue(Q))
    		cout<<"队列非空"<<endl;
    
    	e=rand()%50;
    	cout<<endl<<"入队的元素为"<<e<<endl;
    	EnQueue(Q,e);//再次入队	
    	GetTop(Q,e);
    	cout<<"当前队头元素为："<<e;
    	ShowQueue(Q);
    	
    	//清空
    	cout<<endl<<"-----------清空队列--------";
    	DestroyQueue(Q);
    	ShowQueue(Q);
    
    	return 0;
    }

实现结果截图：

![20160921225804133][]

[20160921225804133]: /images/20220717/580b35904e744f7194056a53734e808f.png