链表队列的实现

在 Linux 的vi编辑器下 

        简单的链表队列实现 .

#include<iostream>
using namespace std;

struct Node
{
	int data;
	Node* next;
};

class Queue
{
public:
	Queue();
	bool full();             //判断是否为满
	bool empty();            //判断是否为空
	bool Enqueue(int);       //进队
	bool Dequeue(int&);      //出对
//	Node* bfront();
	void list();             //遍历队列元素
	unsigned short QueueLength();    //记录进队的元素
private:
	unsigned short ilen;    //长度记录
	Node* front;            //指向队头
	Node* rear;             //指向队尾
};

unsigned short Queue::QueueLength()
{
	return this->ilen;
}

void Queue::list()
{
	while(this->front!=NULL)    //判断队头元素是否为空
	{
		int value;
		Dequeue(value);
		cout<<"出队:"<<value<<endl;
	}
}

/*
Node* Queue::bfront()
{
	return this->front;
}
*/

Queue::Queue()            //初始化
{
	this->front=NULL;
	this->rear=NULL;
	this->ilen=0;
}

bool Queue::full()
{
	return false;
}

bool Queue::empty()
{
	if(NULL==this->front)
		return true;
	else
		return false;
}

bool Queue::Enqueue(int d)      //进队
{
	Node* pnew=new Node;        //申请节点空间
	pnew->data=d;
	if(NULL==pnew)
		return false;
	if(NULL==this->front)        //当第一次进队时
	{
		this->front=pnew;
		this->rear=pnew;
	}
	else                        //非第一次进队,代表不是从第一个元素进队
	{
		this->rear->next=pnew;
		this->rear=pnew;
	}
	ilen++;                    //记录元素个数
	return true;
}

bool Queue::Dequeue(int& value)//出队
{
	if(this->empty())
		return false;
	else
		value=this->front->data;    //出队是先拿到元素
		Node* ptemp=this->front;    //将节点空间记录
		this->front=this->front->next;    //将头节点指向下一个节点
		delete ptemp;               //释放记录的空间
	ilen--;
	return true;
}

int main()
{
	Queue q;
	int i=1;
	for(i=1;i<8;i++)
	{
		if(q.Enqueue(i))
			cout<<"进队:"<<i<<endl;
	}
	
	cout<<"进队后有"<<q.QueueLength()<<"个元素"<<endl;
	
	q.list();             //遍历出队

	cout<<"出队后有"<<q.QueueLength()<<"个元素"<<endl;

/*	int value;            //遍历出队
	while(q.bfront()!=NULL)
	{
		q.Dequeue(value);
		cout<<value<<endl;
	}
*/
}

 

       下面是将 节点分为一个类,有头文件,和类文件 , 将数据区作为一个类(类似于结构体),有头文件和类文件  ,  将 队列作为一个文件,有头文件和类文件  ,  将主函数作为一个文件  ,  来实现的链表队列 . 

 首先创建一个 node 文件.  node 节点 的内容.

#include "patient"

#ifndef __nodeH__
#define __nodeH__

class Node
{
public:
	Node();
	Node(patient&);
	void setNext(Node* next);//设置next
	//返回地址
	Node* getNext();
	//返回别名
	patient&  getData(); 
	
private:
	patient data;	//Patient信息：
	struct Node* next;
};

#endif 

   node.cpp  的构造方法 .

#include "node"

Node::Node():data(),next(NULL)
{
}
Node::Node(patient& p):data(p),next(NULL)
{
}
void Node::setNext(Node* p)
{
	this->next=p;
}
patient& Node::getData()
{
	return this->data;
}
Node* Node::getNext()
{
	return this->next;
}

    patient  的头文件的数据区.

//防止得利包含
#ifndef __HPATIENT__
#define __HPATIENT__
#include<string>
using namespace std;
class patient
{
public:
	//构造器：
	patient();
	patient(int,string,string);
	void show();
private:
	int id;	    //ID
	string name;//用类作属性成员
	string room;
};

#endif

   patient 的构造方法 .

#include<iostream>
using namespace std;
#include "patient"

//无参构造
patient::patient():id(0),name("nul"),room("nul")
{
}
//有参构造
patient::patient(int i,string n,string r):id(i),name(n),room(r)
{

}
//输出：
void patient::show()
{
	cout<<"ID:"<<id<<" 姓名:"<<name<<" 科室"<<room;
}

   队列的 queue 头文件 .

#include "node"
#include "patient"
#ifndef __QUEUE__
#define __QUEUE__

class Queue
{
public:
	Queue();
	//队列操作
	bool EnQueue(patient&);//进队
	bool DeQueue(patient&);
	bool IsFull();//为满
	bool IsEmpty();//为空
	unsigned short QueueLength();//队列长度
	//bool ClearQueue(); //清空队列
//属性
private:
	unsigned short ilen;
	Node* front;//队头
	Node* rear;//队尾
};

#endif

    queue  的方法的实现 .

#include "queue"
#include "patient"
#include <iostream>
using namespace std;
//构造
Queue::Queue():rear(NULL),front(NULL),ilen(0)
{
}
//为满 
bool Queue::IsFull()
{
	return false;
}
//空
bool Queue::IsEmpty()
{
	if(NULL==this->front)
		return true;
	else
		return false; 
}
//进队
bool Queue::EnQueue(patient& p)
{
//1分配节点空间
	Node* pnew=new Node(p);
	if(NULL==pnew)
		return false;
//2修改指向域
	if(NULL==this->front)//第一次创建
		this->front=pnew;
	else//非第一次创建
		this->rear->setNext(pnew); //由于next是私有的,调用公用接口
	this->rear=pnew;
	this->ilen++;
	return true;
}
//出队：只需要把信息返回
bool Queue::DeQueue(patient& p)
{
	if(this->IsEmpty())//为空
		return false;	
	//先返回信息
	p=this->front->getData();		//this->front->data; 私有
	//释放结点
	Node* ptemp=this->front;
	this->front=this->front->getNext();	//next是私有的，类外不能访问
	delete ptemp;
	//长度
	this->ilen--;
	return true;
}
//长度
unsigned short Queue::QueueLength()
{
	return this->ilen;
}

   主函数 :

#include <iostream>
#include "queue"
#include "patient"
using namespace std;

int main()
{
//定义队列
	Queue q;//构造函数	
//进队
	patient p(101,"刘二狗","精神科");//构造函数
	if(q.EnQueue(p))
		cout<<"成功"<<endl;
//出队	
	patient value;
	if(q.DeQueue(value))
	{
		value.show();
	}
	else
		cout<<"失败"<<endl;
}