数据结构-栈

摘要：栈也称为后进先出表栈的应用场景操作撤销例如将操作的每组数据存入栈中，如果想要撤销，只需要弹出栈顶元素，就可以恢复上一步操作了。最后执行完成，根据栈的结构开始弹出数据，一步一步再走回方法。

数据结构-栈

栈（英语：stack）又称为堆栈或堆叠，栈作为一种数据结构，它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
　　由于堆叠数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。栈也称为后进先出表

例如：将操作的每组数据存入栈中，如果想要撤销，只需要弹出栈顶元素，就可以恢复上一步操作了。

例如：A方法调用B方法得到返回值，B调用C得到返回值，A操作走到了B方法，这个时候可以将A的代码位置存储到栈中，然后走到B方法，B操作走到了C方法，这个时候可以将B的代码位置存储到栈中。最后C执行完成，根据栈的结构开始弹出数据，一步一步再走回A方法。

开括号必须用同一类型的括号闭合。

开方括号必须按正确顺序闭合。

例如：正确的:{[()]} [{()}] ({[]}) 等 。错误的：[{(})] [}{()] 等。

栈在java.util有一个工具类，先不用，自定义实现一个

创建一个接口，用来统一规范所有栈实现

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();
}

用基于数组的方式来实现一个栈（上文所写的自定义数组）

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题，花括号正确闭合
思路

根据栈的数据结构特点，我们可以先将所有左括号‘[{(’放进栈中，然后判断当前字符如果是‘)]}’这种的右括号，但是栈顶的括号却不匹配，返回false
注意控制判断
这里使用java自带的栈工具类来实现
leetcode给的测试例子：



 
1
2
3
4
5


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


代码实现
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": "网站","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();
    }*/
}
如果想实现更多字符串关于括号的匹配，如JSON等等，可以根据栈的特点来实现
代码例子GIT地址：https://git.dev.tencent.com/y...
项目简介：
这个项目是我做测试，学习的主要项目，目前里面包含了：

一些设计模式的demo（抽象工程模式，适配器模式，外观模式，命令模式，装饰者模式等等）
即将学习的数据结构demo，数组，栈，后续还会持续更新数据结构，可能会有队列，链表，递归，红黑树，线段树等等一系列，如果感兴趣，欢迎留言。