大话数据结构（十）java程序——队列

1、队列的定义

队列（queue）：是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的线性表，简称FIFO(First out firts in)。允许插入的一头是队尾，允许删除的一头是队头。

注意：

队列是线性表，也同样有类似线性表的各种操作，不同的就是插入数据只能在队尾进行，删除数据只能在队头进行。

2、循环队列

2.1 循环队列的定义

队列中front指针指向队头元素，rear指针指向队尾元素的下一个元素，这样当front==rear 时，此队列是空队列。

循环队列的定义是：队列头尾相接的顺序存储结构称为循环队列。

队列满的条件是：（rear+1）%Queuesize = front；

通用的计算队列长度的公式为：（rear-front+Queuesize)%Queue

2.2 队列的顺序存储

队列插入元素主要步骤：rear = (rear+1)%Queuesize;

队列删除元素主要步骤：front = (front+1)%Queuesize;

队列的顺序存储代码实现：

public class SqeQueue<E> {
   ArrayList<E>  queue = new ArrayList<E>();
   
   final int MAXSIZE = 20;//循环队列的长度
   int font;//对头
   int rear;//队尾
   /*
    * 队列构造函数
    */
   public SqeQueue(){
       initQueue();
   }
   /*
    * 队列初始化
    */
   public void initQueue(){
       font=0;
       rear=0;
   }
   /*
    * 队列的当前长度
    */
   public int getLength(){
       return (rear-font+1)%MAXSIZE;
   }
   /*
    * 入队，队是在队尾入队
    */
   public boolean addQueue(E e){
       //队列满的判断
       if((rear+1)%MAXSIZE == font){
           System.out.println("队满");
       }
       //将e赋给队尾
       queue.add(rear, e);
       //rear 后移一位
       rear =( rear+1) %MAXSIZE;
       return true;
   }
   public E deleteQueue(){
       //队列满的判断
       if(font == rear){
           System.out.println("队为空");
       }
       //队头元素赋值给e
       E e = queue.get(font);
       //对头后移一位
       font = (font+1)%MAXSIZE;
       return e;
   }
   
   public static void main(String args[]){
       SqeQueue<Object> sqeQueue = new SqeQueue<Object>();
       sqeQueue.addQueue("zzzzz");
       sqeQueue.addQueue("bbbbbb");
       sqeQueue.addQueue("333333");
       for(int i=0;i<=sqeQueue.getLength();i++){
           System.out.println(sqeQueue.deleteQueue());
       }
   }
}

3、队列的链式存储结构及实现

队列的链式存储结构，其实就是线性表的单链表，只不过它是尾进头出，我们把它简称为链队列。

队头指针指向链队列的头结点，队尾指针指向终端结点。

空队列时，front和rear都指向头结点。

入队操作时，其实就是在链表尾部插入结点。

出队操作时，其实就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素，则需要将rear指向头结点。

package com.aclie.dataStructe4.queue;

public class LinkQueue {
   Node2 rear;//队尾
   Node2 front;//队头
   int count=0;
   /*
    * 无参构造函数，初始化链表
    */
   public LinkQueue(){
       rear = front = null;
   }
   /*
    * 有参构造函数，初始化链表
    */
   public LinkQueue(Object obj){
       front = new Node2(obj);
       rear = front;
       count++;
   }
   /*
    * 得到链表的当前长度
    */
   public int getLinkLength(){
       return count;
   }
   /*
    * 入队，在队尾插入元素
    */
   public void addLinkQueue(Object obj){
      
       if(front == null){//空队列，插入元素
           front = new Node2(obj);
           rear = front;
       }else{//非空队列
           Node2 p = new Node2(obj);//要插入的结点
           rear.next2 = p;//将插入结点赋值给rear后继
           rear = p;//更改rear，rear指向插入的结点
           
       }
       count++;
   }
   public Object deleteLinkQueue(Object obj){
       if(rear == front){
           System.out.println("参数错误");
       }
       Node2 s =front;//将要删除的结点暂存为结点s
       Object data2= s.data;//获取要删除的元素
       front = s.next2;//将原队头结点后继s.next2 赋值给头结点后继
       if(rear == s){//若队头是队尾，则将删除后将rear指向队头
           rear = front;
       }
       s.next2 = null;//释放要删除结点
       count--;       
       return data2;//返回删除
     }
   
   public void printLinkQueue(){
       if(front == null){
           System.out.println("无打印的参数");
       }else{
           Node2 cur = front;
           while(cur != null){
               System.out.println(cur.data);
               cur = cur.next2;
           }
       }
      
   }
   public static void main(String args[]){
        LinkQueue linkQueue = new LinkQueue();
        linkQueue.addLinkQueue("222214");
        
        linkQueue.addLinkQueue("ewqtee");
        
        linkQueue.addLinkQueue("35432654");
    
        linkQueue.printLinkQueue();
        System.out.println("...........");
        linkQueue.deleteLinkQueue(linkQueue.front);
        linkQueue.deleteLinkQueue(linkQueue.front);
        linkQueue.deleteLinkQueue(linkQueue.front);
        linkQueue.printLinkQueue();
        
        
      } 
}
class Node2{
    Object data;//数字域
    Node2 next2;//指针域
    public Node2(Object d2){
        this.data = d2;
    }
}

4、总结

对应循环队列与链队列的比较，可以从以下两方面：

时间上：其实他们都是基本的常数时间，即O(1),不过循环队列是事先申请好的空间，使用期间不释放，而对于链队列，每次申请和释放存在一些时间开销，

如果入队出队频繁，则两者还是有细微差异的。

空间上：循环队列必须有一个固定的长度，这就造成了存储元素个数和空间上的浪费。而链队列不存在这个问题。尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以空间上，链队列更加灵活。

总得来说，在可以确定队列长度最大值情况下，建议用循环队列，如果无法预估队列长度，则用链队列。