队列的链式实现（带有头结点）

迷南。 2022-12-04 09:22 158阅读 0赞

链式队列是采用链式存储结构实现的队列。

## 存储结构 ##

typedef struct Qnode{
        
    	int data;
    	struct Qnode *next;
    } *Quene;     //每一个结点的结构 
    
    typedef struct{
        
    	Quene front;    //队头指针 
    	Quene rear;     //队尾指针 
    }LinkQuene;

初始化  
![在这里插入图片描述][20200907201813841.png_pic_center]

//初始化
    void initQuene(LinkQuene &Q){
        
    	Q.front = Q.rear = new Qnode;   //队头队尾指针都指向新创建的空结点 
    	Q.front->next = NULL;           //将队头指针指向的结点的next域指向空 
    }

入队  
![在这里插入图片描述][20200907202203141.png_pic_center]

//入队
    void push(LinkQuene &Q,int e){
        
    	//新建结点 指针p指向新结点 
    	Qnode *p = new Qnode;
    	//将新结点的数据域置为e
    	p->data = e;
    	//将新结点插入到队尾
    	p->next = NULL;
    	Q.rear->next = p;
    	//修改队尾指针 
    	Q.rear = p;
    }

出队  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center]

//出队
    bool pop(LinkQuene &Q){
        
    	//判断队列是否为空
    	if(isnull(Q)){
        
    		return false;
    	}
    	
    	else{
        
    	//临时保存队头指针指向的结点
    	Qnode *temp = Q.front->next;
    	//修改头结点指针域
    	Q.front->next = temp->next;
    	//判断出队的结点是否为最后一个结点，若是则将队头队尾指针重新赋值 
    	if(Q.rear == temp) Q.rear = Q.front;
    	//释放临时保存的结点 
    	delete temp;
    	return true;
    }
    }

取队头元素

int getHead(LinkQuene &Q){
        
    	if(!isnull(Q)){
        
    		return Q.front->next->data;
    	}
    }

总结测试

#include <iostream>
    using namespace std;
    //存储结构
    typedef struct Qnode{
        
    	int data;
    	struct Qnode *next;
    } *Quene;     //每一个结点的结构 
    
    typedef struct{
        
    	Quene front;    //队头指针 
    	Quene rear;     //队尾指针 
    }LinkQuene;
    //初始化
    void initQuene(LinkQuene &Q){
        
    	Q.front = Q.rear = new Qnode;   //队头队尾指针都指向新创建的空结点 
    	Q.front->next = NULL;           //将队头指针指向的结点的next域指向空 
    }
    //入队
    void push(LinkQuene &Q,int e){
        
    	//新建结点 指针p指向新结点 
    	Qnode *p = new Qnode;
    	//将新结点的数据域置为e
    	p->data = e;
    	//将新结点插入到队尾
    	p->next = NULL;
    	Q.rear->next = p;
    	//修改队尾指针 
    	Q.rear = p;
    }
    //判空
    bool isnull(LinkQuene &Q){
        
    	if(Q.rear == Q.front) return true;
    	return false;
    }
    //出队
    bool pop(LinkQuene &Q){
        
    	//判断队列是否为空
    	if(isnull(Q)){
        
    		return false;
    	}
    	
    	else{
        
    	//临时保存队头指针指向的结点
    	Qnode *temp = Q.front->next;
    	//修改头结点指针域
    	Q.front->next = temp->next;
    	//判断出队的结点是否为最后一个结点，若是则将队头队尾指针重新赋值 
    	if(Q.rear == temp) Q.rear = Q.front;
    	//释放临时保存的结点 
    	delete temp;
    	return true;
    }
    }
    //取队头元素
    int getHead(LinkQuene &Q){
        
    	if(!isnull(Q)){
        
    		return Q.front->next->data;
    	}
    }
    int main()
    {
        
    	LinkQuene Q;
    	initQuene(Q);
    	push(Q,1);
    	push(Q,2);
    	push(Q,3);
    	cout << getHead(Q) << endl;
    	pop(Q);
    	cout << getHead(Q) << endl;
    	pop(Q);
    	cout << getHead(Q) << endl;
    	return 0;
     }

运行结果  
![在这里插入图片描述][20200907202825381.png_pic_center]

[20200907201813841.png_pic_center]: /images/20221123/b23690ccd042431fb50382550213ce8f.png
[20200907202203141.png_pic_center]: /images/20221123/24328c994cc54b85a77eaf7a580e13f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/1fafdff8a2b7402a87362a96cc3f6281.png
[20200907202825381.png_pic_center]: /images/20221123/ee5bd094e14240bf8ca10ff0a5a210b2.png