数据结构之队列的java实现

队列在计算机术语中使用queue,和list(排)其实是一个意思。队列也是一种数据结构，类似于栈，只是与栈相反，在队列中最先插入的数据也最先被移除，即先进先出(FIFO,First In First Out)。队列可以理解成排队，比如，食堂窗口排的队，越在前面的，越早得到服务而先离开。在银行大厅的排号的机器也许就用了队列这个数据结构。在打印的时候，有“添加到队列”的选项，队列应用是很广泛的。
队列的操作有：插入到队尾数据项，移除队头数据项，查看数据项等功能。

下面用Java实现队列的基本功能（数组版）。

package cn.zhf.list;
public class MyQueue {
    private int maxSize;//定义最大容量
    private int[] qarray;//存放元素的数组
    private int front;//前一个元素索引
    private int rear;//后一个元素索引
    private int nItems;//队列中元素的个数
    //构造对象并初始化
    public MyQueue(int s){
        maxSize = s;
        qarray = new int[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }
    //在队列尾端插入元素
    public void enqueue(int i){
        if(rear == maxSize - 1){
            rear = -1;
        }
        qarray[++rear] = i;
        nItems++;
    }
    //删除队首元素
    public int dequeue(){
        int temp = qarray[front++];
        if(front == maxSize){
            front = 0;
        }
        nItems--;
        return temp;
    }
    public int peekFront(){//取第一个元素
        return qarray[front];
    }
    public boolean isEmpty(){
        return (nItems == 0);
    }
    public static void main(String[] args) {
        MyQueue queue = new MyQueue(5);
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        queue.enqueue(4);
        queue.enqueue(5);
        while(!queue.isEmpty()){
            int i = queue.dequeue();
            System.out.println(i);
        }
    }
}

下面是用链表实现的队列。

package cn.zhf.list;
//其中的Link和LinkList两类同栈中的相同
public class LinkQueue {
        private LinkList list;
        public LinkQueue(){
            list = new LinkList();
        }
        public boolean isEmpty(){
            return list.isEmpty();
        }
        public void insert(int id,double dd){
            list.insertFirst(id, dd);
        }
        public Link delete(){
            return list.deleteFirst();
        }
        public void display(){
            list.displayLink();
        }
    public static void main(String[] args) {
        LinkQueue lq = new LinkQueue();
        lq.insert(12, 20.0);
        lq.insert(13, 20.1);
        lq.insert(14, 20.2);
        lq.display();
        System.out.println("-----------");
        lq.delete();
        lq.display();
    }
}

运行结果：

14,20.2
13,20.1
12,20.0
-----------
13,20.1
12,20.0