1.栈
先进后出，后进先出
栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
stack.png
package com.fantj.dataStruct.stack;
/**
* 栈
* Created by Fant.J.
* 2017/12/21 10:20
*/
public class MyStack {
//底层是一个数组
private long []arr;
private int top;
/**
* 默认构造方法
*/
public MyStack(){
arr = new long[10];
top = -1;
}
/**
* 带参数的构造方法
*/
public MyStack(int maxsize){
arr = new long[maxsize];
top = -1;
}
/**
* 添加数据
*/
public void push(int value){
arr[++top] = value;
}
/**
* 移除pop数据
*/
public long pop(){
return arr[top--]; //返回数据并递减
}
/**
* 查看数据
*/
public long peek(){
return arr[top]; //返回数据
}
/**
* 判断 是否是空
*/
public boolean isEmpty(){
return top == -1; //top为-1，就是空
}
/**
* 判断 是否满了
*/
public boolean isFull(){
return top == arr.length-1;
}
}
2.队列
先进先出
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头
queue.png
package com.fantj.dataStruct.queue;
/**
* 队列（先进先出）
* Created by Fant.J.
* 2017/12/21 10:44
*/
public class MyQueue {
//底层使用数组
private long []arr;
//有效数据的多少
private int elements;
//队头
private int front;
//队尾
private int end;
/**
* 默认构造方法
*/
public MyQueue(){
arr = new long[10];
elements = 0;
front = 0;
end = -1;
}
/**
* 带参数的构造方法，参数为数组大小
*/
public MyQueue(int maxsize){
arr = new long[maxsize];
elements = 0;
front = 0;
end = -1;
}
/**
* 添加数据，从队尾插入
*/
public void insert(long value){
arr[++end] = value;
elements++;
}
/**
* 删除数据，从队尾删除
*/
public long remove(){
elements--;
return arr[front++];
}
/**
* 查看数据，从对头查看
*/
public long peek(){
return arr[front];
}
/**
* 判断是否为空
*/
public boolean isEmpty(){
return elements == 0;
}
/**
* 判断是否满了
*/
public boolean isFull(){
return elements == arr.length;
}
}
但是普通队列有个问题，就是你在进行一轮存取数据操作后，因为end=arr.length-1;front = arr.lenth-1;所以，会报错越界异常。因此我们会在插入删除前加入判断，让这个队列循环利用。 --循环队列
2.队列pro --循环队列
为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。这种循环队列可以以单链表的方式来在实际编程应用中来实现。
修改两处：insert和remove
/**
* 添加数据，从队尾插入
*/
public void insert(long value){
if (end == arr.length-1){
end = -1; //如果到达了队列尽头，初始化end
}
arr[++end] = value;
elements++;
}
/**
* 删除数据，从队尾删除
*/
public long remove(){
long value = arr[front++];
if (front == arr.length){
front=0; //如果到达了队列尽头，初始化front
}
elements--;
return value;
}
源码地址：git地址
