1、栈的定义
凡事了解过编程的朋友，肯定都应该听说过栈这种数据结构，而且这个数据结构最有意思的一点是数据先进后出，后进先出，所以栈( stack )是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶 (top) ，另一端称为栈底 (bottom) ，不含任何数据元素的栈称为空栈。栈又称为后进先出 (Last In Filrst Out) 的线性表，简称 LlFO结构。
理解栈的定义需要注意:
首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。
它的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得栈底是固定的，最先进栈的只能在栈底。
栈的插入操作，叫作进栈，也称压栈、入栈。 类似子弹入弹夹。
栈的删除操作，叫作出栈，也有的叫作弹栈。如同弹夹中的子弹出夹。具体操作入下图所示：
同时这里要强调一个问题：最先进栈的元素，是不是就只能是最后出栈呢?
答案是不一定，要看什么情况。栈对线性表的插入和删除的位置进行了限制 ，并没有对元素进出的时间进行限制，也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就可以。
举例来说，如果我们现在是有 3 个整型数字元素 1、 2、 3 依次进栈，会有哪些出栈次序呢?
• 第一种: 1 、 2、 3 进，再 3、 2、 1 出。这是最简单的最好理解的一种，出栈次序为 321。
• 第二种: 1 进， 1 出， 2 进. 2 出， 3 进， 3 出。也就是进一个就出一个，出栈次序为 123。
• 第三种: 1 进， 2 进， 2 出， 1 出， 3 进， 3 出。出栈次序为 213。
• 第四种: 1 进， 1 出， 2 进， 3 进， 3 出， 2 出。出栈次序为 132.
• 第五种: 1 进， 2 进， 2 出， 3 进， 3 出， 1 出。 出钱次序为 231。
有没有可能是312 这样的次序出栈呢？答案是肯定不会。因为 3 先出栈，就意味着， 3 曾经进栈，既然 3 都进栈了，那也就意味着，1 和 2 已经进栈了，此时， 2 一 定是在 1 的上面，就是更接近栈顶，那么出栈只可能是 321，不然不满足123 依次进栈的要求，所以此时不会发生1 比 2 先出栈的情况。
从这个简单的例子就能看出，只是 3 个元素，就有 5 种可能的出栈次序，如果元素数量多，其实出栈的变化将会更多的。这个知识点一定要弄明白。
2、栈的顺序存储结构及实现
既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。线性表是用数组来实现的，对于栈这种只能一头插入删除的线性表来说，用数组下标为 0 的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以让它作栈底。
以下是代码实现：
public class SeqStack<T> {
private int top = -1;// 定义栈顶指针，当指针为-1表示空栈
private T[] arry;// 定义一个数组
private int arrySize;// 定义数组的大小
/**
* 定义一个线性栈的构造函数
*
* @return
*/
@SuppressWarnings("unchecked")
public SeqStack(int stackSize) {
arry = (T[]) new Object[stackSize];
}
/**
* 判定栈是否为空
*
* @return
*/
public Boolean isEmpty() {
return top == -1;
}
/**
* 获取栈顶元素
*
* @return
*/
public T getTop() {
if (isEmpty()) {
new Exception("栈元素为空");
}
return arry[top];
}
/**
* 栈新增元素
*/
public void push(T data) {
if (arry.length == arrySize) {
new Exception("栈元素已满");
}
arry[++top] = data;
arrySize++;
}
/**
* 删除元素
*
* @return
*/
public T remove() {
if (isEmpty()) {
new Exception("栈元素为空");
}
arrySize--;
return arry[top--];
}
public static void main(String arg[]) {
SeqStack<Integer> stack = new SeqStack<>(10);
for (int j = 1; j < 8; j++) {
stack.push(j);
}
int length = stack.arrySize;
System.out.println("stackSize：" + length);
for (int i = 0; i < length; i++) {
System.out.println("new stack.pop：" + stack.getTop());
stack.remove();
}
}
}
3、扩展：两栈共享空间
其实栈的顺序存储还是很方便的，因为它只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个很大的缺陷，就是必须事先确定数组存储空间大小，万一不够用了，就需要编程手段来扩展数组的容量，非常麻烦。 对于一个栈，我们也只能尽量考虑周金，设计出合适大小的数组来处理，但对于两个相同类型的栈，我们却可以做到最大限度地利用其事先开辟的存储空间来进行操作。
做法如图，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为 0 处，另一个栈为栈的末端，即下标为数组长度 n-1 处。这样，两个栈如果增加元素，就是两端点向中间延伸。
其实关键思路是：它们是在数组的两端，向中间靠拢。 top1和 top2 是栈 1 和栈 2 的栈顶指针，可以想象，只要它们俩不见面，两个栈就可以一直使用。
在真正实现的时候，不是使用两个栈，把他们再合并，而是使用一个数组，只是让top指针按照之前所讲的规则指向而已，如下图所示：
具体操作代码如下：
public class ShareStack<T> {
// 定义数组
private T[] arry;
// 定义两个栈顶指针
private int top1;
private int top2;
// 定义数组长度
private int stackSize;
/**
* 创建共享栈的构造函数
*
* @param stackSize
*/
@SuppressWarnings("unchecked")
public ShareStack(int stackSize) {
arry = (T[]) new Object[stackSize];
top1 = -1;
top2 = stackSize;
}
/**
* 入栈操作
*/
public void push(int i, T data) {
if (top1 == top2 - 1) {// 如果两个指针碰面，证明栈已经满了
new Exception("栈已满");
}
if (i == 1) {// 如果是从栈1入站，top1指针往后移动
top1++;
arry[top1] = data;
} else if (i == 2) {// 如果是从栈1入站，top2指针往前移动
top2--;
arry[top2] = data;
} else {
new Exception("入栈错误");
}
}
/**
* 判定栈是否为空
*
* @return
*/
public boolean isEmpty(int i) {
if (i == 1) {
return top1 == -1;
} else if (i == 2) {
return top2 == stackSize;
} else {
new Exception("输入错误");
}
return false;
}
/**
* 获取栈顶元素
*
* @return
*/
public T getTop(int i) {
if (i == 1) {
if (top1 == -1) {// 判定栈是否为空
new Exception("栈1为空");
} else {
return arry[top1];
}
} else if (i == 2) {
if (top2 == stackSize) {// 判定栈是否为空
new Exception("栈2为空");
} else {
return arry[top2];
}
} else {
new Exception("没有这个栈");
}
return null;
}
/**
* 删除栈顶元素
*
* @param arry
* @param top
* @return
*/
public T remove(int i) {
if (i == 1) {
if (top1 == -1) {
new Exception("栈1为空");
} else {
arry[top1] = null;// 将栈顶指针所对应的数组设置为空
return arry[top1--];// 返回删除后的栈顶指针所对应的值
}
} else if (i == 2) {
if (top2 == stackSize) {
new Exception("栈2为空");
} else {
arry[top2] = null;// 将栈顶指针所对应的数组设置为空
return arry[top2++];// 返回删除后的栈顶指针所对应的值
}
} else {
new Exception("没有这个栈");
}
return null;
}
/**
* 测试情况
*
* @param args
*/
public static void main(String[] args) {
ShareStack<Integer> stack = new ShareStack<>(10);
stack.push(1, 1);
stack.push(1, 2);
stack.push(2, 10);
stack.push(2, 9);
System.out.println("栈1栈顶元素为：" + stack.getTop(1));
System.out.println("栈2栈顶元素为：" + stack.getTop(2));
stack.remove(1);
stack.remove(2);
System.out.println("栈1栈顶元素为：" + stack.getTop(1));
System.out.println("栈2栈顶元素为：" + stack.getTop(2));
}
}