Java基础复习笔记06数据结构-队列

1.       队列

队列又是一种比较特殊的线性表，和栈一样在线性表的基础上进行了一些限制操作。就是队列了。顾名思义，队列就是咱们排队买火车票一样，排在最前面的先买到，排到后面的后买到。先进先出、后进后出。

 

2.       队列的操作

队列的操作一般包括：进队列、出队列，访问队列头元素、删除队列头元素、判断队列是否为空、获得队列大小这些核心操作。Sun为Java的队列规定了一个规范、反映出来的的就是java.util.Queue，实现了此接口的所有方法，相当于“你按照Sun的Java规范为自己写了一个符合规范的队列实现类”。

3.       队列的使用场景

队列的使用场景其实个人感觉比栈要广泛一些，比如开发网络服务中间件，处理并发消息的时候就需要将这些消息组成队列的方式一个一个处理，再比如对象池的应用，底层完全可以做成一个对象队列，将一个用完的对象放回池中后，就是放到等待队列中，先归还的对象，下次再使用的时候就比后放入的对象优先调用，因为先归还的对象肯定是休息了很久了，该对象应当回收的资源也都回收了。

4.       队列的顺序实现

和栈结构一样队列也有两种实现方式，先来看顺序的实现方式，顺序实现方式就是利用数组，记录当前队列头标记nowTopIndex以及下一个、新的队列结尾元素的标记newTailIndex。

程序如下：

package dateStructer.queue;

/**
 * 顺序队列
 * 
 * @author liuyan
 * @param <E>
 */
public class MyArrayQueue<E> implements Queue<E> {

	// 默认大小
	private final static int DefSize = 32;

	// 临时数组
	private Object[] objects;

	// 当前队列头元素索引
	private int nowTopIndex;

	// 下一个队列新元素的索引
	private int newTailIndex;

	public MyArrayQueue() {
		objects = new Object[DefSize];
	}

	/**
	 * 添加元素
	 */
	@Override
	public boolean add(E e) {

		int elementSize = newTailIndex - nowTopIndex;

		if (elementSize == 0 && newTailIndex == 0) {
			objects[0] = e;
			nowTopIndex = 0;
			newTailIndex = 1;
			return true;
		}

		objects[newTailIndex++] = e;

		return true;
	}

	/**
	 * 获取队头元素
	 */
	@Override
	public E element() {
		return (E) objects[nowTopIndex];
	}

	/**
	 * 返回头元素，不删除头元素
	 */
	@Override
	public E peek() {
		return (E) objects[nowTopIndex];
	}

	/**
	 * 返回头元素，删除头元素
	 */
	@Override
	public E poll() {

		if (objects[nowTopIndex] == null) {
			return null;
		}

		E date = (E) objects[nowTopIndex];
		objects[nowTopIndex++] = null;
		return date;
	}

	@Override
	public E remove() {
		if (nowTopIndex == 0) {
			return null;
		}
		E date = (E) objects[nowTopIndex];
		objects[nowTopIndex--] = null;
		return date;
	}

	@Override
	public void clear() {
		Arrays.fill(objects, null);
		nowTopIndex = 0;
		newTailIndex = 0;
	}

	@Override
	public boolean contains(Object object) {
		for (int i = 0; i < objects.length; i++) {
			if (object == objects[i]) {
				return true;
			}
		}
		return false;
	}

	@Override
	public boolean isEmpty() {
		int elementSize = newTailIndex - nowTopIndex;
		return elementSize == 0;
	}

	@Override
	public int size() {
		return newTailIndex - nowTopIndex;
	}

	@Override
	public String toString() {

		StringBuffer str = new StringBuffer("[");

		int elementSize = newTailIndex - nowTopIndex;

		for (int i = nowTopIndex; i < newTailIndex; i++) {

			str.append("[" + objects[i].toString() + "],");

		}

		if (elementSize > 0) {
			return str.substring(0, str.lastIndexOf(",")) + "]";
		}

		return str.append("]").toString();
	}
}

 测试代码如下

	public static void main(String[] args) {
		MyArrayQueue<String> myQueue = new MyArrayQueue<String>();
		myQueue.add("1");
		myQueue.add("2");
		myQueue.add("3");
		System.out.println(myQueue.toString());
		String e = myQueue.poll();
		System.out.println(e);
		System.out.println(myQueue.toString());
		myQueue.add("4");
		e = myQueue.peek();
		System.out.println("是否为空队列" + myQueue.isEmpty());
		System.out.println("队列大小" + myQueue.size());
		System.out.println(e);
		System.out.println(myQueue.toString());
		System.out.println("是否包含相关元素" + myQueue.contains("1"));
		System.out.println("是否包含相关元素" + myQueue.contains("2"));
		myQueue.clear();
		System.out.println("是否为空队列" + myQueue.isEmpty());
	}

 运行后效果如下

[[1],[2],[3]]
1
[[2],[3]]
是否为空队列false
队列大小3
2
[[2],[3],[4]]
是否包含相关元素false
是否包含相关元素true
是否为空队列true

5.       队列的链表实现

相对于顺序实现方式，链式实现相对比较简单，只需要利用Node结构，记录下队列的头Node和尾巴Node，在记录下元素个数就可以了。算法如下

package dateStructer.queue;

/**
 * 实现自己的队列
 * @author liuyan
 * @param <E>
 */
public class MyQueue<E> implements Queue<E> {
	
	/**
	 * 双向链表结构
	 */
	public class LinkNode {

		// 真正的数据域
		private E date;

		// 记录上一个节点
		private LinkNode prevLinkNode;

		// 记录下一个节点
		private LinkNode nextLinkNode;

		public LinkNode() {

		}

		public LinkNode(E date, LinkNode prevLinkNode, LinkNode nextLinkNode) {
			this.date = date;
			this.prevLinkNode = prevLinkNode;
			this.nextLinkNode = nextLinkNode;
		}
	}
	
	// 结点个数
	private int nodeSize;

	// 头结点
	private LinkNode headNode;

	// 尾巴节点
	private LinkNode tailNode;
	
	public MyQueue(){
		headNode = null;
		tailNode = null;
	}
	
	/**
	 * 添加元素
	 */
	@Override
	public boolean add(E element) {
		if (nodeSize == 0) {
			headNode = new LinkNode(element, null, tailNode);
		}else {

			if (tailNode == null) {
				tailNode = new LinkNode(element, headNode, null);
				headNode.nextLinkNode = tailNode;
				nodeSize++;
				return true;
			}

			LinkNode linkNode = tailNode;
			tailNode = new LinkNode(element, linkNode, null);
			linkNode.nextLinkNode = tailNode;

		}
		nodeSize++;
		return true;
	}
	
	/**
	 * 访问队列头元素
	 */
	@Override
	public E element() {
		return headNode.date;
	}
	
	/**
	 * 返回头元素，不删除头元素
	 */
	@Override
	public E peek() {
		return headNode.date;
	}

	/**
	 * 返回头元素，删除头元素
	 */
	@Override
	public E poll() {
		
		LinkNode headNodeTemp = headNode;
		E date = headNodeTemp.date;
		if(headNode.nextLinkNode == null){
			headNode.date = null;
			headNode = null;
			nodeSize--;
			return date;
		}else{
			headNode = headNode.nextLinkNode;
			if(headNode == tailNode){
				tailNode = null;
			}
		}
		
		nodeSize--;
		
		return headNodeTemp.date;
	}
	
	/**
	 * 清除所有元素
	 */
	@Override
	public void clear() {

		LinkNode linkNodeNowTemp = headNode;

		for (int i = 0; i < nodeSize; i++) {

			if (linkNodeNowTemp != tailNode && linkNodeNowTemp != headNode) {
				linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
				linkNodeNowTemp.prevLinkNode.nextLinkNode = null;
				linkNodeNowTemp.prevLinkNode.prevLinkNode = null;
				linkNodeNowTemp.prevLinkNode.date = null;
				linkNodeNowTemp.prevLinkNode = null;
			} else if (linkNodeNowTemp == tailNode) {
				linkNodeNowTemp.prevLinkNode = null;
			} else if (linkNodeNowTemp == headNode) {
				linkNodeNowTemp.nextLinkNode = null;
			}

		}
		headNode = null;
		tailNode = null;
		nodeSize = 0;

	}
	
	/**
	 * 判断是否存在
	 */
	@Override
	public boolean contains(Object object) {

		LinkNode linkNodeNowTemp = headNode;

		for (int i = 0; i < nodeSize; i++) {

			if (object == linkNodeNowTemp.date) {
				return true;
			}

			linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
		}

		return false;
	}
	
	/**
	 * 队列是否为空
	 */
	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return nodeSize == 0;
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return nodeSize;
	}
	
	/**
	 * 根据索引号查找节点
	 * 
	 * @param index
	 * @return
	 */
	public LinkNode findLinkNodeByIndex(int index) {

		LinkNode linkNodeNowTemp = headNode;

		for (int i = 0; i < nodeSize; i++) {

			if (i == index) {
				return linkNodeNowTemp;
			}

			linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
		}
		return null;
	}
	
	@Override
	public String toString() {

		StringBuffer str = new StringBuffer("[");
		LinkNode linkNode = null;
		for (int i = 0; i < nodeSize; i++) {

			linkNode = findLinkNodeByIndex(i);

			str.append("[" + linkNode.date + "],");

		}

		if (nodeSize > 0) {
			return str.substring(0, str.lastIndexOf(",")) + "]";
		}

		return str.append("]").toString();
	}
	
}

 测试代码和顺序实现的测试代码相同，在此不再赘述。

6.       总结

队列是一种比较简单线性表，使用场景很多，尤其是开发自己的类库层次。使用队列这种结构存储临时数据的情况比较多。顺序实现与链表实现各有利弊。一般元素个数比较固定用顺序实现方式，如果使用元素个数变化十分频繁，还是使用链表效率好一些。顺序实现方式存在一种隐患就是“假满现象”，所以顺序实现还可以采用循环队列，循环队列的原理就是如果头索引=尾索引，并且头索引不等于0，并且此时数组大小已经都用完了，那么将头、尾索引都置为0即可，这里就不给出代码了。当然以上2种方式的实现都是没有做安全检查的，而且顺序实现元素最大个数也只能拥有和数组一样的元素个数。Java有个常用的队列java.util.concurrent.ConcurrentLinkedQueue。