栈存储结构
栈的定义
栈定义
弹夹式手枪在给弹夹塞子弹的时候，先放进去的在弹夹最底下最后放进去的在弹夹最上面。而当打枪的时候也是最后塞的子弹先打出，第一次塞的子弹最后打出。这就是栈的特性:
栈是仅限定在表尾的一端删除和插入操作的特殊线性表，插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，没有任何数据就是空栈。栈又称为先进后出(Last In First Out)的线性表即LIFO结构。
既然栈属于线性表的一种数据结构，那么线性表的特性它都符合。即可分出以下两个栈结构:
栈的顺序存储结构
我们以数组实现一个栈，那么栈底和栈顶的位置如何确认呢？
很对！我们可以将下标0的数组首元素的位置作为栈底。为什么呢有以下几点考虑:
1. 首元素的位置固定
2. 栈顶是动态变化的，以下标0作为栈底。栈顶的变化就是向数组高索引方向移动。
3. 更直观和一致性
那么空栈的时候栈顶(top)等于-1，那么栈满的时候栈顶(top)等于array.length-1
栈的简单实现
- 必要方法及初始化
初始化栈
static Integer [] stack =new Integer[5];
// 栈顶top
static int top = -1;
// 栈底bottom
static int bottom = 0;
static {
stack[0]=1;
stack[1]=2;
stack[2]=3;
stack[3]=4;
stack[4]=5;
// 栈底栈顶赋值，这个值在这写死了 其实需要根据数组长度变
top = stack.length-1;
bottom = 0;
}
/**
* 判断栈是否为空
* 是否为空即判断top==-1即可
*/
public static boolean stackEmpty() {
if(StackSort.top == -1){
return false;
}
return true;
}
/**
* 判断栈是否已满
* 栈满的时候就是栈顶等于数组长度减1
*/
public boolean stackFull() {
if(StackSort.top == StackSort.stack.length-1){
return true;
}
return false;
}
- pop出栈
POP
/**
* 出栈
*/
public static Integer pop() throws Exception {
if(!stackEmpty()){
throw new Exception("栈为空~~~");
}
Integer[] stackNum = StackSort.stack;
Integer result = stackNum[StackSort.top];
top--;
return result;
}
- push进栈
push
/**
* 进栈
*/
public static void push(int num) throws Exception {
if(stackFull()){
throw new Exception("栈满了~~~");
}
top++;
stack[top] = num;
}
warning
以上操作可以看到没有涉及到循环，时间复杂度可到O(1)。
在java中java.util包下提供了实现栈的类Stack，它继承了Vector类所以线程上是安全的。 其中Stack类中提供了以下方法:
- public E push(E item) 压栈
- public synchronized E pop() 出栈
- public boolean empty() 是否空栈
- public synchronized E peek() 返回栈顶元素
redis中栈的展现
在redis中有一个数据结构可以实现栈（先进后出），那就是Redis的List数据结构
通过以下命令实现:
# 添加key为stack，value为 v1 v2 v3
LPUSH stack v1 v2 v3
# 查询key为stack数据: 最后展示为 v3 v2 v1的顺序
LRANGE stack 0 -1
栈的链式存储结构
链栈
上述说过既然栈属于线性表，那么就存在栈的链式存储结构简称为链栈
我们以头结点（第一个结点）为栈顶，尾结点为栈底！第一个结点为栈顶，对于push，pop操作的时间复杂度都是O(1)。
那么空栈的时候栈顶(top)等于-1，那么栈满的时候栈顶(top)等于array.length-1
链栈的简单实现
那么空栈的时候栈顶(top)等于null，对于链栈的长度也没有过多限制（可以说无限长，当然要看内存的）
- 必要方法及初始化
初始化栈
// 栈顶指针
static Node head = new Node(null,null);
// 栈顶top
static Node top;
static {
Node node0 = new Node("node0", "java");
Node node1 = new Node("node1", "go");
Node node2 = new Node("node2", "python");
Node node3 = new Node("node3", "vue");
Node node4 = new Node("node4", "php");
if (head.getNext() == null) {
head.setNext(node0);
}
node0.setNext(node1);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
node4.setNext(null);
// 第一个结点为栈顶
top = head.getNext();
}
/**
* 判断栈是否为空
* 是否为空即判断top==null即可
*/
public static boolean stackEmpty() {
if(StackSort.top == null){
return false;
}
return true;
}
- pop出栈
POP
/**
* 出栈
*/
public static Node pop() throws Exception {
if(!stackEmpty()){
throw new Exception("栈为空~~~");
}
// 通过栈顶指针获取第一个结点
Node top = StackSort.head.getNext();
// 将栈顶指针指向下一个结点
StackSort.top = top.getNext();
// 将栈顶指针重新指向新的结点
StackSort.head.setNext(top.getNext());
System.out.println("新栈顶: "+ StackSort.top);
return top;
}
- push进栈
push
/**
* 进栈
*/
public static void push(Node node) throws Exception {
Node next = StackSort.head.getNext();
node.setNext(next);
StackSort.head.setNext(node);
StackSort.top = node;
}
warning
当元素时长变化一会小一会大，那就选择链栈来实现，当元素变化在可控范围内，当然选择顺序栈会更好一点