如果让你手写个栈和队列，你还会写吗？
来源：程序员私房菜（ID：eson_15）
昨天跟一个CSDN上的朋友聊天，他说现在如果让他自己手写一个栈或者队列，估计都要写蛮久的，平时虽然都在用，但是都是别人封装好的集合。
确实，经典的数据结构，包括排序算法，虽然我们平时不用手写了，但是这些内功，作为开发人员来说是必须要掌握的。受此启发，我打算更一下经典数据结构和算法的系列文章。今天先从栈和队列说起。
这些东西，挤地铁时，吃饭排队时，等公交时，可以拿来看看，或者，就把它当作个下午茶吧~
我们知道，在数组中，若知道数据项的下标，便可立即访问该数据项，或者通过顺序搜索数据项，访问到数组中的各个数据项。但是栈和队列不同，它们的访问是受限制的，即在特定时刻只有一个数据项可以被读取或者被删除。众所周知，栈是先进后出，只能访问栈顶的数据，队列是先进先出，只能访问头部数据。这里不再赘述。
栈的主要机制可以用数组来实现，也可以用链表来实现，下面用数组来实现栈的基本操作：
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;
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == size -1);
}
public void display() {
for(int i = top; i >= 0; i--) {
System.out.print(a[i] + " ");
}
System.out.println("");
}
}数据项入栈和出栈的时间复杂度均为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++;
/* if(rear == size-1){
rear = -1;
}
a[++rear] = value;
*/
}
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) 的时间。
（完）
腾讯云开发者
