Skip to content

Latest commit

 

History

History
224 lines (154 loc) · 5.04 KB

数据结构（4）队列.md

File metadata and controls

224 lines (154 loc) · 5.04 KB
Raw

队列特性

队列和栈相似，是另一种顺序存储元素的线性数据结构。

  • 有两个指针 front、rear指向对头 和队尾；

  • 队头(front)一端进行删除操作，队尾(rear)一端进行插入操作，是FIFO，即先进先出

  • 使用场景：因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。

  • 栈与队列的区别：最大差别在于栈是LIFO（后进先出）

  • 队列分：顺序队列 、循环队列、链式队列

顺序队列

顺序对象过程

队列过程：

  • 队头和队尾的指针在初始化是都为指向 0
  • 当插入一个元素时，rear 加 1；
  • 当删除一个元素时，front 减 1；

由此可见：当 front = rear 时，队列为空。

假溢出现象

当队列经过新增，有经过删除时。即此时 front = rear 时，队列为空；但是在添加元素时，可能会发生 “假溢出” 现象，如图：

假溢出现象解决方案：

  1. 使用一个计数器记录队列中元素个数（即队列长度）
  2. 使用循环队列，人为浪费一个单元，令队满特征为 front = (rear +1)%maxSize

循环队列

循环队列是改进版的顺序队列，没有“假溢出”现象

在顺序队列中，当rear=front的时候，队列可能是满，也可能是空。

因此循环队列，加入了对 满和空两种情况的判断：

  • 队满：添加元素时，rear + 1 指向了 head 的元素。也就是转圈子要碰头了，就认为队列满了。即：front (rear+1)%MAXSIZE

  • 队空：删除元素到 head = rear 的时候，我们认为队列空了。rear == front，不一定为0

Java 循环实现

public class ArrayQueue {
	Object[] elementData; // 对象数组，队列最多存储a.length-1个对象
	int front; // 队首下标
	int rear; // 队尾下标

	public ArrayQueue() {
		this(10); // 调用其他构造方法
	}

	public ArrayQueue(int size) {
		elementData = new Object[size];
		front = 0;
		rear = 0;
	}

	// 入队
	public boolean push(Object obj) {
		if ((rear + 1) % elementData.length == front) { // 关键步骤 判断是否队满 
			return false;
		}
		elementData[rear] = obj;
		rear = (rear + 1) % elementData.length;  // 关键步骤 队尾指针后移
		return true;
	}

	// 出队 
	public Object pop() {
		if (rear == front) {	//  关键步骤 判断是否队空
			return null;
		}
		Object obj = elementData[front];
		front = (front + 1) % elementData.length;  // 关键步骤 队头指针后移
		return obj;
	}

	public static void main(String[] args) {
		ArrayQueue q = new ArrayQueue(4);
		System.out.println(q.push("张三")); // true
		System.out.println(q.push("李斯")); // true
		System.out.println(q.push("赵五")); // true
		System.out.println(q.push("王一")); // false 无法入队列，队列满
		for (int i = 0; i < 4; i++) {
			System.out.println(q.pop());
		}
		/* 循环体输出 ：
		 * 张三
		 * 李斯 
		 * 赵五 
		 * null
		 */
	}
}

链式队列

链式存储结构，限制仅在表头删除和表尾插入的单链表

代码实现

public class LinkQueue<T> {
	// 定义一个内部类Node，Node实例代表链队列的节点。
	private class Node {
		private T data;// 保存节点的数据
		private Node next;// 指向下个节点的引用

		// 初始化全部属性的构造器
		public Node(T data, Node next) {
			this.data = data;
			this.next = next;
		}
	}

	private Node front;// 保存该链队列的头节点
	private Node rear;// 保存该链队列的尾节点

	public LinkQueue() {
		// 空链队列，front和rear都是null
		front = null;
		rear = null;
	}

	public LinkQueue(T element) {
		front = new Node(element, null);
		// 只有一个节点，front、rear都指向该节点
		rear = front;
	}

	/**
	 * 入队
	 * 
	 * @param element
	 */
	public void offer(T element) {
		Node newNode = new Node(element, null);// 创建新节点
		// 如果该链队列还是空链队列
		if (front == null) {
			front = newNode;
			rear = front; // 只有一个节点，front、rear都指向该节点
		} else {
			rear.next = newNode;// 让尾节点的next指向新增的节点
			rear = newNode;// 以新节点作为新的尾节点
		}
	}

	/**
	 * 出队
	 * @return
	 */
	public T poll() {
		if (front == null ) {
			return null;
		}
		Node oldFront = front;
		front = front.next; // 将队头指针更改为指向 下一个节点
		oldFront.next = null;
		return oldFront.data;
	}

	public static void main(String[] args) {
		LinkQueue<String> q = new LinkQueue<>();
		q.offer("张三");
		q.offer("李斯");
		q.offer("赵五");
		q.offer("神兽");
		for (int i = 0; i < 5; i++) {
			System.out.println(q.poll());
		}
	}
}

//  输出：
张三
李斯
赵五
神兽
null