栈或者队列是经典的数据结构,虽然平时都在用,但是都是别人封装好的集合,我们不用手写了,但是这些内功,作为开发人员来说是必须要掌握的。
我们知道,在数组中,若知道数据项的下标,便可立即访问该数据项,或者通过顺序搜索数据项,访问到数组中的各个数据项。但是栈和队列不同,它们的访问是受限制的,即在特定时刻只有一个数据项可以被读取或者被删除。众所周知,栈是先进后出,只能访问栈顶的数据,队列是先进先出,只能访问头部数据。这里不再赘述。
栈的主要机制可以用数组来实现,也可以用链表来实现,下面用数组来实现栈的基本操作:
public class ArrayStack {
private long[] a;
//栈数组大小
private int size;
//栈顶
private int top;
//初始化栈
public ArrayStack(int maxSize) {
this.size = maxSize;
a = new long[size];
//表示空栈
top = -1;
}
//入栈
public void push(int value) {
if (isFull()) {
System.out.println("Stack is Full!");
return;
}
a[++top] = value;
}
//出栈,返回栈顶元素并删除
public long pop() {
if (isEmpty()) {
System.out.println("Stack is Empty!");
return 0;
}
return a[top--];
}
//获取并返回栈顶元素
public long peak() {
if (isEmpty()) {
System.out.println("Stack is Empty!");
return 0;
}
return a[top];
}
public boolean isFull() {
return top == size - 1;
}
public boolean isEmpty() {
return top == -1;
}
//遍历栈元素
public void display() {
if (isEmpty()) {
System.out.println("Stack is Empty!");
return;
}
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 front;
//队尾
private int rear;
//实际存储元素个数
private int nItems;
//初始化队列
public RoundQueue(int maxSize) {
this.size = maxSize;
a = new long[size];
front = 0;
rear = -1;
nItems = 0;
}
//插入数据
public void insert(int value) {
if (isFull()) {
System.out.println("Queue is Full!");
return;
}
//尾指针满了就循环到0处
rear = ++rear % size;
a[rear] = value;
nItems++;
/*if (rear == size - 1) {
rear = -1;
}
a[++rear] = value;*/
}
//删除数据
public long remove() {
if (isEmpty()) {
System.out.println("Queue is Empty!");
return 0;
}
nItems--;
front = front % size;
return a[front++];
}
//返回队头数据
public long peak() {
if (isEmpty()) {
System.out.println("Queue is Empty!");
return 0;
}
return a[front];
}
public boolean isFull() {
return nItems == size;
}
public boolean isEmpty() {
return nItems == 0;
}
public void display() {
if (isEmpty()) {
System.out.println("Queue is Empty!");
return;
}
int item = front;
for (int i = 0; i < nItems; i++) {
System.out.print(a[item++ % size] + " ");
}
System.out.println();
}
}
和栈一样,队列中插入数据项和删除数据项的时间复杂度均为O(1)。
还有个优先级队列,优先级队列是比栈和队列更专用的数据结构。优先级队列与上面普通的队列相比,主要区别在于队列中的元素是有序的,关键字最小(或者最大)的数据项总在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。优先级队列的内部实现可以用数组或者一种特别的树——堆来实现。
public class PriorityQueue {
private long[] a;
//数组大小
private int size;
//实际存储元素个数
private int nItems;
public PriorityQueue(int maxSize) {
this.size = maxSize;
a = new long[size];
nItems = 0;
}
public void insert(int value) {
if (isFull()) {
System.out.println("Queue is Full!");
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("Queue is Empty!");
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) 的时间。
原文参考【Java知音网】