java算法：FIFO队列

java算法：FIFO队列

FIFO队列是一个ADT，由两个基本操作构成：插入（放入）一个新项，删除（得到）最早插入的项。

例1：FIFO队列ADT接口

Java代码

interfaceintQueue{ intQueue(intq); intempty(); voidput(intq); intget(); }

interface intQueue{intQueue(int q);int empty();void put(int q);int get();}

使用数组或链表，在常数时间内实现FIFO队列ADT的get和put操作。

例2：FIFO队列的链表实现

Java代码

publicclassintQueue{ privateclassNode{ intitem; Nodenext; Node(intitem){ this.item=item; next=null; } } privateNodehead,tail; intQueue(intmax){ head=null; tail=null; } booleanempty(){ return(head==null); } voidput(intitem){ Nodet=tail; tail=newNode(item); if(empty()){ head=tail; }else{ t.next=tail; } } intget(){ intv=head.item; Nodet=head.next; head=t; returnv; } }

public class intQueue{private class Node{int item;Node next;Node(int item){this.item = item; next = null;}}private Node head, tail;intQueue(int max){head = null;tail = null;}boolean empty(){return (head == null);}void put(int item){Node t = tail;tail = new Node(item);if(empty()){head = tail;}else{t.next = tail;}}int get(){int v = head.item;Node t = head.next;head = t;return v;}}

数组要求自始自终都要为预计的最大的项数保留足够的空间，而链表表示使用的空间与数据结构中的元素个数成比例，但要为指针分配额外的空间，并且每个操作都要花分配和释放内存的额外时间。

例3：FIFO队列的数组实现

Java代码

publicclassintQueue{ privateint[]q; privateintN,head,tail; intQueue(intmax){ q=newint[maxN+1]; head=N; tail=0; } booleanempty(){ return(head%N==tail); } voidput(intitem){ q[tail++]=item; tail=tail%N; } intget(){ head=head%N; returnq[head++]; } }

public class intQueue{private int[] q;private int N, head, tail;intQueue(int max){q = new int[maxN + 1];head = N;tail = 0;}boolean empty(){return (head%N == tail);}void put(int item){q[tail++] = item;tail = tail%N;}int get(){head = head%N;return q[head++];}}

拓展：双端队列，删除随机项队列（如果第一项则是FIFO队列，如果最后一项则是栈），或者删除关键字项，自定义项等。

看不见我将要去的地方，记不得我已经去过的地方。