本文共 4828 字，大约阅读时间需要 16 分钟。

队列

队列（queue）是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。

队列的抽象数据类型

package pers.zhang.queue;/** * @author zhang * @date 2020/1/17 - 11:35 * * 队列的接口 */public interface QQueue
   
     {
       //判断队列是否为空    boolean isEmpty();    //元素x入队    void enqueue(T x);    //出队，返回队头元素    T dequeue();}
   

队列的实现

顺序队列

存在假溢出问题！不建议使用

顺序循环队列

package pers.zhang.queue;/** * @author zhang * @date 2020/1/17 - 11:45 * * 顺序循环队列 */public class SeqQueue
   
     implements QQueue
    
      {
       //存储队列数据的Object数组    private Object element[];    //队头和队尾引用    private int front, rear;    //构造    public SeqQueue(int length){
           if(length < 64)            length = 64;        this.element = new Object[Math.abs(length)];//设置队列容量最小值        this.front = this.rear = 0;//构造空队列    }    //默认构造    public SeqQueue(){
           this(64);    }    //判断队列是否为空    @Override    public boolean isEmpty() {
           return this.front == this.rear;    }    //元素x入队，空对象不能入队    @Override    public void enqueue(T x) {
           if(x == null)            return;        if(this.front == (this.rear + 1) % this.element.length){
   //队满，扩容            Object[] temp = this.element;            this.element = new Object[temp.length * 2];//重新申请一个数组            int j = 0;            for(int i = this.front; i != this.rear; i = (i + 1) % temp.length)                this.element[j++] = temp[i];        }        this.element[this.rear] = x;//插入数据        this.rear = (this.rear + 1) % this.element.length;//移动队尾    }    //出队，返回队头元素    @Override    public T dequeue() {
           if(isEmpty())//空队列返回null            return null;        T temp = (T) this.element[this.front];        this.front = (this.front + 1) % this.element.length;        return temp;    }    @Override    public String toString(){
                        //返回队列所有元素的描述字符串，形式为“(,)”，按照队列元素次序        String str = "(";        if (!isEmpty()){
               str += this.element[this.front].toString();            int i = (this.front+1) % this.element.length;            while(i != this.rear){
                   str += ", "+this.element[i].toString();                i = (i + 1) % this.element.length;            }        }        return str + ")";    }}
    
   

链式队列

package pers.zhang.queue;import pers.zhang.linearList.Node;/** * @author zhang * @date 2020/1/17 - 12:48 * * 链式队列 */public class LinkedQueue
   
     implements QQueue
    
      {
       //头节点和尾节点引用    private Node
     
       front, rear;    //构造空队列    public LinkedQueue(){
           this.front = this.rear = null;    }    //判断队列是否为空    @Override    public boolean isEmpty() {
           return this.front == null && this.rear == null;    }    //元素x入队，空对象不操作    @Override    public void enqueue(T x) {
           if(x == null)            return;        Node
      
        q = new Node
       
        (x, null);        if(this.front == null)            this.front = q;//空队插入        else            this.rear.next = q;//插入队尾        this.rear = q;    }    //出队，返回队头元素    @Override    public T dequeue() {
           if(isEmpty())            return null;        T temp = this.front.data;        this.front = this.front.next;//删除队头节点        if(this.front == null)            this.rear = null;        return temp;    }    //返回队列所有元素的描述字符串，形式为“(,)”    @Override    public String toString(){
   //算法同不带头结点的单链表        String str = "(";        for (Node
        
          p=this.front; p!=null; p=p.next){ str += p.data.toString(); if (p.next != null) str += ", "; //不是最后一个结点时后加分隔符 } return str + ")"; //空表返回() }}
        
       
      
     
    
   

测试

package pers.zhang.queue;/** * @author zhang * @date 2020/1/17 - 12:55 */public class Queue_ex {
       public static void main(String args[])    {
           SeqQueue
   
     que = new SeqQueue
    
     (5);        que.enqueue(new Integer(10));        que.enqueue(new Integer(20));        System.out.println("dequeue : "+que.dequeue().toString()+"  "+que.dequeue().toString()+"  ");        System.out.println(que.toString());        que.enqueue(new Integer(30));        que.enqueue(new Integer(40));        que.enqueue(new Integer(50));        que.enqueue(new Integer(60));        System.out.println(que.toString());        que.enqueue(new Integer(70));        System.out.println(que.toString());        LinkedQueue
     
       q = new LinkedQueue
      
       ();        System.out.print("enqueue: ");        for (int i=1; i<=5; i++)        {
               Integer intobj = new Integer(i);            q.enqueue(intobj);            System.out.print(intobj+"  ");        }        System.out.println("\n"+q.toString());        System.out.print("dequeue : ");        while (!q.isEmpty())            System.out.print(q.dequeue().toString()+"  ");        System.out.println();    }}/*dequeue : 10  20  ()(30, 40, 50, 60)(30, 40, 50, 60, 70)enqueue: 1  2  3  4  5  (1, 2, 3, 4, 5)dequeue : 1  2  3  4  5  */
      
     
    
   

转载地址：http://nypqb.baihongyu.com/