#栈和队列 --- ##栈 --- 栈只允许访问一个数据项：即最后插入的数据。溢出这个数据才能访问倒数第二个插入的数据项。它是一种"后进先出"的数据结构。 栈最基本的操作是出栈(Pop)、入栈(Push)，还有其他扩展操作，如查看栈顶元素，判断栈是否为空、是否已满，读取栈的大小等。 ``` /** * 栈是先进后出 * 只能访问栈顶的数据 * @author dream * */ /** * 基于数组来实现栈的基本操作 * 数据项入栈和出栈的时间复杂度均为O(1) * @author dream * */ public class ArrayStack { private long[] a; private int size; //栈数组的大小 private int top; //栈顶 public ArrayStack(int maxSize){ this.size = maxSize; this.a = new long[size]; this.top = -1; //表示空栈 } public void push(long value){ //入栈 if(isFull()){ System.out.println("栈已满!"); return; } a[++top] = value; } public long peek(){ //返回栈顶内容，但不删除 if(isEmpty()){ System.out.println("栈中没有数据"); return 0; } return a[top]; } public long pop(){ //弹出栈顶内容 if(isEmpty()){ System.out.println("栈中没有数据!"); return 0; } return a[top--]; } public int size(){ return top + 1; } /** * 判断是否满了 * @return */ public boolean isFull(){ return (top == size - 1); } /** * 是否为空 * @return */ public boolean isEmpty(){ return (top == -1); } public void display(){ for (int i = top; i >= 0; i--) { System.out.println(a[i] + " "); } System.out.println(""); } } ``` ##队列 --- 依然使用数组作为底层容器来实现一个队列的封装 ``` /** * 队列也可以用数组来实现，不过这里有个问题，当数组下标满了后就不能再添加了， * 但是数组前面由于已经删除队列头的数据了，导致空。所以队列我们可以用循环数组来实现， * @author dream * */ 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.println(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(isFull()){ 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.println(a[i] + " "); } System.out.println(" "); } } ``` 优先级队列中，插入操作需要O(N)的时间，而删除操作则需要O(1)的时间。