java 实现数据结构之队列
队列是一种特殊的线性表，它只允许在表的前端(front)进行删除操作，只允许在表的后端（rear）进行插入操作。
1.队列的顺序存储结构及实现
public 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();}}}import java.util.Arrays;public 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();}}}}public class LinkQueue<T>{//定义一个内部类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;}}//保存该链队列的头节点private Node front;//保存该链队列的尾节点private Node rear;//保存该链队列中已包含的节点数private int size;//创建空链队列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();}}}