数据结构 - 栈
栈(英语: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<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
思路
- 根据栈的数据结构特点,我们可以先将所有左括号‘[{(’放进栈中,然后判断当前字符如果是‘)]}’这种的右括号,但是栈顶的括号却不匹配,返回 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,数组,栈,后续还会持续更新数据结构,可能会有队列,链表,递归,红黑树,线段树等等一系列,如果感兴趣,欢迎留言。