1、线性表之队列(queue)
1、队列(Queue)-概述：1-1、队列是只允许在一端进行插入，在另一端进行删除操作的线性表。允许插入的一端成为队尾，允许删除的一端称为队头。1-2、队列是先进先出(FIFO-First in, First out)的线性表。2、队列(Queue)-使用场景：2-1、因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。
1.1、队列(Queue)-存储结构/分类
1、队列(Queue)-存储结构/分类：1-1、顺序存储结构：使用数组实现的叫静态队列1-1-1、插入元素的时间复杂度为O(1)，删除元素事前面的元素删除之后，后面的元素都要向前挪，因此其时间复杂度为O(N)。1-2、链式存储结构：使用链表实现的叫动态队列1-2-1、插入元素的时间复杂度为O(1)，引入front [frʌnt]和rear [rɪə(r)]指针，front指向队头，rear指向队尾，当两者相等时，front=rear说明队列满，但是front=rear也说明队列为空。。因此删除操作其时间复杂度为O(N)。
1.1.1、线性表之队列(queue)-顺序存储结构及实现-Demo
1、顺序存储结构及实现-Demopublic class SequenceQueue<T> {private int DEFAULT_SIZE = 10;//保存数组的长度。private int capacity;//定义一个数组用于保存顺序队列的元素private Object[] elementData;//保存顺序队列中元素的当前个数private int front = 0;private int rear = 0;//以默认数组长度创建空顺序队列public SequenceQueue() {capacity = DEFAULT_SIZE;elementData = new Object[capacity];}//以一个初始化元素来创建顺序队列public SequenceQueue(T element) {this();elementData[0] = element;rear++;}/*** 以指定长度的数组来创建顺序队列* @param element 指定顺序队列中第一个元素* @param initSize 指定顺序队列底层数组的长度*/public SequenceQueue(T element , int initSize) {this.capacity = initSize;elementData = new Object[capacity];elementData[0] = element;rear++;}//获取顺序队列的大小public int length() {return rear - front;}//插入队列public void add(T element) {if (rear > capacity - 1) {throw new IndexOutOfBoundsException("队列已满的异常");}elementData[rear++] = element;}//移除队列public T remove() {if (empty()) {throw new IndexOutOfBoundsException("空队列异常");}//保留队列的rear端的元素的值T oldValue = (T)elementData[front];//释放队列的rear端的元素elementData[front++] = null;return oldValue;}//返回队列顶元素，但不删除队列顶元素public T element() {if (empty()) {throw new IndexOutOfBoundsException("空队列异常");}return (T)elementData[front];}//判断顺序队列是否为空队列public boolean empty() {return rear == front;}//清空顺序队列public void clear() {//将底层数组所有元素赋为nullArrays.fill(elementData , null);front = 0;rear = 0;}public String toString() {if (empty()) {return "[]";}else{StringBuilder sb = new StringBuilder("[");for (int i = front ; i < rear ; i++ ) {sb.append(elementData[i].toString() + ", ");}int len = sb.length();return sb.delete(len - 2 , len).append("]").toString();}}}
1.1.2、线性表之队列(queue)-循环存储结构及实现-Demo
1、循环存储结构及实现-Demopublic class LoopQueue<T> {private int DEFAULT_SIZE = 10;//保存数组的长度。private int capacity;//定义一个数组用于保存循环队列的元素private Object[] elementData;//保存循环队列中元素的当前个数private int front = 0;private int rear = 0;//以默认数组长度创建空循环队列public LoopQueue() {capacity = DEFAULT_SIZE;elementData = new Object[capacity];}//以一个初始化元素来创建循环队列public LoopQueue(T element) {this();elementData[0] = element;rear++;}/*** 以指定长度的数组来创建循环队列* @param element 指定循环队列中第一个元素* @param initSize 指定循环队列底层数组的长度*/public LoopQueue(T element , int initSize) {this.capacity = initSize;elementData = new Object[capacity];elementData[0] = element;rear++;}//获取循环队列的大小public int length() {if (empty()){return 0;}return rear > front ? rear - front: capacity - (front - rear);}//插入队列public void add(T element) {if (rear == front && elementData[front] != null) {throw new IndexOutOfBoundsException("队列已满的异常");}elementData[rear++] = element;//如果rear已经到头，那就转头rear = rear == capacity ? 0 : rear;}//移除队列public T remove() {if (empty()) {throw new IndexOutOfBoundsException("空队列异常");}//保留队列的rear端的元素的值T oldValue = (T)elementData[front];//释放队列的rear端的元素elementData[front++] = null;//如果front已经到头，那就转头front = front == capacity ? 0 : front;return oldValue;}//返回队列顶元素，但不删除队列顶元素public T element() {if (empty()) {throw new IndexOutOfBoundsException("空队列异常");}return (T)elementData[front];}//判断循环队列是否为空队列public boolean empty(){//rear==front且rear处的元素为nullreturn rear == front && elementData[rear] == null;}//清空循环队列public void clear() {//将底层数组所有元素赋为nullArrays.fill(elementData , null);front = 0;rear = 0;}public String toString() {if (empty()) {return "[]";}else{//如果front < rear，有效元素就是front到rear之间的元素if (front < rear){StringBuilder sb = new StringBuilder("[");for (int i = front ; i < rear ; i++ ){sb.append(elementData[i].toString() + ", ");}int len = sb.length();return sb.delete(len - 2 , len).append("]").toString();}//如果front >= rear，有效元素为front->capacity之间、0->front之间的else{StringBuilder sb = new StringBuilder("[");for (int i = front ; i < capacity ; i++ ) {sb.append(elementData[i].toString() + ", ");}for (int i = 0 ; i < rear ; i++){sb.append(elementData[i].toString() + ", ");}int len = sb.length();return sb.delete(len - 2 , len).append("]").toString();}}}}
1.1.2、线性表之队列(queue)-链式存储结构及实现-Demo
1、链式存储结构及实现-Demopublic class LinkQueue<T> {//保存该链队列的头节点private Node front;//保存该链队列的尾节点private Node rear;//保存该链队列中已包含的节点数private int size;//定义一个内部类Node，Node实例代表链队列的节点。private class Node {//保存节点的数据private T data;//指向下个节点的引用private Node next;//无参数的构造器public Node() {}//初始化全部属性的构造器public Node(T data , Node next){this.data = data;this.next = next;}}//创建空链队列public LinkQueue() {//空链队列，front和rear都是nullfront = null;rear = null;}//以指定数据元素来创建链队列，该链队列只有一个元素public LinkQueue(T element) {front = new Node(element , null);//只有一个节点，front、rear都指向该节点rear = front;size++;}//返回链队列的长度public int length(){return size;}//将新元素加入队列public void add(T element) {//如果该链队列还是空链队列if (front == null) {front = new Node(element , null);//只有一个节点，front、rear都指向该节点rear = front;}else{//创建新节点Node newNode = new Node(element , null);//让尾节点的next指向新增的节点rear.next = newNode;//以新节点作为新的尾节点rear = newNode;}size++;}//删除队列front端的元素public T remove() {Node oldFront = front;front = front.next;oldFront.next = null;size--;return oldFront.data;}//访问链式队列中最后一个元素public T element() {return rear.data;}//判断链式队列是否为空队列public boolean empty() {return size == 0;}//清空链队列public void clear() {//将front、rear两个节点赋为nullfront = null;rear = null;size = 0;}public String toString() {//链队列为空链队列时if (empty()) {return "[]";}else{StringBuilder sb = new StringBuilder("[");for (Node current = front ; current != null ; current = current.next ){sb.append(current.data.toString() + ", ");}int len = sb.length();return sb.delete(len - 2 , len).append("]").toString();}}}
若有收获，就点个赞吧
0 人点赞
