stack，中文翻译为堆栈，其实指的是栈，heap，堆。这里讲的是数据结构的栈，不是内存分配里面的堆和栈。

栈是先进后出的数据的结构，好比你碟子一个一个堆起来，最后放的那个是堆在最上面的。

队列就是排队买苹果，先去的那个可以先买。

栈

public class Stack {
    private int array[];
    private int max;
    private int top;
    public Stack(int max){
        this.max = max;
        array = new int[max];
        top = 0;
    }
    public void push(int value){
        if(isFull()){
            System.out.println("full,can not insert");
            return;
        }
        array[top++]=value;
    }
    public int pop(){
        return array[--top];
    }
    public boolean isEmpty(){
        if(top == 0){
            return true;
        }
        return false;
    }
    public boolean isFull(){
        if(top == max ){
            return true;
        }
        return false;
    }
    public void display(){
        while(!isEmpty()){
            System.out.println(pop());
        }
    }
    public static void main(String[] args) {
        Stack s = new Stack(5);
        s.push(1);
        s.push(3);
        s.push(5);
        s.push(5);
        s.push(5);
        s.display();
    }
}

top指向0，因为每次都push一个元素加一，那么添加到最后一个元素的时候top=max。由于先进后出，那么先出的是最后进的，刚刚为top-1所在的位置。

正确输出：

5
5
5
3
1

public String reverse(String in){
        String out="";
        for (int i = 0; i < in.length(); i++) {
            char c = in.charAt(i);
            push(c);
        }
        while(!isEmpty()){
            out+=pop();
        }
        return out;
    }
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        String string = s.nextLine();
        Stack st = new Stack(string.length());
        System.out.println(st.reverse(string));
        
    }

读取输入也可以用IO读取。

    public static void main(String[] args) {
        InputStreamReader is = new InputStreamReader(System.in);
        BufferedReader b = new BufferedReader(is);
        String string="";
        try {
            string = b.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        Stack st = new Stack(string.length());
        System.out.println(st.reverse(string));
    }

二、栈的使用——分隔符匹配。

public int charat(char c){
    for (int i = 0; i < array.length; i++) {
        if(c == array[i])
            return i;
    }
    return array.length;
}
public void match(String in){
    String out="";
    for (int i = 0; i < in.length(); i++) {
        char c = in.charAt(i);
        if(c == '{' || c == '(' || c == '[' ){
            push(c);
        }
        if(c == '}' || c == ')' || c == ']'){
            char temp = pop();
            if(c == '}' && temp != '{'|| c == ')'  && temp != '('|| c == ']' && temp != ']'){
                System.out.println("can not match in "+i);
            }
        }
    }
    while(!isEmpty()){
        char c = pop();
        if(c == '{'){
            System.out.println("insert } to match "+charat(c));
        }
        if(c == '[' ){
            System.out.println("insert ] to match "+charat(c));
        }
        if(c == '(' ){
            System.out.println("insert ) to match "+charat(c));
        }
    }
}
public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    String string = s.nextLine();
    Stack st = new Stack(string.length());
    st.match(string);
}

result：
klsjdf(klj{lkjjsdf{)
can not match in 19
insert } to match 1
insert ) to match 0

这是可以用栈来实现的工具。

栈中数据入栈和出栈的时间复杂度为常数O(1)，因为与数据个数无关，直接压入弹出，操作时间短，优势便在这里，如果现实生活的使用只需用到先进后出的顺序而且只用到进出数据的比较，那就可以使用栈了。