Java数据结构（三）

Java数据结构（三）

——队列

队列（简称为队）也是一种特殊的线性表，队列的数据元素以及数据元素之间的操作与线性表完全相同，差别是线性表允许在任意位置插入和删除，而队列只允许在一端进行插入操作而在另一端进行删除操作。队列允许插入操作的一端称为队尾，允许进行删除操作的一端称为对头。队列的插入操作通常称为入队列，队列的删除操作通常称为出队列。

因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，因此队列也被称为先进先出表。比方说，大家在食堂排队买饭时，只有最早来排队的，即最先入队列的，才能最先买到饭，即最先出队列。

顺序队列

使用顺序存储结构的队列称为顺序队列。

 

如图所示，这是一个有4个存储空间的顺序队列的动态示意图，图中front表示队头，rear表示队尾，图（a）表示一个空队列，此时front=rear=0；图（b）表示数据元素A、B、C入队列后的状态。此时front=0，rear=3；图（c）表示A已经退出队列，此时front=1，rear=3；图（d）表示B、C都已经出队列，此时队列已空。但是front=rear=3。那么，假如我们一开始设置的队列长度仅为3个时，即maxSize=3，那么如果还有数据元素想要进入队列，顺序队列将因为越出数组下界而“溢出”。但实际上数组中还有3个位置可以存储，此时的“溢出”并是不是由于数组空间不够而产生的溢出。顺序队列因多次入队列和出队列的操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出。

假溢出是由于队尾rear的值和队头front的值不能由所定义数组下界值自动转为数组上届值而产生的。因此，解决该问题的方法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到maxSize-1后，在加1就自动到0，这样就不会出现假溢出的问题，例如rear=（rear+1）%6。

不过顺序循环队列还存在一个问题，即当队列空时和队列满时，front=rear=0，即无法区分队列为空还是为满的状态，这样最好的解决无疑是设置一个计数器count，初始时设置count=0（队列空时为0），每入列一次count加一，每出列一次count就减一，因此，这样判断队列为空的条件为count==0，队列满的判断条件为count！=0&&front == rear。下面为具体实现代码：

 

package pzw.Queue;
/**
 * 使用顺序存储结构实现的队列
 * @author pzw
 *
 */
public class SeqQueue implements queue{
	
	public final int defaultSize = 10;//默认构造队列的大小
	public Object[] queue;//队列数组
	public int top;//队列头部位置
	public int end;//队列尾部位置
	public int count;//队列中现有元素的个数
	public int maxSize;//队列中最大元素的个数
	
	//无参构造函数
	public SeqQueue(){
		initiate(defaultSize);
	}
	//构造函数
	public SeqQueue(int size){
		initiate(size);
	}
	//队列初始化
	private void initiate(int size){
		maxSize = size;
		queue = new Object[size];
		top = 0;
		end = 0;
		count = 0;
	}
	
	public void insert(Object elm) throws Exception{
		if(top == end&&count != 0){
			throw new Exception("该队列已满，请先清空该队列");
		}
		queue[end] = elm;
		end = (end + 1) % maxSize;//加一后求模，解决顺序存储结构假溢出
		count++;
	}

	public Object delete() throws Exception{
		if(top == end&&count == 0){
			throw new Exception("该队列已空，请添加数据");
		}
		top = (top + 1) % maxSize;
		count--;
		return queue[top];
	}

	public Object getData() throws Exception{
		if(top == end&&count == 0){
			throw new Exception("该队列已空，请添加数据");
		}
		return queue[top];
	}

	public boolean notEmpty() {
		return count > 0;
	}

}

 

链式队列

package pzw.Queue;
/**
 * 队列的链式存储结构的实现
 * @author pzw
 *
 */
public class LinQueue implements queue{
	
	private Node top;//队列的头部
	private Node end;//队列的尾部
	private int count;//队列中元素的个数
	
	//构造函数
	public LinQueue(){
		initiate();
	}
	
	//初始化队列
	private void initiate(){
		top = null;
		end = null;
		count = 0;
	}
	
	public void insert(Object elm) throws Exception {
		Node newNode = new Node(elm,null);
		if(end != null){
			end.next = newNode;//插入新结点
		}
		end = newNode;//重置尾结点
		if(top == null){
			top = newNode;
		}
		count++;
	}

	public Object delete() throws Exception {
		if(count == 0){
			throw new Exception("该队列已空，请添加数据");
		}
		Node temp = top;
		top = top.next;//重置头结点
		count--;
		return temp.elm;
	}

	public Object getData() throws Exception {
		if(count == 0){
			throw new Exception("该队列已空，请添加数据");
		}
		return top.elm;
	}

	public boolean notEmpty() {
		// TODO Auto-generated method stub
		return count != 0;
	}

}