作者：nnngu
GitHub：https://github.com/nnngu
博客园：http://www.cnblogs.com/nnngu
简书：https://www.jianshu.com/users/1df20d76ea5c
知乎：https://www.zhihu.com/people/nnngu/posts
这篇文章要总结的是栈，主要从以下几个方面来进行总结。
1、栈是什么
2、栈的存储结构
3、栈的常见操作及代码实现
1、栈是什么
栈是一种特殊的线性表，它限定了只能在表的一端进行插入与删除操作。因此，栈就是后进先出 Last In First Out (LIFO) 的线性表。
线性表分为顺序表和链表，所以栈分为顺序栈和链式栈，为了方便演示，下文所使用的栈都是顺序栈。
它的应用场景有很多，比如手枪弹夹里面的子弹，只能从一端塞入或者取出子弹。
2、栈的存储结构
顺序栈的代码实现：
SeqStack.java
/**
* 自己封装一个顺序栈
*/
public class SeqStack {
// 使用数组来存放元素
public Object[] data;
// 栈顶指针
public int top;
public SeqStack(int length) {
data = new Object[length];
}
}
3、栈的常见操作及代码实现
3-1、初始化
实现思路：用指定大小的 length 实例化一个 SeqStack，然后使top指针指向-1
代码：
SeqStackOperate.java
public class SeqStackOperate {
/**
* 初始化
* @param length
* @return
*/
public SeqStack init(int length) {
SeqStack seqStack = new SeqStack(length);
seqStack.top = -1;
return seqStack;
}
}
3-2、进栈
实现思路：将top指针加1，然后将新元素插入到top指针指向的位置。
代码：
SeqStackOperate.java 中添加方法
/**
* 进栈
* @param seqStack
* @param data
*/
public void push(SeqStack seqStack, Object data) {
// 检查栈是否满了
if (seqStack.top == seqStack.data.length - 1) {
return;
}
seqStack.top++;
seqStack.data[seqStack.top] = data;
}
3-3、出栈
实现思路：删除top指针指向的元素，并使top指针减1
代码：
SeqStackOperate.java 中添加方法
/**
* 出栈
* @param seqStack
* @return
*/
public Object pop(SeqStack seqStack) {
// 检查栈是否为空
if (seqStack.top == -1) {
return null;
}
Object obj = seqStack.data[seqStack.top];
seqStack.data[seqStack.top] = null;
seqStack.top--;
return obj;
}
3-4、获取栈顶元素
实现思路：与出栈相似，但是不删除栈顶元素。
代码：
SeqStackOperate.java 中添加方法
/**
* 获取栈顶元素
*
* @param seqStack
* @return
*/
public Object getTopData(SeqStack seqStack) {
// 检查栈是否为空
if (seqStack.top == -1) {
return null;
}
return seqStack.data[seqStack.top];
}
3-5、判断是否栈空
实现思路：判断top指针是否等于-1就可以
代码：
SeqStackOperate.java 中添加方法
/**
* 判断是否栈空
* @param seqStack
* @return
*/
public boolean isEmpty(SeqStack seqStack) {
return seqStack.top == -1;
}
3-6、判断是否栈满
实现思路：检查top指针的值与数组长度减1是否相等，如果相等则为栈满。
代码：
SeqStackOperate.java 中添加方法
/**
* 判断是否栈满
* @param seqStack
* @return
*/
public boolean isFull(SeqStack seqStack) {
return seqStack.top == seqStack.data.length - 1;
}
3-7、获取栈中元素个数
实现思路：top指针的值加1就是栈中的元素个数。
代码：
SeqStackOperate.java 中添加方法
/**
* 获取栈中元素个数
*
* @param seqStack
* @return
*/
public int getLength(SeqStack seqStack) {
return seqStack.top + 1;
}
4、测试
添加一个用来测试的类：StackTest.java
public class StackTest {
public static void main(String[] args) {
SeqStackOperate seqStackOperate = new SeqStackOperate();
// 初始化一个栈，最大长度为5
SeqStack seqStack = seqStackOperate.init(5);
// 看看能否放进6个元素
seqStackOperate.push(seqStack, 1);
seqStackOperate.push(seqStack, 2);
seqStackOperate.push(seqStack, 3);
seqStackOperate.push(seqStack, 4);
seqStackOperate.push(seqStack, 5);
seqStackOperate.push(seqStack, 6);
// 输出栈当前的长度
int length = seqStackOperate.getLength(seqStack);
System.out.println("栈当前的长度：" + length);
System.out.println("");
// 出栈
Object obj = seqStackOperate.pop(seqStack);
System.out.println("出栈的元素是 ---- " + obj);
System.out.println("");
// 输出栈当前的长度
length = seqStackOperate.getLength(seqStack);
System.out.println("栈当前的长度：" + length);
System.out.println("");
// 输出当前的栈顶元素
obj = seqStackOperate.getTopData(seqStack);
System.out.println("当前的栈顶元素是 ---- " + obj);
System.out.println("");
}
}
测试结果：
