如何写Java栈和队列

我们知道，在数组中，若知道数据项的下标，便可立即访问该数据项，或者通过顺序搜索数据项，访问到数组中的各个数据项。但是栈和队列不同，它们的访问是受限制的，即在特定时刻只有一个数据项可以被读取或者被删除。众所周知，栈是先进后出，只能访问栈顶的数据，队列是先进先出，只能访问头部数据。这里不再赘述。

栈的主要机制可以用数组来实现，也可以用链表来实现，下面用数组来实现栈的基本操作：

数据项入栈和出栈的时间复杂度均为O(1)。这也就是说，栈操作所消耗的时间不依赖于栈中数据项的个数，因此操作时间很短。栈不需要比较和移动操作。

队列也可以用数组来实现，不过这里有个问题，当数组下标满了后就不能再添加了，但是数组前面由于已经删除队列头的数据了，导致空。所以队列我们可以用循环数组来实现，见下面的代码：

public class RoundQueue {    private long[] a;    private int size;   //数组大小    private int nItems; //实际存储数量    private int front;  //头    private int rear;   //尾    public RoundQueue(int maxSize) {        this.size = maxSize;        a = new long[size];        front = 0;        rear = -1;        nItems = 0;    }    public void insert(long value) {        if(isFull()){            System.out.println("队列已满");            return;        }        rear = ++rear % size;        a[rear] = value; //尾指针满了就循环到0处,这句相当于下面注释内容              nItems++;    }    public long remove() {        if(isEmpty()) {            System.out.println("队列为空！");            return 0;        }        nItems--;        front = front % size;        return a[front++];    }    public void display() {        if(isEmpty()) {            System.out.println("队列为空！");            return;        }        int item = front;        for(int i = 0; i < nItems; i++) {            System.out.print(a[item++ % size] + " ");        }        System.out.println("");    }    public long peek() {        if(isEmpty()) {            System.out.println("队列为空！");            return 0;        }        return a[front];    }    public boolean isFull() {        return (nItems == size);    }    public boolean isEmpty() {        return (nItems == 0);    }    public int size() {        return nItems;    }}

和栈一样，队列中插入数据项和删除数据项的时间复杂度均为O(1)。

还有个优先级队列，优先级队列是比栈和队列更专用的数据结构。优先级队列与上面普通的队列相比，主要区别在于队列中的元素是有序的，关键字最小（或者最大）的数据项总在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。优先级队列的内部实现可以用数组或者一种特别的树——堆来实现。

public class PriorityQueue {    private long[] a;    private int size;    private int nItems;//元素个数    public PriorityQueue(int maxSize) {        size = maxSize;        nItems = 0;        a = new long[size];    }    public void insert(long value) {        if(isFull()){            System.out.println("队列已满！");            return;        }        int j;        if(nItems == 0) { //空队列直接添加            a[nItems++] = value;        }        else{//将数组中的数字依照下标按照从大到小排列            for(j = nItems-1; j >= 0; j--) {                if(value > a[j]){                    a[j+1] = a[j];                }                else {                    break;                }            }            a[j+1] = value;            nItems++;        }    }    public long remove() {        if(isEmpty()){            System.out.println("队列为空！");            return 0;        }        return a[--nItems];    }    public long peekMin() {        return a[nItems-1];    }    public boolean isFull() {        return (nItems == size);    }    public boolean isEmpty() {        return (nItems == 0);    }    public int size() {        return nItems;    }    public void display() {        for(int i = nItems-1; i >= 0; i--) {            System.out.print(a[i] + " ");        }        System.out.println(" ");    }}

这里实现的优先级队列中，插入操作需要 O(N) 的时间，而删除操作则需要 O(1) 的时间。