java编程中数据结构与算法之队列详解

一、队列的定义

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。故队列又称为先进先出（FIFO—first in first out）线性表。

二、顺序队列

每次在队尾插入一个元素是，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。

顺序队列中的溢出现象：

（1） "下溢"现象：当队列为空时，做出队运算产生的溢出现象(数组已经为空了继续取出元素没有意义)。“下溢”是正常现象，常用作程序控制转移的条件。

（2）"真上溢"现象：当队列满时，继续做进栈运算产生空间溢出的现象(数组越界)。“真上溢”是一种出错状态，应设法避免。

（3）"假上溢"现象：由于头尾指针都不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了"上溢"现象。

顺序队列的数组实现

package com.jalja.org.arith;public class MySeQuence { private Object [] arr; private int maxSize; private int index;//当前有效数据指针 private int front;//队头指针front private int rear;//队尾指针rear public MySeQuence(int maxSize){ this.arr=new Object[maxSize]; this.front=0; this.rear=0; this.index=0; this.maxSize=maxSize; } //加入队列 public void push(E e) { arr[rear]=e; rear++; index++; } //出队列 public E pop() { if(isNull()) { throw new RuntimeException("MySeQuence is null"); } E e=(E)arr[front]; front++; index--; return e; } //查询队列内元素的个数 public int getSize() { return index; } //判断队列是否为空 public boolean isNull() { return front==rear; } //队列是否满了 true=满了 public boolean isFull() { return rear==maxSize; } public static void main(String[] args) { MySeQuence myQueue=new MySeQuence(3); myQueue.push(1); myQueue.push(2); myQueue.push(3); System.out.println(String.format("元素个数:%s",myQueue.getSize())); System.out.println(String.format("队列是否满了:%s",myQueue.isFull())); while(!myQueue.isNull()) { System.out.println(myQueue.pop()); } System.out.println(String.format("元素个数:%s",myQueue.getSize())); System.out.println(String.format("队列是否为空:%s",myQueue.isNull())); }}

该实现会出现假上溢，当然这也是顺序队列的特点。我们一般使用循环队列解决这种问题。

三、循环队列

把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。

循环队列实现原理：

1、无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置,可用取余运算rear%MaxSize和front%MaxSize来实现。

2、在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize+1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了；因此，队列判空的条件时front=rear，而队列判满的条件时front=rear%MaxSize。

循环队列数组的实现

package com.jalja.org.arith;public class MyCirQuence { private Object [] arr; private int maxSize; private int index;//当前有效数据指针 private int front;//队头指针front private int rear;//队尾指针rear public MyCirQuence(int maxSize){ this.arr=new Object[maxSize+1]; this.front=0; this.rear=0; this.index=0; this.maxSize=maxSize; } //加入队列 在除法计算中 余数一定要比除数小 public void push(E e) { if(isFull()) { throw new RuntimeException("MySeQuence is full"); } arr[rear%maxSize]=e; //数组的下表在循环 rear%maxSize rear++;//real 一直在增加 index++; } //出队列 余数一定要比除数小 public E pop() { if(isNull()) { throw new RuntimeException("MySeQuence is null"); } E e=(E)arr[front%maxSize]; front++; index--; return e; } //查询队列内元素的个数 public int getSize() { return index; } //判断队列是否为空 public boolean isNull() { return front==rear; } //队列是否满了 true=满了 public boolean isFull() { return !isNull() && front==rear%maxSize; } public static void main(String[] args) { MyCirQuence myQueue=new MyCirQuence(3); myQueue.push(1); myQueue.push(2); myQueue.push(3); System.out.println("==>:"+myQueue.pop()); System.out.println("==>:"+myQueue.pop()); System.out.println("==>:"+myQueue.pop()); myQueue.push(4); myQueue.push(5); myQueue.push(6); while(!myQueue.isNull()) { System.out.println(myQueue.pop()); } }}

每天用心记录一点点。内容也许不重要，但习惯很重要！