3.4.2 -队列的链式表示和实现

队列的链式表示和实现

   队列是一种先进先出的数据结构,和食堂排队打饭类似,在前面的先打到饭,而后来者只有等前面的打完饭,后面的才能进行
以下给出C++实现

#include <iostream>
using namespace std;

#define ElemType int
typedef struct QNode{
	ElemType data;
	struct QNode *next;
}Node, *NodePtr;

//72
//链队列
class Queue{
private:
	NodePtr front; //队头
	NodePtr rear;  //队尾
public:
	Queue()
	{
		InitQueue();
	}
	bool InitQueue(); //构造一个空队列
	bool DestoryQueue(); //销毁队列
	void ClearQueue(); //清空队列
	bool QueueEmpty(); //队列是否为空
	int QueueLength(); //队列长度
	void GetHead(ElemType &e); //获取队头元素
	bool EnQueue(ElemType e); //把e插入到队尾
	bool DeQueue(ElemType &e); //如果队列不为空,删除队头元素,用e返回其值
};

//初始队列
bool Queue::InitQueue()
{
	this->front = this->rear = (NodePtr)malloc(sizeof(Node));
	if(!this->front)
		return false; //创建失败 
	this->front->next = NULL;
	return true;
}

//销毁队列
bool Queue::DestoryQueue()
{
	while(this->front) //不用新开一个变量,直接用队尾指针
	{
		this->rear = this->front->next;
		delete this->front;
		this->front = this->rear;
	}
	return true;
}
//插入元素到队尾,相当于入队列
bool Queue::EnQueue(ElemType e)
{
	NodePtr cur = (NodePtr)malloc(sizeof(Node));
	if(!cur)
		return false;
	cur->data = e; 
	this->rear->next = cur; //让队尾的下一个元素为cur
	this->rear = cur;  //移动队尾指针
	this->rear->next = NULL; //让队尾指针为NULL
	return true;
}
//队列是这样的 队头(数据域为空) 第一个元素 ....第n个元素 队尾 出队列
bool Queue::DeQueue(ElemType &e)
{
	if(this->front == this->rear)
		return false; //队列为空
	NodePtr cur = this->front->next; //找到第一个元素,也就是队头后面的元素
	e = cur->data;
	this->front->next = cur->next; //删除第一个元素
	if(this->rear == cur) //如果第一个元素刚好是队尾元素
		this->rear = this->front; //则让 this->rear 和front为第一个空元素
	delete cur; //销毁
	return true;
}
//清空队列
void Queue::ClearQueue()
{
	this->rear = this->front;
}
//判断队列是否为空
bool Queue::QueueEmpty()
{
	return this->rear == this->front;
}
//获取队列长度
int Queue::QueueLength()
{
	NodePtr cur = this->front->next;
	int size = 0;
	while(cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
//获取队头数据
void Queue::GetHead(ElemType &e)
{
	e = this->rear->data;
}
int main()
{
	int e;
	Queue queue;
	queue.EnQueue(3);
	queue.DeQueue(e);
	cout<<e<<endl;
	queue.EnQueue(4);
	cout<<"队列长度:"<<queue.QueueLength()<<endl;
	if(queue.QueueEmpty())
		cout<<"队列为空\n";
	else
		cout<<"队列不为空\n";
	queue.GetHead(e);
	cout<<"队头元素:"<<e<<endl;
	return 0;
}

java代码实现

Node(结点类):

package study.queue;
//结点类
public class Node<T> {
	
	private T data;
	
	private Node<T> next;

	public T getData() {
		return data;
	}

	public void setData(T data) {
		this.data = data;
	}

	public Node<T> getNext() {
		return next;
	}

	public void setNext(Node<T> next) {
		this.next = next;
	}
}

Queue(队列类):

package study.queue;

public class Queue<T> {
	//队头
	private Node<T> front = null;
	//队尾
	private Node<T> rear = null;
	//获取队列元素
	private T e; 
	
	public Queue(){
		this.InitQueue();
	}
	
	/**
	 * 获取元素
	 * @return
	 */
	public T getE() {
		return e;
	}
	/**
	 * 初始化队列
	 * @return
	 */
	private boolean InitQueue(){
		this.front = this.rear = new Node<T>();
		if(this.front == null)
			return false; //初始化失败
		this.front.setNext(null);
		return true;
	}
	/**
	 * 销毁队列
	 */
	public void DestoryQueue(){
		while(this.front != null){
			this.rear = this.front.getNext();
			this.front = this.rear;
		}
	}
	/**
	 * 入队列
	 * @param e
	 * @return
	 */
	public boolean EnQueue(T e){
		Node<T> cur = new Node<T>();
		if(cur == null)
			return false;
		cur.setData(e);
		this.rear.setNext(cur);
		this.rear = cur;
		this.rear.setNext(null);
		return true;
	}
	/**
	 * 出队列
	 * @return
	 */
	public boolean DeQueue(){
		if(this.front == this.rear)
			return false;
		Node<T> cur = this.front.getNext();
		e = cur.getData();
		this.front.setNext(cur.getNext());
		if(cur == this.rear)
			this.rear = this.front;
		return true;
	}
	/**
	 * 情况队列
	 */
	public void ClearQueue(){
		this.rear = this.front;
	}
	/**
	 * 判断队列是否为空 是则返回ture
	 * @return
	 */
	public boolean QueueEmpty(){
		return this.rear == this.front;
	}
	/**
	 * 获取队列长度
	 * @return
	 */
	public int QueueLength(){
		int size = 0;
		Node<T> cur = this.front.getNext();
		while(cur != null){
			size++;
			cur = cur.getNext();
		}
		return size;
	}
	/**
	 * 获取队头元素
	 * @return
	 */
	public T GetHead(){
		return this.rear.getData();
	}
}

Main(测试类):

package study.queue;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Queue<Integer> queue = new Queue<Integer>();
		queue.EnQueue(3);
		queue.DeQueue();
		System.out.println("出队列元素:" + queue.getE());
		queue.EnQueue(4);
		System.out.println("队列长度:" + queue.QueueLength());
	}

}