算法1.3 队列(FIFO)

先进先出队列

数组实现(Ex1_3_14)

import java.util.Iterator;
public class ArrayQueue<Item> implements Iterable<Item> {
    private Item[] a = (Item[]) new Object[1];
    private int N = 0;
    private int head = 0;//出队元素索引
    private int tail = 0;//入队元素索引
    public boolean isEmpty() {
        return N > 0;
    }
    public int size() {
        return N;
    }
    public void resize(int max) {
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0; i < N; i++) {
            temp[i] = a[i];
        }
        a = temp;
    }
    public void enqueue(Item item) {
        if (N == a.length) resize(2 * a.length);
        a[N++] = item;
        tail++;
    }//从队尾插入
    public Item dequeue() {
        Item item = a[--N];
        if (N == a.length / 4) resize(a.length / 2);
        head++;
        return item;
    }//从队首离开
    @Override
    public Iterator<Item> iterator() { return new ArrayIterator(); }
    private class ArrayIterator implements Iterator<Item> {
        private int i = head;
        @Override
        public boolean hasNext() { return i <= tail; }
        @Override
        public Item next() { return a[i++]; }
        @Override
        public void remove() { }
    }
}

要点

1. 两个int变量,head和tail作为索引,当元素入列,进入队尾,tail++;当元素出列,离开队首,head++,通过这种方法保证只有head和tail间的元素可以被操作

算法1.3 先进先出队列(链表实现)

import java.util.Iterator;
public class Queue<Item> implements Iterable<Item>{
    private Node first;
    private Node last;
    private int N;
    private class Node{
        Item item;
        Node next;
    }
    public boolean isEmpty(){ return N == 0 ;}
    public int size(){ return N;}
    public void enqueue(Item item){
        Node oldLast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if(isEmpty()) first = last ;//链表为空,first,last同时指向新节点
        else oldLast.next = last;
        N++;
    }
    public Item dequeue(){
        Item item = first.item;
        first = first.next;
        if(isEmpty()) last = null;//链表为空,更新last
        N--;
        return item;
    }
    @Override
    public Iterator<Item> iterator(){ return new QueueIterator(); }
    private class QueueIterator implements Iterator<Item> {
        private Node current = first;
        @Override
        public boolean hasNext(){ return current != null;}
        @Override
        public Item next(){
            Item item = current.item;
            current = current.next;
            return item;
        }
        @Override
        public void remove(){}
    }
}

要点

1. 定义内部类Node
2. Node型的实例变量first和last分别指向最早和最晚添加进的节点
3. enqueue()中,创建节点后,链表为空时,first和last同时指向新节点
4. dequeue()中,删除节点后,链表为空时,last为null

特点

1. 可以处理任何类型的数据
2. 所需空间和集合大小成正比
3. 操作所需时间和集合大小无关