C++链队：创建链式队列/初始化、入队、出队、销毁、取队头

末蓝、 2022-12-22 14:30 284阅读 0赞

**链队列：队列的链接存储结构称为链队列，通常用单链表表示。其结点的结构与单链表的结点结构相同。根据队列的先进先出特性，为了操作上的方便，设置队头指针指向链队列的头结点，队尾指针指向终端结点。**  
**C++链队列的实现：**

> **1.创建链式队列**

typedef int DataType;
    struct Node{
    	DataType data;
    	Node *next;
    };
    class LinkQueue{
    	public:
    		LinkQueue();//初始化空的链表队列
    		~LinkQueue();//释放链队列的存储空间
    		void EnQueue(DataType x);//入队操作，将元素x出队
    		DataType DeQueue();//出队操作，将队头元素出队 
    		DataType GetHead();//取链队列队头元素
    		int Empty();//判断队列是否为空
    	private:
    		Node *front,*rear;//队头和队尾指针 
    		int Len;
    };
    //链队列基本操作的实现本质上是单链表操作的简单化，且时间复杂度均为O(1)

> **2.构造函数**

//构造函数----链队列的初始化
    LinkQueue::LinkQueue(){
    	Node *s=nullptr;
    	s=new Node;
    	s->next = nullptr;
    	front=rear=s;//将队头指针和队尾指针都指向头结点s 
    }

> **3.析构函数**

//析构函数----链队列的销毁【链队列是动态存储分配，需要释放链队列的所有结点的存储空间】 
    LinkQueue::~LinkQueue(){
    	while(front){//释放每一个结点的存储空间 
    		rear=front->next;
    		delete front;
    		front=rear;
    	}
    }

> ** 4.入队操作**

//入队操作----链队列的插入操作只需考虑在链表的尾部进行
    void LinkQueue::EnQueue(DataType x){
    	Node *s=nullptr;
    	s=new Node;
    	s->data=x;s->next=nullptr;
    	rear->next=s;rear=s;//将结点s插入到队尾 
    	Len++;
    }

> **5.出队操作**

//出队操作----链队列的删除操作只需考虑在链表的头部进行 
    DataType LinkQueue::DeQueue(){
    	DataType x;
    	Node *p=nullptr;
    	if(rear == front) throw "下溢";
    	p=front->next;x=p->data;
    	front->next=p->next;
    	//if(!p->next)
    	if(rear==p) front=rear;
    	delete p;
    	Len--;
    	return x;
    }

> **6.取队头元素**

DataType LinkQueue::GetHead(){
    	return front->next->data;
    }

> **7.判断队列是否为空**

int LinkQueue::Empty(){
    	if(front==rear) return 1;
    	else return 0;
    }

**C++链队列完整代码 ：**

#include <iostream>
    using namespace std;
    typedef int DataType;
    struct Node{
    	DataType data;
    	Node *next;
    };
    class LinkQueue{
    	public:
    		LinkQueue();//初始化空的链表队列
    		~LinkQueue();//释放链队列的存储空间
    		void EnQueue(DataType x);//入队操作，将元素x出队
    		DataType DeQueue();//出队操作，将队头元素出队 
    		DataType GetHead();//取链队列队头元素
    		int Empty();//判断队列是否为空
    	private:
    		Node *front,*rear;//队头和队尾指针 
    		int Len;
    };
    //链队列基本操作的实现本质上是单链表操作的简单化，且时间复杂度均为O(1)
    
    //构造函数----链队列的初始化
    LinkQueue::LinkQueue(){
    	Node *s=nullptr;
    	s=new Node;
    	s->next = nullptr;
    	front=rear=s;//将队头指针和队尾指针都指向头结点s 
    }
    
    //析构函数----链队列的销毁【链队列是动态存储分配，需要释放链队列的所有结点的存储空间】 
    LinkQueue::~LinkQueue(){
    	while(front){//释放每一个结点的存储空间 
    		rear=front->next;
    		delete front;
    		front=rear;
    	}
    }
    
    //入队操作----链队列的插入操作只需考虑在链表的尾部进行
    void LinkQueue::EnQueue(DataType x){
    	Node *s=nullptr;
    	s=new Node;
    	s->data=x;s->next=nullptr;
    	rear->next=s;rear=s;//将结点s插入到队尾 
    	Len++;
    } 
    
    //出队操作----链队列的删除操作只需考虑在链表的头部进行 
    DataType LinkQueue::DeQueue(){
    	DataType x;
    	Node *p=nullptr;
    	if(rear == front) throw "下溢";
    	p=front->next;x=p->data;
    	front->next=p->next;
    	//if(!p->next)
    	if(rear==p) front=rear;
    	delete p;
    	Len--;
    	return x;
    } 
    
    //取队头元素
    DataType LinkQueue::GetHead(){
    	return front->next->data;
    }
    
    //判断队列是否为空
    int LinkQueue::Empty(){
    	if(front==rear) return 1;
    	else return 0;
    }
    
    int main(){
    	int x;
    	LinkQueue Q{};//定义对象变量Q
    	cout<<"对5和8执行入队操作,";
    	Q.EnQueue(5);
    	Q.EnQueue(8);
    	cout<<"当前队头元素为："<<Q.GetHead()<<endl;//输出队头元素5
    	try{
    		x=Q.DeQueue();
    		cout<<"执行一次出队操作，出队元素是："<<x<<endl;//输出出队元素5 
    	} catch(char *str){
    		cout<<str<<endl;
    	}
    	cout<<"当前队头元素为："<<Q.GetHead()<<endl;//输出队头元素8
    	try{
    		cout<<"请输入入队元素：";
    		cin>>x;
    		Q.EnQueue(x);
    	} catch(char *str){
    		cout<<str<<endl;
    	}
    	if(Q.Empty()==1) cout<<"队列为空"<<endl;
    	else cout<<"队列非空"<<endl;//队列有2个元素，输出队列非空 
    	return 0;
    }