队列(queue)是只允许在一端进行插入 *** 作,而在另一端进行删除 *** 作的线性表。 队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队,如果你排在他前面,你将先上车,而后来的人将会排在你朋友后面。队列的工作原理与此相同。
队列是一种先进先出(First In First Out)的线性表,简称FIFO。 允许插入的一端称为队尾,允许删除的一端称为队头。假设队列是q=(a1,a2,…,an),那么a1就是队头元素,而an是队尾元素。这样我们就可以删除时,总是从a1开始,而插入时,列在最后。
因为队列属于线性表,因此队列也可以采用顺序存储结构和链式存储结构来实现。Java中已经提供了很多线程的队列的实现,比如JUC中的各种阻塞、非阻塞队列。在生产环境中,各种消息队列比如kafka底层都使用了最基本的队列的特性。队列的使用频率是要高于栈的。
package com.lineardatastructure.queue; public interface Queue队列数组储结构{ void push(T e); T pop(); T peek(); int getSize(); boolean isEmpty(); boolean isFull(); void queueDestroy(); }
队列的入队和出队 *** 作在不同端。采用数组来实现时,如果队头在数组元素最小索引处,那么入队列就是将元素添加到最大索引后的索引处,不需要移动元素,此时时间复杂度为O(1), 但是出队列就要在数组头部了,此时将会移动全部元素,时间复杂度为O(n)(但是也是有优化办法看下图)。
当浪费到指定数量内存后我们进行迁移数据
当队列满了,我们就进行扩容
package com.lineardatastructure.queue; public class ArrayQueue队列链表储结构implements Queue { private Object[] arrayQueue;//队列数组 private int end = 0;//队尾下标 private int begin=0;//队列开头 private final int CLEARTRASH = 1000; //垃圾个数 private int length; public ArrayQueue(int size) { arrayQueue = new Object[size]; } public ArrayQueue() { arrayQueue = new Object[30]; } @Override public synchronized void push(T e) { if (!this.isFull()) { this.arrayQueue[this.end++] = e; } else { //队列满了进行扩容 this.length = this.arrayQueue.length + (int) (this.arrayQueue.length * 0.75 + 1); Object[] target = new Object[this.length]; //java最快数组copy方式 System.arraycopy(this.arrayQueue, 0, target, 0, this.arrayQueue.length); this.arrayQueue = target;//将原数组替换 this.arrayQueue[this.end++] = e; } } @Override public synchronized T pop() { if (this.isEmpty()) { System.out.println("队列为空,请先向队列中添加元素"); return null; } else { T t = (T) this.arrayQueue[this.begin]; if (this.begin == CLEARTRASH) { //队列向前移动,清理垃圾 int i = this.CLEARTRASH + 1; int i1 =this.end-i ; Object[] target = new Object[this.length]; System.arraycopy(this.arrayQueue, i, target, 0, i1); this.arrayQueue = target; this.begin = -1; this.end=this.end-i; } this.begin++; return t; } } @Override public synchronized T peek() { return (T) this.arrayQueue[this.begin]; } @Override public synchronized int getSize() { return this.end; } @Override public synchronized boolean isEmpty() { if (this.arrayQueue == null) { return true; } return this.arrayQueue[this.begin] == null; } @Override public synchronized boolean isFull() { return this.arrayQueue.length == this.end; } @Override public synchronized void queueDestroy() { this.arrayQueue = null; this.end = 0; } }
队列的入队和出队 *** 作在不同端。采用链表来实现时,队列头和队列尾部, 时间复杂度都是O(1) 使用链式结构实现队列相比顺序结构的实现更加简单。
队列的链式存储结构,其实就是线性表的单链表,只不过它只是尾进头出而已,我们把它简称为链队列。为了 *** 作上的方便,我们将队头指针指向链队列的头结点,而队尾指针指向终端节点
空队列时,头指针front和尾指针rear都指向头结点。
插入
取值
package com.lineardatastructure.queue; public class linkedQueueimplements Queue { private Node first; private Node end; private int size; private static class Node { //下一个结点的引用 Node next; //结点数据 T data; //节点构造器 public Node(T data, Node next) { this.data = data; this.next = next; } } @Override public void push(T e) { //创建新节点 Node newNode = new Node<>(e, null); if (this.end == null) { this.end = newNode; this.first = newNode; this.size++; return; } //改变头节点,和尾节点 ,A-b-c-d this.end.next=newNode;// 这个动作其实是添加this.first的下一个节点 ,1,2,3,4 this.end=newNode; //存放最后节点元素 this.size++; } @Override public T pop() { if (this.isEmpty()) { return null; } T e = this.first.data; //改变队头节点引用,将下一个节点引用替换当前引用 this.first = this.first.next; //如果元素为0,则将队尾节点引用置空 if (--this.size == 0) { this.end = null; } return e; } @Override public T peek() { return this.first.data; } @Override public int getSize() { return this.size; } @Override public boolean isEmpty() { return this.first == null; } @Override public boolean isFull() { return false; } @Override public void queueDestroy() { this.first=null; this.end=null; this.size=0; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)