链队列之C++实现

骑猪看日落 2021-12-13 23:31 214阅读 0赞

链队列时建立在单链表的基础之上的。由于是动态分配节点内存，所以无需判满。

链队列的形式如下:

1、队列空

![20130831193404687][]

2、队列存在数据

![20130831193411828][]

下面介绍下C++实现的链队列，VC6下调试通过。

1、文件组织

![20130831192947843][]

2、lq.h链队列类的说明

#ifndef _LQ_H_
    #define _LQ_H_
    
    typedef int dataType;
    
    struct node                 //队列节点
    {
    	dataType data;          //数据域
    	node *next;             //指针域
    };
    
    class lq
    {
    public:
    	lq();                     //构造函数
    	~lq();                    //析构函数
    	void push(dataType var);  //入队
    	void pop();               //出队
    	dataType front();         //取对头元素,对头不变化
    	bool isEmpty();           //判空.head=tail=NULL时队列为空
    
    private:
    	node *head;               //对头指针
    	node *tail;               //队尾指针
    };
    
    #endif

3、lq.cpp链队列的定义

#include <iostream>
    #include "lq.h"
    using namespace std;
    
    lq::lq()
    {
    	head = NULL;           //head=tail=NULL时队列为空
    	tail = NULL;
    }
    
    lq::~lq()
    {
    	node *ptr = NULL;
    
    	while(head != NULL)
    	{
    		ptr = head->next;
    		delete head;
    		head = ptr;
    	}
    }
    
    void lq::push(dataType var)
    {
    	node *ptr = new node;
    
    	ptr->data = var;
    	ptr->next = NULL;
    	if(tail != NULL)         
    	{
    		tail->next = ptr;       //不是入队的第一个节点
    	}
    	else
    	{
    		head = ptr;				//如果是入队的第一个节点
    	}
    	tail = ptr;
    }
    
    void lq::pop()
    {
    	node *ptr = head->next;
    
    	delete head;
    	head = ptr;
    
    	if(head == NULL)         //head时要将tail也赋为NULL
    	{
    		tail = NULL;
    	}
    }
    
    dataType lq::front()
    {
    	return head->data;
    }
    
    bool lq::isEmpty()
    {
    	return head == NULL && tail == NULL;
    }

4、main.cpp

#include <iostream>
    #include "lq.h"
    using namespace std;
    
    int main()
    {
    	lq exp;
    	int i =0;
    
    	for(i=0;i<100;i++)
    	{
    		exp.push(i);
    	}
    
    	for(i=0;i<200;i++)
    	{
    		if(!exp.isEmpty())
    		{
    			cout<<exp.front()<<endl;
    			exp.pop();
    		}
    	}
    
    	if(exp.isEmpty())
    	{
    		cout<<"队列为空!"<<endl;
    	}
    
    	return 0;
    }

转载于:https://www.cnblogs.com/james1207/p/3293784.html

[20130831193404687]: /images/20211213/0d7882b2958a4008aca9ff80cd184b7e.png
[20130831193411828]: /images/20211213/d44892c102a64d14bc8c09e77a0bb72c.png
[20130831192947843]: /images/20211213/364cbc2e530640faaa84921d0023b046.png