队列的接口
package edu.lqstudy.chaptor.chaptor22.queue;
public interface Queue {
/**插入一个元素到队列尾部*/
public void enQueue(Object obj) throws Exception;
/**删除队列头部的元素，并且返回其值*/
public Object deQueue() throws Exception;
/**获取队列头部的值，但是不删除*/
public Object queueFront() throws Exception;
/**判断队列是否为空*/
public boolean isEmpty();
}
队列的实现方式
这里有两种实现方式，一种是顺序存储结构，另一种是链式存储结构
添加元素移动tail的值，删除元素移动head的值
顺序存储结构实现队列
package edu.lqstudy.chaptor.chaptor22.queue;
/**
* 循环队列，head指向的位置没有值，这是为了区分队列满和空的必要妥协
*
* @author hacker
*
*/
public class SeqQueue implements Queue{
private Object[] queue;//队列的数据区
private int head = 0;//（head + 1）%size为队列的头部
private int tail = 0;//队列的尾部
private int size = 0;//queue数组的容量，队列的容量为size - 1
/**
* 无参构造函数，队列的容量默认为10
*
*/
SeqQueue(){
size = 10 + 1;
queue = new Object[size];
}
/**
* 构造函数，根据给定的n生成容量为n的队列，
*
* @param int n
*/
SeqQueue(int n){
queue = new Object[n + 1];
size = n + 1;
}
@Override
public void enQueue(Object obj) throws Exception {
// TODO Auto-generated method stub
if(isFull()){
throw new Exception("队列已满");
}
else{
tail = (tail + 1)%size;
this.queue[tail] = obj;
}
}
@Override
public Object deQueue() throws Exception {
// TODO Auto-generated method stub
Object obj = null;
if(isEmpty()){
throw new Exception("队列已空");
}
else{
head = (head + 1)%size;
obj = queue[head];
}
return obj;
}
@Override
public Object queueFront() throws Exception {
// TODO Auto-generated method stub
Object obj = null;
if(isEmpty()){
throw new Exception("队列已空");
}
else{
int index = (head + 1)%size;
obj = queue[index];
}
return obj;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return tail == head;
}
/**
* 判断队列是否已满
* @return boolean
*/
public boolean isFull(){
return (tail + 1)%size == head;//如果tail在向前走一步等于head，
//说明队列已经饶了一圈，则已经满了
}
/**
* 返回队列中元素的个数
* @return int
*/
public int getLength(){
return (size + tail - head)%size;//如果tail > head,值为tail - head
//如果tail < head 值为size - (head - tail),都是元素的个数
}
/**
* 返回描述对象信息的String对象
* 格式为：
* 初始大小：（int）
* head值： （int）
* tail值： （int）
* size值： （int）
*
*/
public String toString(){
String s = "初始大小" + getLength() + "\nhead值：" +
head + "\ntail值: " + tail + "\nsize值： " + size;
return s;//
}
}
链式结果实现队列
package edu.lqstudy.chaptor.chaptor22.queue;
/**
* 使用链式存储结构实现队列，实现了两个类：
* Node类：结点类，相当于集合的元素
* LinkQueue类：相当于存储元素的集合
* @author hacker
*
*/
public class LinkQueue implements Queue{
private Node head;//指向队列头元素
private Node tail;//指向队列尾元素
private int len;//添加，删除数据时改变len的值
/**构造函数*/
LinkQueue(){
head = tail = null;
len = 0;
}
@Override
public void enQueue(Object obj) throws Exception {
// TODO Auto-generated method stub
Node n = new Node(obj);
if(isEmpty()){
head = tail = n;//如果添加元素到空队列，说明head值会改变
//并且tail之前的值为null；
}
else{
tail.setNext(n);//原结点指向新生成的结点
tail = n;
}
len++;
}
@Override
public Object deQueue() throws Exception {
// TODO Auto-generated method stub
Object ans = null;
if(isEmpty())
throw new Exception("从空队列中移除对象是不予许的");
else{
Node n = head;//获取头结点
head = head.getNext();//将head指针指向下一个结点
len--;
if(isEmpty())//如果删除的是最后一个元素，说明tail的值也发生了变化
tail = null;
ans = n.getObj();
}
return ans;
}
@Override
public Object queueFront() throws Exception {
// TODO Auto-generated method stub
Object obj = null;
if(isEmpty())
throw new Exception("从空队列中查找元素是不予许的");
else{
Node n = head;
obj = n.getObj();
}
return obj;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return len == 0;
}
public int length(){
return len;
}
}
class Node{
private Object obj;//存储的对象
private Node next = null;//下一个对象的指针
public Node(){
obj = null;
}
public Node(Object obj){
this.obj = obj;
}
public Node(Object obj,Node next){
this(obj);
this.next = next;
}
public Object getObj(){
return obj;
}
public Node getNext(){
return next;
}
public void setNext(Node next){
this.next = next;
}
}
