循环顺序队列类 ！
循环顺序队列，在逻辑上是一个循环，也就是队首和队尾连接
循环顺序队列，在物理上就是一个数组 。
循环顺序队列类Java语言描述【SqQueue】
—— 实现队列接口IQueue
package data.linear_table.stack_queue; //循环队列类 public class SqQueue implements IQueue { private Object[] queueElem ; //队列的存空间 private int front ; //队首的引用，若队列不为空，指向队首元素 private int rear ; //队尾的引用，若队列不为空，指向队尾元素的下一个存储位置 //循环队列类的构造函数 public SqQueue(int maxSize) { front = rear = 0 ; //队首、队尾初始化为0 queueElem = new Object[maxSize] ; //为队列分配maxSize个存储单元 } //队列置空 @Override public void clear() { front = rear = 0 ; } //判断队列是否为空 @Override public boolean isEmpty() { return front == rear; } //求队列的长度 @Override public int length() { //（尾 - 头 + 队列长度） % 队列长度 return (rear - front + queueElem.length)%queueElem.length ; } //读取队首元素 @Override public Object peek() { if (front == rear) { //队列为空 return null ; }else { //返回队首元素 return queueElem[front]; } } //入队 @Override public void offer(Object x) throws Exception { //{..... } } //出队 @Override public Object poll() { //{..... } return null ; } //输出队列中的所有数据元素（从队首到队尾） public void display () { //队列不为空 if (!isEmpty()) { for (int i = front ; i != rear ; i = (i+1)% queueElem.length ) { System.out.print(queueElem[i].toString()+" "); } }else { System.out.println("此队列为空"); } } }
注： 代码中 ” {....}“ 处，会在后面单独进行讲解。
算法：入队
//入队 @Override public void offer(Object x) throws Exception { //判断是否已经满了，如果已经满了，抛异常 //例头front = 0 ; rear = 4 ； 即queueElem.length = 5 ； //即：(rear+1) % queueElem.length = 5 % 5 = 0 = front ；满足，即队列满 if ( (rear+1) % queueElem.length == front) { throw new RuntimeException("队列满了"); }else { //没有满进行入队操作 //入队只能从队尾进行添加。队尾rear queueElem[rear] = x ; rear = (rear + 1) % queueElem.length ; //队尾rear累加1 ， 但最后时需要归零 } }
//出队 @Override public Object poll() { if (front == rear) { //队列为空 return null ; }else { Object t = queueElem[front] ; //记录出队的元素 front = (front+1) % queueElem.length ; //重新赋值队首+1 ，并且要归0 return t ; //返回队列的队首元素 } }
(八) 链队列
一、什么是链队列？
队列采用链式存储结构的队列叫链队列。
用两个指针front和rear 来分别队首元素和队尾元素。
二、链队列类【LinkQueue】
链表所需结点类：
package data.linear_table.node; //单链表：结点类 public class Node { public Object data ; //存放结点值 public Node next ; // 后继结点的引用 //无参时的构造函数 public Node() { this(null,null); } //带一个参数时的构造函数 public Node(Object data) { this(data,null); } //带两个参数时的构造函数 public Node(Object data , Node next) { this.data = data ; this.next = next ; } }
LinkQueue类
package data.linear_table.stack_queue; import data.linear_table.node.Node; //链队列类 public class LinkQueue implements IQueue { private Node front ; //队首指针 private Node rear ; //队尾指针 //链队列类的构造函数 public LinkQueue () { front = rear = null ; } //队列置空 @Override public void clear() { front = rear = null ; } //判断队列是否为空 @Override public boolean isEmpty() { return front == null ; } //求队列的长度 @Override public int length() { Node p = front ; int length = 0 ; while (p != null ){ p = p.next ; length++ ; } return length ; } //取首元素 @Override public Object peek() { if (front != null ) { //队列非空 return front.data ; //返回队首结点数据域值 } else { return null ; } } //入队 @Override public void offer(Object x) throws Exception { //{...} } //出队 @Override public Object poll() { //{...} return null } }
注： 代码中 ” {....}“ 处，会在后面单独进行讲解。
算法：入队
//入队 @Override public void offer(Object x) throws Exception { Node p = new Node(x) ; //初始化新结点 if (front != null) { //队列非空 rear.next = p ; //指向队尾指向新结点 rear = p ; //改变队尾的位置 }else { //队列为空的话，新添加的这个就是队首元素 front = rear = p ; } }
算法：出队
//出队 @Override public Object poll() { if (front != null ) { //队列非空 Node p = front ; //p指向队首结点,记录被删除的结点 front = front.next ; //队首结点移动到下一个 if (p == rear ) { //只有应该元素，删除的队首结点是队尾时 rear = null ; } return p.data ; //返回被删除的队首元素的数据域值 }else { return null ; } } }
