栈
参考：
https://www.cnblogs.com/ysocean/p/7911910.html
Java数据结构和算法第二版【第四章栈和队列 97】
栈的基本概念
栈（stack）又称为堆栈或堆叠，栈作为一个数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）
栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。
由于堆叠数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。栈也称为后进先出表。
这里以羽毛球筒为例，羽毛球筒就是一个栈，刚开始羽毛球筒是空的，也就是空栈，然后我们一个一个放入羽毛球，也就是一个一个push进栈，当我们需要使用羽毛球的时候，从筒里面拿，也就是pop出栈，但是第一个拿到的羽毛球是我们最后放进去的。
Java模型简单的顺序栈实现
public class MyStack {
private int[] array;
private int top;
private int maxSize;
public MyStack(int size){
maxSize=size;
array=new int[size];
//空栈
top=-1;
}
//压入数据
public void push(int value){
if(top<maxSize-1){
array[++top]=value;
}
}
//弹出栈顶数据
public int pop(){
return array[top--];
}
//访问栈顶数据
public int peek(){
return array[top];
}
//判断栈是否为空
public boolean isEmpty(){
return (top==-1);
}
//判断栈是否满了
public boolean isFull(){
return (top==maxSize-1);
}
public static void main(String[] args) {
MyStack stack=new MyStack(3);
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.peek());
while(!stack.isEmpty()){
System.out.println(stack.pop());
}
}
}
这个栈是用数组实现的，内部定义了一个数组，一个表示最大容量的值以及一个指向栈顶元素的top变量。构造方法根据参数规定的容量创建一个新栈，push()方法是向栈中压入元素，指向栈顶的变量top加一，使它指向原顶端数据项上面的一个位置，并在这个位置上存储一个数据。pop()方法返回top变量指向的元素，然后将top变量减一，便移除了数据项。要知道 top 变量指向的始终是栈顶的元素。
产生的问题：
①、上面栈的实现初始化容量之后，后面是不能进行扩容的（虽然栈不是用来存储大量数据的），如果说后期数据量超过初始容量之后怎么办？（自动扩容）
②、我们是用数组实现栈，在定义数组类型的时候，也就规定了存储在栈中的数据类型，那么同一个栈能不能存储不同类型的数据呢？（声明为Object）
③、栈需要初始化容量，而且数组实现的栈元素都是连续存储的，那么能不能不初始化容量呢？（改为由链表实现）
增强功能版栈
public class ArrayStack {
//存储元素的数组,声明为Object类型能存储任意类型的数据
private Object[] elementData;
//指向栈顶的指针
private int top;
//栈的总容量
private int size;
//默认构造一个容量为10的栈
public ArrayStack(){
this.elementData = new Object[10];
this.top = -1;
this.size = 10;
}
public ArrayStack(int initialCapacity){
if(initialCapacity < 0){
throw new IllegalArgumentException("栈初始容量不能小于0: "+initialCapacity);
}
this.elementData = new Object[initialCapacity];
this.top = -1;
this.size = initialCapacity;
}
//压入元素
public Object push(Object item){
//是否需要扩容
isGrow(top+1);
elementData[++top] = item;
return item;
}
//弹出栈顶元素
public Object pop(){
Object obj = peek();
remove(top);
return obj;
}
//获取栈顶元素
public Object peek(){
if(top == -1){
throw new EmptyStackException();
}
return elementData[top];
}
//判断栈是否为空
public boolean isEmpty(){
return (top == -1);
}
//删除栈顶元素
public void remove(int top){
//栈顶元素置为null
elementData[top] = null;
this.top--;
}
/**
* 是否需要扩容，如果需要，则扩大一倍并返回true，不需要则返回false
* @param minCapacity
* @return
*/
public boolean isGrow(int minCapacity){
int oldCapacity = size;
//如果当前元素压入栈之后总容量大于前面定义的容量，则需要扩容
if(minCapacity >= oldCapacity){
//定义扩大之后栈的总容量
int newCapacity = 0;
//栈容量扩大两倍(左移一位)看是否超过int类型所表示的最大范围
if((oldCapacity<<1) - Integer.MAX_VALUE >0){
newCapacity = Integer.MAX_VALUE;
}else{
newCapacity = (oldCapacity<<1);//左移一位，相当于*2
}
this.size = newCapacity;
elementData = Arrays.copyOf(elementData, size);
return true;
}else{
return false;
}
}
public static void main(String[] args) {
ArrayStack stack = new ArrayStack(3);
stack.push(1);
//System.out.println(stack.peek());
stack.push(2);
stack.push(3);
stack.push("abc");
System.out.println(stack.peek());
stack.pop();
stack.pop();
stack.pop();
System.out.println(stack.peek());
}
}
栈实例1：单词逆序
【书103页】
public class StackX {
private int maxSize;
private char[] stackArray;
private int top;
public StackX(int max){
maxSize=max;
stackArray=new char[max];
top=-1;
}
public void push(char cha){
stackArray[++top]=cha;
}
public char pop(){
return stackArray[top--];
}
public char peek(){
return stackArray[top];
}
public boolean isEmpty(){
return (top==-1);
}
}
public class Reverser {
private String input;
private String output;
public Reverser(String in){
input=in;
}
public String doRev(){
int stackSize=input.length();
StackX theStack=new StackX(stackSize);
for(int i=0;i<input.length();i++){
char ch=input.charAt(i);
theStack.push(ch);
}
output="";
while(!theStack.isEmpty()){
char ch=theStack.pop();
output=output+ch;
}
return output;
}
}
public class ReverseApp {
public static void main(String[] args) throws IOException {
String input,output;
while(true){
System.out.print("Enter a string:");
System.out.flush();
input=getString();
//read a string from kbd
if(input.equals("")){
break;
}
Reverser theReverser=new Reverser(input);
output=theReverser.doRev();
System.out.println("Reversed: "+output);
}
}
private static String getString() throws IOException {
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
String s=br.readLine();
return s;
}
}
建立Reverse类来处理输入字符串的逆序工作。该类的关键组成部分是doRev()方法，该方法利用栈实现逆置操作。在doRev()中创建了一个栈，它根据输入字符串的长度确定栈的大小。
main()方法中由一个字符串，创建Reverser对象，字符串作为一个参数传给构造方法，接着调用这个对象的doRev()方法，并显示返回值，这个返回值是逆序的字符串。
栈实例2：分隔符匹配
栈通常用于解析某种类型的文本串。通常，文本串是用计算机语言写的代码行，而解析它们的程序就是编译器。
举例来说，分隔符包括大括号‘{’和‘}’,中括号‘[’和‘]’和小括号’(‘和‘)’。每个左分割符需要和右分隔符匹配；这就是说，每个‘{’后面要有’}’匹配，依次类推。同时，在字符串中后出现的左分隔符应该比早出现的左分隔符先完成匹配。
栈中的左分割符
分隔符匹配程序从字符串不断地读取字符，每次读取一个字符。若发现它是左分隔符，将它压入栈中 。当从输入中读到一个右分隔符时，弹出栈顶地左分隔符，并且查看它是否和右分隔符相匹配。如果它们不匹配（比如，一个左大括号和一个右小括号），则程序报错，如果栈中没有左分割符和右分隔符匹配，或者一直存在着没有被匹配地分隔符，程序也报错。分隔符没有被匹配，表现为把所有地字符读入之后，栈中仍留有分隔符。这个规律符合栈的后进先出的特点。
public class BracketChecker {
private String input;
//构造器
public BracketChecker(String in){
input=in;
}
public void check(){
int stackSize=input.length();
StackX theStack=new StackX(stackSize);
for(int i=0;i<input.length();i++){
char ch=input.charAt(i);
switch (ch){
case '{':
case '[':
case '(':
theStack.push(ch);
break;
case '}':
case ']':
case ')':
if(!theStack.isEmpty()){
char chx=theStack.pop();
if((ch=='}'&&chx!='{')||
(ch==']'&&chx!='[')
||(ch==')'&&chx!='(')){
System.out.println("Error: "+ch+" at "+i);
}
}else{
System.out.println("Error: "+ch+" at "+i);
break;
}
default:
break;
}
}
if(!theStack.isEmpty()){
System.out.println("Error:missing right delimiter");
}
}
}
public class BracketsApp {
public static void main(String[] args) throws IOException {
String input;
while(true){
System.out.print("Enter string containing delimiters: ");
System.out.flush();
input=getString();
if(input.equals(""))
break;
BracketChecker theChecker=new BracketChecker(input);
theChecker.check();
}
}
private static String getString() throws IOException {
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
String s=br.readLine();
return s;
}
}
栈中的push方法和add方法有什么区别
push(E item)
Pushes an item onto the top of this stack.
public boolean add(E e)
Appends the specified element to the end of this Vector.