Java顺序队列的定义~
顺序队列是三中队列之一，它是基于数组构造。具有队首front，队尾rear，元素数组element[]，和元素个数length等属性。
由于队列的形式有三种，顺序队列只是之一（还有链式队列和优先级队列），因此首先写一个结构等待实现
本文代码主要参考自《数据结构（Java版）》–叶核亚，也即本人的教材，在此基础上做修改或添加
package queue;public interface Queue<T> {/*** 由于加了尾指针，因此入队时间复杂性是O(1)* 队空条件队头队尾节点都是null* 该队列不需要头结点* @return*/public abstract boolean isEmpty();public abstract boolean add(T x);public abstract T peek();public abstract T poll();
}然后顺序队列定义如下：
本人在《数据结构（Java版）》–叶核亚 的基础上做了一些改动，加上了使用数组或顺序表ArrayList构造顺序队列，加上了获取队列元素个数的属性和方法，可以使队列用起来更方便
package queue;
import java.util.ArrayList;
import java.util.Iterator;/*** @author ZhaoKe and TextBook* @date: 2019年11月13日 下午7:27:38*/
public class SeqQueue<T> implements Queue<T> {private Object element[];private int front, rear;//@ author ZhaoKeprivate int length = 0;public SeqQueue(int length) {if (length < 64)length = 64;this.element = new Object[64];this.front = this.rear = 0;}//@ author ZhaoKepublic int getLength() {return this.length;}//@ author ZhaoKepublic SeqQueue(T[] values) {this();//没有这一句就会发生NullPointExceptionfor (int i = 0; i < values.length; i++) {this.add(values[i]);}}//@ author ZhaoKe//使用顺序表构造顺序队列public SeqQueue(ArrayList<T> values) {this();//没有这一句就会发生NullPointExceptionIterator<T> it = values.iterator();while (it.hasNext()) {T t = (T) it.next();this.add(t);}}public SeqQueue() {this(64);}@Overridepublic boolean isEmpty() {return this.front == this.rear;}@Overridepublic boolean add(T x) {if(x == null)return false;if (this.front == (this.rear+1) % this.element.length) {//如果队满,扩容之后原本的加入队列Object[] temp = this.element;this.element = new Object[temp.length*2];int j = 0;for (int i = 0; i != this.rear; i = (i+1)%temp.length)this.element[j++] = temp[i];this.front = 0;this.rear = j;}//然后加入x,修改队尾指针this.element[this.rear] = x;this.rear = (this.rear + 1) % this.element.length;this.length++;return true;}@SuppressWarnings("unchecked")@Overridepublic T peek() {return this.isEmpty() ? null : (T)this.element[this.front];}@Overridepublic T poll() {if(this.isEmpty())return null;@SuppressWarnings("unchecked")T temp = (T)this.element[front];this.front = (this.front + 1)% this.element.length;this.length--;return temp;}
}
看不懂的地方可以评论，最迟一节课时间就能改动或回复hhhhh~~
–CUST ZKe
Java顺序队列的定义~
顺序队列是三中队列之一，它是基于数组构造。具有队首front，队尾rear，元素数组element[]，和元素个数length等属性。
由于队列的形式有三种，顺序队列只是之一（还有链式队列和优先级队列），因此首先写一个结构等待实现
本文代码主要参考自《数据结构（Java版）》–叶核亚，也即本人的教材，在此基础上做修改或添加
package queue;public interface Queue<T> {/*** 由于加了尾指针，因此入队时间复杂性是O(1)* 队空条件队头队尾节点都是null* 该队列不需要头结点* @return*/public abstract boolean isEmpty();public abstract boolean add(T x);public abstract T peek();public abstract T poll();
}然后顺序队列定义如下：
本人在《数据结构（Java版）》–叶核亚 的基础上做了一些改动，加上了使用数组或顺序表ArrayList构造顺序队列，加上了获取队列元素个数的属性和方法，可以使队列用起来更方便
package queue;
import java.util.ArrayList;
import java.util.Iterator;/*** @author ZhaoKe and TextBook* @date: 2019年11月13日 下午7:27:38*/
public class SeqQueue<T> implements Queue<T> {private Object element[];private int front, rear;//@ author ZhaoKeprivate int length = 0;public SeqQueue(int length) {if (length < 64)length = 64;this.element = new Object[64];this.front = this.rear = 0;}//@ author ZhaoKepublic int getLength() {return this.length;}//@ author ZhaoKepublic SeqQueue(T[] values) {this();//没有这一句就会发生NullPointExceptionfor (int i = 0; i < values.length; i++) {this.add(values[i]);}}//@ author ZhaoKe//使用顺序表构造顺序队列public SeqQueue(ArrayList<T> values) {this();//没有这一句就会发生NullPointExceptionIterator<T> it = values.iterator();while (it.hasNext()) {T t = (T) it.next();this.add(t);}}public SeqQueue() {this(64);}@Overridepublic boolean isEmpty() {return this.front == this.rear;}@Overridepublic boolean add(T x) {if(x == null)return false;if (this.front == (this.rear+1) % this.element.length) {//如果队满,扩容之后原本的加入队列Object[] temp = this.element;this.element = new Object[temp.length*2];int j = 0;for (int i = 0; i != this.rear; i = (i+1)%temp.length)this.element[j++] = temp[i];this.front = 0;this.rear = j;}//然后加入x,修改队尾指针this.element[this.rear] = x;this.rear = (this.rear + 1) % this.element.length;this.length++;return true;}@SuppressWarnings("unchecked")@Overridepublic T peek() {return this.isEmpty() ? null : (T)this.element[this.front];}@Overridepublic T poll() {if(this.isEmpty())return null;@SuppressWarnings("unchecked")T temp = (T)this.element[front];this.front = (this.front + 1)% this.element.length;this.length--;return temp;}
}
看不懂的地方可以评论，最迟一节课时间就能改动或回复hhhhh~~
–CUST ZKe
发布评论