摘要：棧也稱為后進(jìn)先出表?xiàng)５膽?yīng)用場(chǎng)景操作撤銷例如將操作的每組數(shù)據(jù)存入棧中，如果想要撤銷，只需要彈出棧頂元素，就可以恢復(fù)上一步操作了。最后執(zhí)行完成，根據(jù)棧的結(jié)構(gòu)開(kāi)始彈出數(shù)據(jù)，一步一步再走回方法。

數(shù)據(jù)結(jié)構(gòu)-棧

棧（英語(yǔ)：stack）又稱為堆?；蚨询B，棧作為一種數(shù)據(jù)結(jié)構(gòu)，它按照先進(jìn)后出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開(kāi)始彈出數(shù)據(jù)（最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來(lái)）。
　　由于堆疊數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出（LIFO, Last In First Out）的原理運(yùn)作。棧也稱為后進(jìn)先出表

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

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

開(kāi)括號(hào)必須用同一類型的括號(hào)閉合。

開(kāi)方括號(hào)必須按正確順序閉合。

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

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

創(chuàng)建一個(gè)接口，用來(lái)統(tǒng)一規(guī)范所有棧實(shí)現(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ù)組的方式來(lái)實(shí)現(xiàn)一個(gè)棧（上文所寫的自定義數(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
測(cè)試代碼
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("----移除上級(jí)元素----value is "+pop);
        System.out.println("-------------移除之后的棧打印------------------");
        System.out.println(integerArrayStack);
    }
}

測(cè)試結(jié)果
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
----移除上級(jí)元素----value is 4
-------------移除之后的棧打印------------------
stack: [0, 1, 2, 3]            right value is stack top
leetCode第20題，花括號(hào)正確閉合
思路

根據(jù)棧的數(shù)據(jù)結(jié)構(gòu)特點(diǎn)，我們可以先將所有左括號(hào)‘[{(’放進(jìn)棧中，然后判斷當(dāng)前字符如果是‘)]}’這種的右括號(hào)，但是棧頂?shù)睦ㄌ?hào)卻不匹配，返回false
注意控制判斷
這里使用java自帶的棧工具類來(lái)實(shí)現(xiàn)
leetcode給的測(cè)試?yán)樱?/p>



 
1
2
3
4
5


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


代碼實(shí)現(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();
    }*/
}
如果想實(shí)現(xiàn)更多字符串關(guān)于括號(hào)的匹配，如JSON等等，可以根據(jù)棧的特點(diǎn)來(lái)實(shí)現(xiàn)
代碼例子GIT地址：https://git.dev.tencent.com/y...
項(xiàng)目簡(jiǎn)介：
這個(gè)項(xiàng)目是我做測(cè)試，學(xué)習(xí)的主要項(xiàng)目，目前里面包含了：

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