数据结构_2:栈
程序员文章站
2024-03-18 11:51:28
...
栈 Stack
写在开头
- 线性结构,栈操作是数组操作的子集
- 先进后出的数据结构(LIFO),只能从一端添加元素,也只能从一端取出元素,这一端称为栈顶
栈的实现:复用动态数组,采用接口的方式进行构造ArrayStack<E>
-
Stack接口:
public interface Stack<E> { /** * 获取栈内元素容量 * @return */ int getSize(); /** * 栈空判断 * @return */ boolean isEmpty(); /** * 入栈 * @param e */ void push(E e); /** * 出栈 * @return */ E pop(); /** * 获取栈顶元素 * @return */ E peek(); }
-
接口实现类:ArrayStack<E>
public class ArrayStack<E> implements Stack<E> { private Array<E> array; public ArrayStack(int capacity) { array = new Array<>(capacity); } public ArrayStack() { array = new Array<>(); } public int getCapacity() { return array.getCapacity(); } @Override public int getSize() { return array.getSize(); } @Override public boolean isEmpty() { return array.isEmpty(); } @Override public void push(E e) { array.addLast(e); } @Override public E pop() { // 等同于:array.remove(size - 1); return array.removeLast(); } @Override public E peek() { // 等同于:array.get(size - 1); return array.getLast(); } @Override public String toString() { return "stack.ArrayStack{" + "array=" + array + '}'; } }
应用
- 编辑器 - Undo(撤销)操作:Undo操作永远撤销的是当前一步操作的上一步操作,从操作栈中依次执行出栈操作。
- 操作系统 - 系统调用栈:记录程序嵌套指令执行中断点,将中断点记录压入栈内(类比子函数执行点,重复子函数执行点入栈操作,直到调用至最底层子函数为止),出栈操作便是对底层中断点结果进行依次返回的操作。
-
编辑器 - 括号匹配,以力扣-T20题目为例:
-
题面:
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
-
题解:利用栈的特性,扫描给定字符串字符元素,对左括号类别字符(
(
、[
、{
),执行入栈操作,对于非左括号类别字符:取栈顶元素进行配对逻辑判断,配对成功并且遍历结束后栈为空作为匹配成功。import java.util.Stack; class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (int i = 0; i < s.length(); i ++) { char c = s.charAt(i); if (c == '(' || c =='[' || c == '{') { stack.push(c); } else { if (stack.isEmpty()) { return false; } if (c == ')' && stack.pop() != '(') { return false; } if (c == ']' && stack.pop() != '[') { return false; } if (c == '}' && stack.pop() != '{') { return false; } } } return stack.isEmpty(); } }
-
上一篇: C++ 实现一个虚拟聊天软件
下一篇: 用两个栈实现队列