数据结构-栈
数据结构-栈
定义
栈(英语:stack)又称为堆栈或堆叠,栈作为一种数据结构,它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。栈也称为后进先出表
栈的应用场景
undo操作(撤销)
- 例如:将操作的每组数据存入栈中,如果想要撤销,只需要弹出栈顶元素,就可以恢复上一步操作了。
程序调用的系统栈
- 例如:A方法调用B方法得到返回值,B调用C得到返回值,A操作走到了B方法,这个时候可以将A的代码位置存储到栈中,然后走到B方法,B操作走到了C方法,这个时候可以将B的代码位置存储到栈中。最后C执行完成,根据栈的结构开始弹出数据,一步一步再走回A方法。
判断括号是否有效。下文会有代码实现(详细规则描述可以参考leetcode第20题)
- 开括号必须用同一类型的括号闭合。
- 开方括号必须按正确顺序闭合。
- 例如:正确的:{[()]} [{()}] ({[]}) 等 。错误的:[{(})] [}{()] 等。
自定义栈基类的代码实现
- 栈在java.util有一个工具类,先不用,自定义实现一个
创建一个接口,用来统一规范所有栈实现
package com.datastructure.stack; public interface Stack<E> { /** * 向栈插入元素 * @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<E> implements Stack<E>{ Array<E> array; public ArrayStack(int capacity){ array=new Array<E>(capacity); } public ArrayStack(){ array=new Array<E>(); } @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<array.getSize();i++){ sb.append(array.get(i)); if(i!=array.getSize()-1){ sb.append(", "); } } sb.append("] right value is stack top"); return sb.toString(); } }
测试代码
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<Integer> 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<Character> 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<Character> 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,数组,栈,后续还会持续更新数据结构,可能会有队列,链表,递归,红黑树,线段树等等一系列,如果感兴趣,欢迎留言。
相关推荐
koushr 2020-11-12
zhangxiafll 2020-11-13
kikaylee 2020-10-31
范范 2020-10-28
MILemon 2020-10-22
hugebawu 2020-10-12
LauraRan 2020-09-28
shenwenjie 2020-09-24
omyrobin 2020-09-23
guangcheng 2020-09-22
qiangde 2020-09-13
hanyujianke 2020-08-18
晨曦之星 2020-08-14
xiesheng 2020-08-06
KAIrving 2020-08-02
xiesheng 2020-08-02
范范 2020-07-30
chenfei0 2020-07-30