注意：这里是JAVA自学与了解的同步笔记与记录，如有问题欢迎指正说明
日撸 Java 三百行（14天：你好，栈）一、关于栈二、顺序表实现栈
1.基本属性与方法2.入栈操作3.出栈操作 三、代码模拟总结
一、关于栈
介绍完线性表的基本存储结构（包括顺序表与链表）后，我们今天用顺序表来模拟一下栈的操作。
栈这种说法对于初学计算机的人来说是很陌生，但是其本质却非常简单易懂。
简单来说，就像装水的杯子，装乒乓球的球筒那样，一种单口进入单口出的一种容器，而且往往只是用于中转，暂时性的，辅助性的操作的数据结构。就像“ 栈 ”这个名称本身的中文含义那样：
“ 栈 ”是一个用于存储货物的房间，就像我们古代用于旅人驻脚歇店的客栈，人们不会在这久居，不过是中转站罢了。
这个翻译可谓很灵性了，计算机中的“ 栈 ”(Stack)也确实也可以理解为暂时存储的容器。比如在函数调用时，底层编译器会把我们当前的数据放于这个临时的容器中存储，避免在进入函数后当前上下文环境的信息丢失，之后，待到函数返回后再从Stack中取出。
当然，这种数据中转存储的数据类型我们不是说都称之为栈，还包括有有队列性质的高速缓存与各种正常的顺序存储的文件系统等，只是说栈有些独有方面的特例：
首先，我们要求栈具有如同线性表那样的数据存放特性。
其次，我们要求栈必须是一种运算受限的线性表: 按照后进先出(Last In First Out，简称LIFO)或先进后出(First In Last Out，简称FILO)的原则进行的线性表，因此，栈又称为LIFO表或FILO表。
（图片来源：https://www.cnblogs.com/misterge/p/3427587.html）
在这样的原则下，我们限定只能在一端进行插入和删除操作，并且将允许操作的一端称为栈顶(Top)，不允许操作的称为栈底(Bottom)，当栈中没有数据元素时叫空栈(Empty Stack)。
二、顺序表实现栈只要扭住“ 运算受限的线性表 ”这个关键词，那么实现栈就非常简单。我们只要按照一般的顺序的创建那样创建这个数据结构即可。
1.基本属性与方法· 代码如下：
public static final int MAX_DEPTH = 10;
int depth;
char[] data;
public CharStack() {
depth = 0;
data = new char[MAX_DEPTH];
}// Of the first constructor
public String toString() {
String resultString = "";
for (int i = 0; i < depth; i++) {
resultString += data[i];
} // Of for i
return resultString;
}// Of toString
有了前几天关于顺序表的建立的操作细节，今天很多内容都可以简单完成。
这里的属性与静态顺序表中的内容无差，构造函数完成栈深度（长度）初始化，空间开辟遵循静态链表开辟的方法——使用new开辟固定“MAX_DEPTH”大小的空间。
但注意，栈是于栈顶一端进行删除与插入的结构，而为了顺序表的实现方便，我们往往在下标较大处插入，因此我们定义栈顶在数组的最右侧。
所以，按照从左向右打印的习惯，toString()函数完成的就是栈底向栈顶的打印过程。
2.入栈操作入栈是栈的专有名词，从栈的角度来看，其意义就是向栈内添加一个元素罢了。
从顺序表的角度来看，其意义就是在顺序表的最后一个元素后面再插入一个元素。
顺序表的插入按照我们之前的经验，这是个涉及“ 一段元素 ”同时向后移动覆盖的过程，听着很麻烦？但其实还好，末尾似乎没有什么元素可以移动的，而且静态顺序表的空间都是开辟好的，我们只需要给末尾元素之后的空位赋值并且让栈深度+1即可（对于从0开始记录的任何表，表长都默认值最后一个元素的下一个位置）
· 代码来咯
public boolean push(char paraChar) {
if (depth == MAX_DEPTH) {
System.out.println("Stack full.");
return false;
} // Of if
data[depth] = paraChar;
depth++;
return true;
}// Of push
对于任何顺序表的插入都不要忘记判断表满的情况，因此，这里先进行一次判满的判断，这是栈的基本健壮性保证。
之后的入栈操作怎么写，要根据你的栈顶指针的默认指向来确定。
这里我们用depth来表示栈深度，同时，自然也用于表示栈顶指针。这种情况的话，depth默认指向的位置刚好就是尾元素后面的空位，刚好可以直接插入，于是可以使用：
data[depth] = paraChar; depth++;
或data[depth++] = paraChar;来完成插入。
当然，若栈顶指针假设指向末尾元素本身的话，这里我们假设这个变量为top。在插入元素时需要保证栈顶指针要先移动到末尾元素后面的空位才能进行插入，于是就要使用：
top++; data[top] = paraChar;
或data[++top] = paraChar;来完成插入。
入栈操作是一个非常单纯的输入型函数，理论上是不会有返回值的。但是不同的语言的库可能会有不同的策略来对待，总之，我们在代码设置上，在函数返回后给用户提供了栈是否满的布尔信息，以方便用户对函数的处理。
3.出栈操作出栈操作可以看做入栈的逆过程。
· 代码来咯
public char pop() {
if (depth == 0) {
System.out.println("Nothing to pop.");
return ' ';
} // Of if
char resultChar = data[depth - 1];
depth--;
return resultChar;
}// Of pop
首先作为一个顺序表，元素删除肯定是要进行表空判断实现基本的健壮性操作。
出栈时，使用resultChar先接收栈顶数据，之后再进行栈指针的下移操作，实现逻辑上元素减少（但是实际上这个值还是存放在原指针所指的位置的），因为我们确定栈元素的多少仅依靠栈顶指针的具体值而定。
这个操作与入栈的操作是完全相逆的，而且也会因为栈顶指针的含义不同而变化，即：
栈顶指针是指向栈顶有效元素本身？
还是
栈顶指针指向栈顶有效元素的上方的一个无数据位？
我们的显然是后者。
具体各种不同指向的代码差异我就不像入栈那样赘述了。
三、代码模拟· 代码来咯
public static void main(String args[]) {
CharStack tempStack = new CharStack();
for (char ch = 'a'; ch < 'm'; ch++) {
tempStack.push(ch);
System.out.println("The current stack is: " + tempStack);
} // Of for ch
char tempChar;
for (int i = 0; i < 12; i++) {
tempChar = tempStack.pop();
System.out.println("Poped: " + tempChar);
System.out.println("The current stack is: " + tempStack);
} // Of for i
}// Of main
今天的代码模拟中，试着按需入栈’a’~'m’的全部字符。但因为栈的容量只有10，因此此操作后续肯定会因为栈满而无法成功。
后续进行了12出栈操作，还是因为大于容量限制，后续出栈操作肯定会因为栈空而无法进行。
· 运行结果
总结
栈的操作并不算复杂，但是栈确实计算机中格外重要的一个数据结构。
栈贯穿了计算机的各个邻域，栈的概念在硬件中就早有使用，因为栈的实现，促成了操作系统的中断特性的实现，而中断的特性又促成后来批处理操作系统的诞生，是当代计算机的奠基石。也许毫不夸张说，没有栈，就没有我们如今的计算机的基础。
逻辑层面，其栈简单易用且巧妙的特征还被很多算法所喜爱，例如符号匹配，字符串的算符运算，单调栈，波兰表达式的实现，树的非递归调用…
同时，栈也实现了“ 调用 ”思想的核心。栈的临时存储与栈出数据总是最近一次栈入的数据的特性非常符合嵌套调用与返回的特性。所以如今我们使用的各种函数都用到了栈的思想，任何使用函数完成的算法体系都可以使用栈完成模拟。
栈虽然简单，但是学会灵活利用栈去解决各种实际的算法问题并不是一件说说很轻松的事情，因此关于栈的学习应永远伴随于计算机的研究生涯，没有尽头。
