(1)数组的简单栈实现
public class MyStack {
private int maxSize;
private long[] arr;
private int top;
// 构造方法
public MyStack(int size) {
maxSize = size;
arr = new long[maxSize];
top = -1;
}
// 压入数据
public void push(long value){
arr[++top]=value;
}
// 弹出数据
public long pop() {
return arr[top--];
}
// 访问栈顶元素
public long peek() {
return arr[top];
}
// 栈是否为空
public boolean isEmpty() {
return (top == -1);
}
// 栈是否满了
public boolean isFull() {
return (top == maxSize - 1);
}
}
(2)java简单的队列实现
public class Queue {
// 数组
private long[] arr;
// 最大空间
private int maxSize;
// 有效元素大小
private int elems;
// 队头
private int font;
// 队尾
private int end;
public Queue(int maxSize) {
this.maxSize = maxSize;
arr = new long[maxSize];
elems = 0;
font = 0;
end = -1;
}
// 插入数据
public void insert(long value) {
arr[++end] = value;
elems++;
}
// 移除数据
public long remove() {
elems--;
return arr[font++];
}
// 是否为空
public boolean isEmpty() {
return (elems == 0);
}
// 是否满了
public boolean isFull() {
return (end == maxSize - 1);
}
// 返回有效元素大小
public int size() {
return elems;
}
}
以上的队列实现了先进先出的原则，但如果超过了栈的预设值，就会发生数组越界异常，所以接下来我们实现下循环队列
(3)Java简单的循环队列实现
public class MyQueue {
// 数组
private long[] arr;
// 最大空间
private int maxSize;
// 有效元素大小
private int elems;
// 队头
private int font;
// 队尾
private int end;
public MyQueue(int maxSize) {
this.maxSize = maxSize;
arr = new long[maxSize];
elems = 0;
font = 0;
end = -1;
}
// 插入数据
public void insert(long value) {
if(end == maxSize - 1) {
end = -1;
}
arr[++end] = value;
elems++;
}
// 移除数据
public long remove() {
long tmp = arr[font++];
if(font == maxSize) {
font = 0;
}
elems--;
return tmp;
}
// 是否为空
public boolean isEmpty() {
return (elems == 0);
}
// 是否满了
public boolean isFull() {
return (elems == maxSize);
}
// 返回有效元素大小
public int size() {
return elems;
}
}
(4)优先级队列 (会将元素在数组中排序插入，实现队列的有序)
public class PriorityQueue {
// 数组
private long[] arr;
// 最大空间
private int maxSize;
// 有效元素大小
private int elems;
public PriorityQueue(int maxSize) {
this.maxSize = maxSize;
arr = new long[maxSize];
elems = 0;
}
// 插入数据
public void insert(long value) {
int i;
for (i = 0; i < elems; i++) {
if(value < arr[i]) {
break;
}
}
for(int j = elems; j > i;j--){
arr[j] = arr[j - 1];
}
arr[i] = value;
elems++;
}
// 移除数据
public long remove() {
long value = arr[elems - 1];
elems--;
return value;
}
// 是否为空
public boolean isEmpty() {
return (elems == 0);
}
// 是否满了
public boolean isFull() {
return (elems == maxSize);
}
// 返回有效元素大小
public int size() {
return elems;
}
}
(5)连接点的实现（由数据和引用构成的node连接而成）
public class Link {
private long data;
private Link next;
public Link(long data) {
this.data = data;
}
public long getData() {
return data;
}
public void setData(long data) {
this.data = data;
}
public Link getNext() {
return next;
}
public void setNext(Link next) {
this.next = next;
}
}
(6)链表的实现比上述连接点的实现更灵活
public class LinkList {
private Link first;
public void insert(long value) {
Link lnk = new Link(value);
if (first == null) {
first = lnk;
} else {
lnk.setNext(first);
first = lnk;
}
}
public void displayAll() {
Link current = first;
while (current != null) {
System.out.print(current.getData() + " ");
current = current.getNext();
}
}
// 查找结点
public Link find(long key) {
Link current = first;
while (current.getData() != key) {
if (current.getNext() == null) {
return null;
}
current = current.getNext();
}
return current;
}
// 插入结点到指定位置
public void insert(long value, int pos) {
if (pos == 0) {
insert(value);
} else {
Link current = first;
for (int i = 0; i < pos - 1; i++) {
current = current.getNext();
}
Link lnk = new Link(value);
lnk.setNext(current.getNext());
current.setNext(lnk);
}
}
// 删除指定结点
public void delete(long key) {
Link current = first;
Link ago = first;
while(current.getData() != key) {
if(current.getNext() == null) {
return;
} else {
ago = current;
current = current.getNext();
}
}
if(current == first) {
first = first.getNext();
} else {
ago.setNext(current.getNext());
}
}
}
上述两个实现指向的方式不一样