本文根据《大话数据结构》一书,实现了Java版的循环队列、链队列。
队列:只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
1.循环队列
队列的顺序储存结构:用数组存储队列,引入front指针指向队头元素,rear指针指向队尾元素的下一个位置,当front=rear时,为空队列,结构如下图所示。
当执行入队操作时,若数组尾部已满,而数组前部因有元素出队而有空位时,我们把新插入的元素从头开始入队,这样就类似于头尾相接的结构。
队列的这种头尾相接的顺序存储结构称为循环队列,如下图所示。
上面队列的定义中提到,当front=rear时,为空队列,而在循环队列中,队列满时,front也等于rear,将无法判断队满和空的情况。
一种办法是设置一个标志变量flag,当front=rear时,通过判断flag是0还是1来确定队列满空情况;
另一种方法是,在数组中只剩一个空闲单位时,定义为队列满,如下图所示。(本文程序采用这种办法)
因为rear可能比front大,也可能比front小,所以队列满的条件应该为:(rear+1)%maxSize==front;同理,队列长度的计算公式为:(rear-front+maxSize)%maxSize。
实现程序:
/** * <循环队列> * * 注意点:表长的表示、队列满的判断、front和rear的改变 * * @author Lai * */ public class SqQueue<E> { private E[] data; private int front; private int rear; private int maxSize; private static final int DEFAULT_SIZE= 10; /* * 初始化 */ public SqQueue(){ this(DEFAULT_SIZE); } public SqQueue(int maxSize){ data=(E[]) new Object[maxSize]; this.maxSize=maxSize; front=0; rear=0; } /* * 求循环队列长度 */ public int getLength() { return (rear-front+maxSize)%maxSize; } /* * 入队操作 */ public void enQueue(E e) { if((rear+1)%maxSize==front) throw new RuntimeException("队列已满,无法入队!"); data[rear]=e; rear=(rear+1)%maxSize; //不是rear=rear+1,当rear在数组尾部时,后移一位会转到数组头部 } /* * 出队操作 */ public E deQueue() { if(rear==front) throw new RuntimeException("队列为空!"); E e=data[front]; front=(front+1)%maxSize; //不是front++,理由同rear return e; } /* * 打印操作 */ public void printQueue() { int k=front; for(int i=0;i<getLength();i++) { System.out.print(data[k]+" "); k=(k+1)%maxSize; } System.out.println(); } /* * 测试代码 */ public static void main(String[] args) { SqQueue<String> aQueue=new SqQueue<>(5); aQueue.enQueue("a"); aQueue.enQueue("b"); aQueue.enQueue("c"); aQueue.enQueue("d"); aQueue.printQueue(); System.out.println("-----"); aQueue.getLength(); aQueue.deQueue(); aQueue.deQueue(); aQueue.enQueue("e"); aQueue.printQueue(); } }
a b c d ----- c d e
2.队列的链式存储结构
用单链表存储队列,称为链队列。
定义front指针指向头结点,rear指针指向终端结点,空队列时,front和rear都指向头结点。
实现程序:
/** * 链队列 * * 注意点:出队操作时,若队头是队尾(即队中仅有一个结点),则删除后要将rear指向头结点。 * * @author Yongh * * @param <E> */ public class LinkQueue<E> { private QNode front,rear; private int count; class QNode{ E data; QNode next; public QNode(E data,QNode next) { this.data=data; this.next=next; } } public LinkQueue() { front=new QNode(null, null); rear=front; count=0; } /* * 入队操作 */ public void enQueue(E e) { QNode node=new QNode(e, null); rear.next=node; rear=node; count++; } /* * 出队操作 */ public E deQueue() { if(rear==front) throw new RuntimeException("队列为空!"); QNode node=front.next; E e=node.data; front.next=node.next; //若队头是队尾,则删除后要将rear指向头结点。 if(rear==node) rear=front; node=null; count--; //通过count来判断,可能更容易理解 //if(count==0) // rear=front; return e; } /* * 获取队列长度 */ public int getLength() { return count; } /* * 打印输出队列 */ public void printQueue() { if(count==0) { System.out.println("空队列"); }else { QNode node=front; for(int i=0;i<count;i++) { node=node.next; System.out.print(node.data+" "); } System.out.println(); } } /* * 测试代码 */ public static void main(String[] args) { LinkQueue<String> lQueue =new LinkQueue<>(); lQueue.printQueue(); lQueue.enQueue("A"); lQueue.enQueue("B"); lQueue.enQueue("c"); lQueue.enQueue("D"); lQueue.printQueue();
lQueue.deQueue(); lQueue.deQueue(); lQueue.enQueue("E"); lQueue.printQueue(); } }
空队列
A B c D
c D E
3.循环队列和链队列的选择
基本操作时间都为O(1)。但链队列每次申请和释放结点会存在一点时间开销,且其需要存储一个指针域;而循环队列必须固定空间长度,存在空间浪费问题,且没链队列灵活。
综上,在可以确定队列长度最大值的情况下,建议用循环队列;当无法预估队列的长度时,使用链队列。