一 前言
本篇使用数组的方式实现栈，当然重点不在使用了什么样的数据结构去实现另一种数据结构，也可以使用动态数组，链表来实现栈；知识追寻者觉得比较重要的是实现一种数据结构的思路；比如栈，只要知道了如何去实现栈的思路，后面不就是敲敲几行代码的事情么，反之三思后行古人早就教给我们了；当然本文只提供一种简单的实现方式，肯定有许多不足之处；
二 栈的实现
2.1栈的含义
- 栈是一种有序的线性表，只能在一端插入数据和删除数据，最后插入的数据也就是最先被删除的数据；通常栈也被称为先进后出或者后进先出的线性表结构；
- 栈的定义看起来对初学者可能有点模糊，读者可以想象一下工厂里面的玻璃，一块一块玻璃从地面开始叠的高高的，取得时候是从最高层得一块玻璃往下取；
- 看下面一张经典得栈结构图，中间是原本得栈大小为3，栈顶的数值为3；如果往栈顶加入一个数值4，就会变为左边的图，此时栈顶为4，栈大小为4；如果中间栈的删除一个元素，就会变为右边的图，此时栈顶值为2，栈大小为2；
2.2 栈的重要数据类型
通过前面说明介绍可以详细的认识到使用栈避不开，栈的栈顶值(top)，栈的添加操作(push)，栈的删除操作(pop)，栈的当前大小(size)；通常每种数据结构都有一个初始容量值(capacity)，当栈的当前大小超出容量值，也就是溢栈，也就是很多文章里面很多提到的 stack overflow；
2.3 数组实现方式
- 入栈push实现思路; 栈顶索引 + 1；
- 出栈pop实现思路；栈顶索引-1；
- 栈顶值peek就是栈顶索引；
/**
* @Author lsc
* <p>数组栈实现 </p>
*/
public class ArrayStack {
// 容量
private int capacity;
// 数组栈
private long[] stackArray;
// 栈顶
private int top;
// 构造
public ArrayStack(int size) {
// 设置容量大小
capacity = size;
// 创建数组
stackArray = new long[capacity];
// 栈顶初始值为 -1 表示空栈
top = -1;
}
// 入栈
public void push(long data) {
// 索引加1
stackArray[++top] = data;
}
// 出栈
public long pop() {
// 索引减1
return stackArray[top--];
}
// 栈顶值
public long peek() {
return stackArray[top];
}
// 判定是否是空栈
public boolean isEmpty() {
return (top == -1);
}
// 判定栈是否已满
public boolean isFull() {
return (top == capacity - 1);
}
}
测试
public static void main(String[] args) {
ArrayStack arrayStack = new ArrayStack(6);
arrayStack.push(1);
arrayStack.push(2);
System.out.println(arrayStack.pop());
System.out.println(arrayStack.peek());
System.out.println(arrayStack.isEmpty());
System.out.println(arrayStack.isFull());
}
输出
2
1
false
false