数据结构之队列

1.引入

    队列（Queue），是一种先进先出（FIFO）的数据结构。现实中，操作系统中作业调度就使用到了队列。本文中，队列的实现，我使用的是链式表示与实现。

2.原理

    队列的示意图如下：

    其uml类图如下：

front:队列的队首，获取数据从这儿开始

rear:队列的队尾，添加数据将添加到rear的后面

length:表示当前队列的长度大小

Queue():队列的构造函数，用于初始化front,rear

deepClone():实现队列的深拷贝

isEmpty():判读队列是否为空

length():获取队列的大小length

getFront():获取队列的队首，从T返回，此时front指针不后移

add(T t):在队尾添加数据，此时rear指针后移

deleteFront():删除队首，并从T返回,此时front指针后移。

3.代码实现

Queue.java

package queue;

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;

public class Queue<T> implements Serializable {
	private Node<T> front;
	private Node<T> rear;
	private int length;

	public Queue() {
		System.out.println("调用了Queue的无参构造函数Queue()");
		front = null;
		rear = null;
		length = 0;
	}

	public Object deepClone() throws CloneNotSupportedException, IOException, ClassNotFoundException {
		// 序列化
		ByteArrayOutputStream bos = new ByteArrayOutputStream();
		ObjectOutputStream oos = new ObjectOutputStream(bos);

		oos.writeObject(this);

		// 反序列化
		ByteArrayInputStream bis = new ByteArrayInputStream(bos.toByteArray());
		ObjectInputStream ois = new ObjectInputStream(bis);

		return ois.readObject();

	}

	public boolean isEmpty() {
		if (length == 0) {
			return true;
		}
		return false;
	}

	public int length() {
		return length;
	}

	public void add(T t) {
		if(length==0)
		{
			front=rear=new Node<T>(t);
			++length;
		}
		else
		{
			Node<T> n=new Node<T>(t);
			rear.setNext(n);
			rear=n;
			++length;
		}
	}

	public T getFront() {
		return front.getData();
	}

	public T deleteFront() {
		T t=front.getData();
		front=front.getNext();
		return t;
	}
}

class Node<T> implements Serializable{
	// 数据信息
	T data;
	// 下一个节点信息
	Node<T> next;

	public Node(T t) {
		data = t;
		next = null;
	}

	public T getData() {
		return data;
	}

	public void setData(T t) {
		data = t;
	}

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

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

	public void setNext(T t) {
		next = new Node<T>(t);
	}
}

    测试层析Main.java如下

package queue;

import java.io.IOException;

public class Main {

	public static void main(String[] args) throws ClassNotFoundException, CloneNotSupportedException, IOException {
		// TODO Auto-generated method stub
		Queue<Integer> q=new Queue<Integer>();
		//测试isEmpty()
		System.out.println(q.isEmpty());
		
		//测试增add()
		q.add(1);
		q.add(2);
		q.add(3);
		q.add(4);
		
		//测试查getFront()
		int t=q.getFront();
		System.out.println(t);
		
		//测试deleteFront(()
		q.deleteFront();
		int t1=q.getFront();
		System.out.println(t1);
		
		//测试isEmpty()
		System.out.println(q.isEmpty());
		
		//测试getLength()
		System.out.printf("队列大小为%4d\n", q.length());
		
		//测试deepClone()
		Queue<Integer> cloneQ=(Queue<Integer>) q.deepClone();
		cloneQ.add(5);
		cloneQ.add(6);
		cloneQ.deleteFront();
		System.out.printf("原队列的队首为%d\n", q.getFront());
		System.out.printf("克隆队列的队首为%d", cloneQ.getFront());
		
	}

}

运行结果如下：