数据结构-栈
2019-05-02 本文已影响0人
Gatlin
数据结构-栈
定义
栈（英语：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/yangxiaojie123/designPattern.git
项目简介：
这个项目是我做测试，学习的主要项目，目前里面包含了：
- 一些设计模式的demo（抽象工程模式，适配器模式，外观模式，命令模式，装饰者模式等等）
- 即将学习的数据结构demo，数组，栈，后续还会持续更新数据结构，可能会有队列，链表，递归，红黑树，线段树等等一系列，如果感兴趣，欢迎留言。
扫面下方二维码，关注公众号，回复 ai ，即可领取129G人工智能资源
image
image
关注公众号发送关键字 复仇者联盟4 可以观看免费视频
image
