一、队列的概念：
队列（简称作队，Queue）也是一种特殊的线性表，队列的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置插入和删除，而队列只允许在其一端进行插入操作在其另一端进行删除操作。
队列中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头。队列的插入操作通常称作入队列，队列的删除操作通常称作出队列。
下图是一个依次向队列中插入数据元素a0,a1,...,an-1后的示意图：
上图中，a0是当前 队头数据元素，an-1是当前 队尾数据元素。
为了避免当只有一个元素时，对头和队尾重合使得处理变得麻烦，所以引入两个指针：front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样的话，当front指针等于rear时，此队列不是还剩一个元素，而是空队列。
二、队列的抽象数据类型：
数据集合：
队列的数据集合可以表示为a0,a1,…,an-1，每个数据元素的数据类型可以是任意的类型。
操作集合：
（1）入队列append(obj)：把数据元素obj插入队尾。
（2）出队列delete()：把队头数据元素删除并由函数返回。
（3）取队头数据元素getFront()：取队头数据元素并由函数返回。
（4）非空否isEmpty()：非空否。若队列非空，则函数返回false，否则函数返回true。
三、循环顺序队列：
线性表有顺序存储和链式存储，队列是一种特殊的线性表，同样也存在这两种存储方式。我们先来看一下队列的顺序存储。
1、顺序队列的“假溢出”：
上图中，front指针指向队头元素，rear指针指向队尾元素的下一个位置。图(d)中b、c、d出队后，front指针指向元素e，rear指针在数组外面。假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经被占用，再向后加就会产生数组越界的错误，可实际上队列在下标为0、1、2、3、4的地方还是空闲的，我们把这种现象叫做“假溢出”。
2、循环顺序队列：
所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种逻辑上首尾相连的顺序存储结构称为循环队列。
如何判断循环队列究竟是空的还是满的：
现在问题又来了，我们之前说，空队列时，front指针等于rear指针，那么现在循环队列满的时候，也是front等于rear，那么如何判断循环队列究竟是空的还是满的？有如下办法：
办法1：设置一个标志位flag。初始时置flag=0；每当入队列操作成功就置flag=1；每当出队列操作成功就置flag=0。则队列空的判断条件为：rear == front && tag==0；队列满的判断条件为：rear = = front && tag= =1。
办法2：保留一个元素的存储空间。此时，队列满时的判断条件为 (rear + 1) % maxSize == front；队列空的判断条件还是front == rear。
办法3：设计一个计数器count，统计队列中的元素个数。此时，队列满的判断条件为：count > 0 && rear == front ；队列空的判断条件为count == 0。
我们在接下来的代码中采用方法3来实现。
3、代码实现：(循环顺序队列的创建)
/**
* 使用环形数组，解决上面数组使用一次就不能用的问题
*将这个数组使用算法，改进成一个环形的队列,使用取模%的方式
* @author syw
*思路如下
*1.front变量的含义调整一下，将front不再指向队头的前一个元素，而是指向队头，既arr[front]为队头,front的初始值为0
*2.rear也调整一下，将rear不再指向最后一个元素，而是最后一个元素的后一个位置。因为希望空出一个空间作为约定，rear的初始值也为0
*注意：预留的位置是动态变化的，始终在rear后面,预留空间的目的是为了区别队空和队满
*3.当队列满时，（rear+1）%maxSize==front,这里取模是为了找到rear的真实位置,因为rear随着取数据，插入数据。可能在front的前面。
*注意maxSize是数组的长度，从0到maxSize-1，一共maxSize个区域。
* 例子：当没有取数据的时候front为0，此时实际数据最多只能到arr[maxSize-2],rear此时指向arr[maxSize-1],也就是预留的空间，此时(rear+1)%maxSize=0=front;
* 当取出一个数据的时候，此时front为1，rear不变，还是maxSize-1,再插入一个数据 到（rear+1）%maxSize，则此时rear指向0（预留空间的位置），插入的数据在arr[maxSize-1],也就是最后一个数据
* 此时 (rear+1)%maxSize=1=front(满)
*4.当队列空时候依然是 rear==front
*5.队列中有效数据的个数 (rear+maxSize-front)%maxSize,例如maxSize为10,front=0,rear=4,此时明显有4个数据既arr[0],arr[1],arr[2],arr[3],
*因为rear指向最后一个元素的下一个元素，所以实际有三个 此时 （4+10-0）%10=4，例如 maxSize为10，front为8，rear为1(实际到a[0],因为rear指向最后一个元素的下一个元素)，
*此时(1+10-8)%10=3,也是三个元素，a[8],a[9],a[0]
*6.在原来的队列上修改变成环形队列
*/
public class RoundQueue {
public static void main(String[] args) {
//1.创建一个队列
RoundArrayQueue arrayQueue = new RoundArrayQueue(4);//这里设置的为4，但是有效数据最多为3个
char key=' ' ;//接受用户的输入
Scanner sc=new Scanner(System.in);
boolean loop=true;
while(loop) {
System.out.println("s(show):显示队列");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加数据到队列");
System.out.println("g(get):从队列中取出数据");
System.out.println("h(head):查看队列头部的数据");
key =sc.next().charAt(0);//接收一个字符
switch(key) {
case 's':
arrayQueue.showQueue();
break;
case 'a':
System.out.println("输入一个数");
int val=sc.nextInt();
arrayQueue.addQueue(val);
break;
case 'g':
try {
int res=arrayQueue.getQueue();//注意这里取出数据只能一个一个个取出
System.out.println("取出的数据是"+res);
}catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e':
sc.close();
loop=false;
break;
case 'h':
try {
int res=arrayQueue.headVal();
System.out.println("队列头部数据是\t"+res);
}catch(Exception e) {
System.out.println(e.getMessage());
}
break;
default:
break;
}
}
System.out.println("程序退出");
}
}
class RoundArrayQueue{
private int maxSize;//表示数组的最大容量
private int front ;//队列头 初始化为0
private int rear;//队列尾部 初始化为0
private int[] arr;//用于存放数据，模拟队列
//1.创建队列的构造器
public RoundArrayQueue(int arrMaxSize) {
maxSize=arrMaxSize;
arr=new int[maxSize]; //这里对数组进行大小初始化，如果不初始化不能存数据
front=0; //指向队列头部
rear=0;//指向队列最后一个元素的下一个元素。
}
//2.判断队列是否满
public boolean isFull() {
return (rear+1)%maxSize==front;
}
//3.判断队列是否为空
public boolean isEmpty() {
return rear==front;
}
//4,添加数据到队列
public void addQueue(int n) {
//判断队列是否满了
if(isFull()) {
System.out.println("队列满了，不能加入");
return ;
}
//如果不满，因为rear的含义是最后一个存在元素的向下一个元素，也就是待插入的位置
arr[rear]=n;
//将rear后移,这里不能直接后移，如果此时在最后一个，直接后移会下标越界，因为是循环队列，通过取模可以跑到前面来
rear=(rear+1)%maxSize;
}
//5,出队列，获取数据
public int getQueue() {
//判断队列是否为空
if(isEmpty()) {
//抛异常
throw new RuntimeException("队列空，不能取");//throw会自动return
}
//不为空，取数据
int temp=arr[front]; //先把front对应的值保存到一个临时变量
front=(front+1)%maxSize; //front后移，注意这里front也不能直接++，因为可能会是front从上面，循环到下面
return temp;
}
//6,显示队列的所有数据
public void showQueue() {
//遍历
if(isEmpty()) {
System.out.println("队列为空，没有数据");
return ;
}
//从front开始，到有效元素个数,否则无法遍历
int vallength=(rear+maxSize-front)%maxSize;//有效元素个数
for(int i=front;i<front+vallength;i++) {
//注意，此时下标为i%maxSize
System.out.println("arr["+i%maxSize+"]="+arr[i%maxSize]);
}
}
//7,显示队头，注意不是去除数据
public int headVal() {
if(isEmpty()) {
throw new RuntimeException("队列空");
}
return arr[front];
}
}四、链式队列：
链式队列其实就是特殊的单链表，只不过它只能尾进头出而已。链式队列的存储结构如下图所示：
1、链式队列的实现：
/**
* 链队列的相关操作的实现
*/
public class LinkQueueImpl implements LinkQueue{
public Node front;//队头
public Node end; //对尾
public int count;//队列长度
public LinkQueueImpl() {
init();
}
//初始化队列
public void init(){
front=end=null;
count=0;
}
@Override
public void appendLinkQueue(Object object) throws Exception {
//新的节点
Node node=new Node(object,null);
//原队尾的指针指向新的节点
if(end!=null){
end.setNext(node);
}
//尾指针指向新的节点
end=node;
//说明插入的是第一个节点
if(front==null){
front=node;
}
//个数增加
count++;
}
@Override
public Object popLinkQueue() throws Exception {
if(!isEmpty()){
//保存出队节点
Node node=front;
//出队
front=front.getNext();
count--;
//如果出队之后数目为0
if (count==0){
end=null;
}
return node.getData();
}else{
throw new Exception("队列为空");
}
}
@Override
public Object getFront() throws Exception {
if(!isEmpty()){
return front.getData();
}else{
return null;
}
}
@Override
public Boolean isEmpty() {
return count==0;
}
@Override
public void cleanLinkQueue() {
front=end=null;
count=0;
}
@Override
public void showLinkQueue() {
//引入一个辅助节点
Node temp=front;
//遍历
while (temp!=null){
System.out.println(temp.getData());
temp=temp.getNext();
}
}
}
class TestLinkQueue{
public static void main(String[] args) throws Exception {
LinkQueueImpl queue=new LinkQueueImpl();
queue.appendLinkQueue("123");
queue.appendLinkQueue("456");
queue.appendLinkQueue("789");
queue.showLinkQueue();
System.out.println(queue.front+":"+queue.end+":"+queue.count);
queue.popLinkQueue();
System.out.println(queue.front+":"+queue.end+":"+queue.count);
queue.cleanLinkQueue();
System.out.println(queue.front+":"+queue.end+":"+queue.count);
}
}
/**
* 定义队列中的节点
*/
class Node{
//数据域
private Object data;
//指针域
private Node next;
//头结点的创建方式
public Node(Object data) {
this.data = data;
}
//非头结点的构造
public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
//获取当前数据域的值
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
}
/**
* 声明队列中的方法
*/
interface LinkQueue{
//入队
public void appendLinkQueue(Object object) throws Exception;
//出队
public Object popLinkQueue()throws Exception;
//获取队头元素
public Object getFront()throws Exception;
//判断队列是否为空
public Boolean isEmpty();
//清空队列
public void cleanLinkQueue();
//遍历队列
public void showLinkQueue();
}2、循环队列和链式队列的比较：
（1）从时间上看，它们的基本操作都是常数时间，即O(1)的。不过循环队列是事先申请好空间，使用期间不释放；而链式队列，每次申请和释放结点也会存在一定的时间开销，如果入栈和出栈比较频繁，则两者还是有细微的差别。
（2）从空间上看，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链式队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链式队列更加灵活。
总结：总的来说，在可以确定队列长度的最大值的情况下，建议用循环队列，如果你无法估计队列的长度，那就用链式队列。
五、优先级队列：
优先级队列是带有优先级的队列。
用顺序存储结构实现的优先级队列称作顺序优先级队列。
用链式存储结构存储的优先级队列称作链式优先级队列。
顺序优先级队列和顺序循环队列相比主要有两点不同：
（1）对于顺序优先级队列来说，出队列操作不是把队头数据元素出队列，而是把队列中优先级最高的数据元素出队列。（入队操作没区别）
（2）对于顺序优先级队列来说，数据元素由两部分组成，一部分是原先意义上的数据元素，另一部分是优先级。通常设计优先级为int类型的数值，并规定数值越小优先级越高。
1、顺序优先队列的实现：
设计顺序优先级队列分为两个类：
数据元素类
优先级队列类
代码实现：
/**
* 数组实现的优先队列
*/
public class PrioritySequenceQueue implements PriorityQueue{
static final int defaultSize = 10; //默认队列长度
public int front; //队头
public int end;//队尾
public int count; //队列中的元素数量
public int maxSize; //队列最大长度
public Element[] queue; //队列
public PrioritySequenceQueue() {
init(defaultSize);
}
public PrioritySequenceQueue(int maxSize) {
init(maxSize);
}
public void init(int size){
front=end=0;
count=0;
maxSize=size;
queue=new Element[size];
}
@Override
public void EnQueue(Element element) throws Exception {
if(count>=maxSize){
throw new Exception("出错");
}else{
queue[end]=element;
end++;
count++;
}
}
@Override
public Object OutQueue() throws Exception {
if(isEmpty()){
throw new Exception("出错");
}else{
//假设第一个元素的优先级最高(越小越高)
Element min=queue[0];
int minIndex=0;
for(int i=0;i<count;i++){
if(queue[i].getPriority()<min.getPriority()){
//更新优先级最高的元素
min=queue[i];
minIndex=i;
}
}
//优先级最高的元素后面的元素后移
for (int i=minIndex+1;i<count;i++){
//从minIndex开始，每个元素都指向后面一个元素
queue[i-1]=queue[i];
}
end--;
count--;
return min;
}
}
@Override
public Object getFrontElement() throws Exception {
if(isEmpty()){
throw new Exception("出错");
}else {
//假设第一个元素为优先级最高的元素
Element min=queue[0];
int minIndex=0;
for(int i=0;i<count;i++){
if(queue[i].getPriority()<min.getPriority()){
//替换
min=queue[i];
minIndex=i;
}
}
return min;
}
}
@Override
public boolean isEmpty() {
return count==0;
}
}
interface PriorityQueue{
//入队
public void EnQueue(Element element) throws Exception;
//出队,默认取出优先级最高的元素
public Object OutQueue() throws Exception;
//查看优先级最高的元素
public Object getFrontElement() throws Exception;
//判断队列是否为空
public boolean isEmpty();
}
/**
* 优先队列的元素节点
*/
class Element{
private Object element;//数据
private int priority;//优先级
public Element(Object element, int priority) {
this.element = element;
this.priority = priority;
}
public Object getElement() {
return element;
}
public void setElement(Object element) {
this.element = element;
}
public int getPriority() {
return priority;
}
public void setPriority(int priority) {
this.priority = priority;
}
}六、队列的实际应用：
使用顺序循环队列和多线程实现一个排队买票的例子。而且，我们只允许这个队伍中同时排队的只有10个人，那就需要用到队列了。
生产者（等候买票）
消费者 (买票离开)
全部评论