摘要：棧也稱為后進先出表棧的應用場景操作撤銷例如將操作的每組數(shù)據(jù)存入棧中，如果想要撤銷，只需要彈出棧頂元素，就可以恢復上一步操作了。最后執(zhí)行完成，根據(jù)棧的結構開始彈出數(shù)據(jù)，一步一步再走回方法。

數(shù)據(jù)結構-棧

棧（英語：stack）又稱為堆棧或堆疊，棧作為一種數(shù)據(jù)結構，它按照先進后出的原則存儲數(shù)據(jù)，先進入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）。
　　由于堆疊數(shù)據(jù)結構只允許在一端進行操作，因而按照后進先出（LIFO, Last In First Out）的原理運作。棧也稱為后進先出表

例如：將操作的每組數(shù)據(jù)存入棧中，如果想要撤銷，只需要彈出棧頂元素，就可以恢復上一步操作了。

例如：A方法調(diào)用B方法得到返回值，B調(diào)用C得到返回值，A操作走到了B方法，這個時候可以將A的代碼位置存儲到棧中，然后走到B方法，B操作走到了C方法，這個時候可以將B的代碼位置存儲到棧中。最后C執(zhí)行完成，根據(jù)棧的結構開始彈出數(shù)據(jù)，一步一步再走回A方法。

開括號必須用同一類型的括號閉合。

開方括號必須按正確順序閉合。

例如：正確的:{[()]} [{()}] ({[]}) 等 。錯誤的：[{(})] [}{()] 等。

棧在java.util有一個工具類，先不用，自定義實現(xiàn)一個

創(chuàng)建一個接口，用來統(tǒng)一規(guī)范所有棧實現(xiàn)

package com.datastructure.stack;

public interface Stack {

    /**
     * 向棧插入元素
     * @param e
     */
    public  void push(E e);


    /**
     * 取出最上面的元素，并且返回
     * @return
     */
    public E pop();

    /**
     * 獲取棧的大小
     * @return
     */
    public int getSize();

    /**
     * 判斷棧是否為空
     * @return
     */
    public boolean isEmpty();

    /**
     * 獲取棧最上面的元素
     * @return
     */
    public E peek();
}

用基于數(shù)組的方式來實現(xiàn)一個棧（上文所寫的自定義數(shù)組）

package com.datastructure.stack;

import com.datastructure.array.Array;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-02 15:27
 **/
public class ArrayStack implements Stack{

    Array array;

    public ArrayStack(int capacity){
        array=new Array(capacity);
    }



    public ArrayStack(){
        array=new Array();
    }

    @Override
    public void push(E e) {
        array.addLast(e);
    }

    @Override
    public E pop() {
        return array.removeLast();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }


    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }


    @Override
    public E peek() {
        return array.getLast();
    }

    /**
     * 獲取容量值
     * @return
     */
    public int getCapacity(){
        return array.getCapacity();
    }


    @Override
    public String toString(){
        StringBuffer sb = new StringBuffer();
        sb.append("stack: ");
        sb.append("[");
        for(int i=0;i
測試代碼
package com.datastructure.stack;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-02 16:11
 **/
public class StackTest {

    public static void main(String[] args) {
        ArrayStack integerArrayStack = new ArrayStack<>();
        for(int i=0;i<5;i++){
            integerArrayStack.push(i);
            System.out.println(integerArrayStack);
        }
        Integer pop = integerArrayStack.pop();
        System.out.println("----移除上級元素----value is "+pop);
        System.out.println("-------------移除之后的棧打印------------------");
        System.out.println(integerArrayStack);
    }
}

測試結果
stack: [0]            right value is stack top
stack: [0, 1]            right value is stack top
stack: [0, 1, 2]            right value is stack top
stack: [0, 1, 2, 3]            right value is stack top
stack: [0, 1, 2, 3, 4]            right value is stack top
----移除上級元素----value is 4
-------------移除之后的棧打印------------------
stack: [0, 1, 2, 3]            right value is stack top
leetCode第20題，花括號正確閉合
思路

根據(jù)棧的數(shù)據(jù)結構特點，我們可以先將所有左括號‘[{(’放進棧中，然后判斷當前字符如果是‘)]}’這種的右括號，但是棧頂?shù)睦ㄌ枀s不匹配，返回false
注意控制判斷
這里使用java自帶的棧工具類來實現(xiàn)
leetcode給的測試例子：



 
1
2
3
4
5


輸入例子
()
()[]{}
(]
([)]
{[]}


代碼實現(xiàn)
package com.datastructure.stack;

import java.util.Stack;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-02 16:59
 **/
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isValid("{"name": "網(wǎng)站","num": 3,"sites": [ "Google.com", "Taobao.com", "Waibo.wang" ]}"));
    }
    public boolean isValid(String s) {
        Stack characters = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == "{" || c == "[" || c == "(") {
                characters.push(c);
            } else {
                if(characters.isEmpty()){
                    return false;
                }
                Character peek = characters.pop();
                switch (c) {
                    case "}":
                        if (!peek.equals("{")) {
                            return false;
                        }
                        continue;
                    case "]":
                        if (!peek.equals("[")) {
                            return false;
                        }
                        continue;
                    case ")":
                        if (!peek.equals("(")) {
                            return false;
                        }
                        continue;
                }
            }
        }
        return characters.isEmpty();
    }

    /*public boolean isValid(String s) {
        Stack characters = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == "{" || c == "[" || c == "(") {
                characters.push(c);
            } else {
                if(characters.isEmpty()){
                    return false;
                }
                Character toChar = characters.pop();
                if(c == ")" && toChar != "("){
                    return false;
                }
                if(c == "}" && toChar != "{"){
                    return false;
                }
                if(c == "]" && toChar != "["){
                    return false;
                }
            }
        }
        return characters.isEmpty();
    }*/
}
如果想實現(xiàn)更多字符串關于括號的匹配，如JSON等等，可以根據(jù)棧的特點來實現(xiàn)
代碼例子GIT地址：https://git.dev.tencent.com/y...
項目簡介：
這個項目是我做測試，學習的主要項目，目前里面包含了：

一些設計模式的demo（抽象工程模式，適配器模式，外觀模式，命令模式，裝飾者模式等等）
即將學習的數(shù)據(jù)結構demo，數(shù)組，棧，后續(xù)還會持續(xù)更新數(shù)據(jù)結構，可能會有隊列，鏈表，遞歸，紅黑樹，線段樹等等一系列，如果感興趣，歡迎留言。