一.栈 Stack
栈也是一种线性的数据结构
相比数组,栈相对应的操作是数组的子集。
只能从一端添加元素,也只能从一端取出元素。这一端成为栈顶。
1,2,3依次入栈得到的顺序为 3,2,1,栈顶为3,只能取出栈顶的元素3(出栈)。
栈是一种后进先出的数据结构 LIFO(Last In First Out)
栈的应用
1.无处不在的Undo操作(撤销)
2.程序调用的系统栈
编程时,用到子过程调用时,当一个子过程执行完成之后自动回到上层中断的位置:
系统栈记录每次调用过程中中断的那个点
function A(){
... //1
B() //
... //3 }
function B(){
... //1
C() //
... //3 }
function B(){
... //1
... //
... //3 }
A2 B2依次入栈 B2 A2依次出栈
3.编译器 括号匹配(第三条会用代码实现)
二.栈的基本实现(基于动态数组)
Stack<E> 5个方法
void push(E) 入栈 O(1)均摊
E pop() 出栈 O(1)均摊
E peek() 查看栈顶元素 O(1)
int getSize() 栈里元素个数 O(1)
boolean isEmpty() 判断栈是否为空 O(1)
具体底层实现,用户不关心,实际底层有多种实现方式。
设置Interface Stack<E>,设置五种方法,用类ArrayStack<E>继承接口具体实现(基于第一章动态数组)
Interface Stack<E>
public interface Stack<E> { int getSize();
boolean isEmpty();
void push(E e);
E pop();
E peek(); }
ArrayStack<E>继承接口
public class ArrayStack<E> implements Stack<E>
1.基本的构造函数
Array<E> array; public ArrayStack(int capacity){
array = new Array<>(capacity);
} public ArrayStack(){
array = new Array<>();
}
基础操作:判断是否为空,获取栈中元素个数,获取栈的容量
@Override
public int getSize() {
return array.getSize();
} @Override
public boolean isEmpty() {
return array.isEmpty();
} public int getCapacity(){
return array.getCapacity();
}
2.入栈操作
@Override
public void push(E e) {
array.addLast(e);
}
3.出栈操作
@Override
public E pop() {
return array.removeLast();
}
在第一章动态数组的Array类中加入getLast()和getFirst()方法得到动态数组的最后一个数和第一个数
其中注意,return get(size - 1); 不可写为return data[size - 1];因为万一size为0,data[-1]索引不合法
//获取index索引位置的元素
E get(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Get failed. Index is illegal");
}
return data[index];
} public E getLast(){
return get(size-1);
//return data[size - 1]; 万一size为0,产生不合法索引
} public E getFirst(){
return get(0);
}
4.栈的查看栈顶操作
@Override
public E peek() {
return array.getLast();
}
5.重写toString方法,让输出更具有可读性
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack:");
res.append("[");
for(int i = 0 ; i < array.getSize() ; i ++){
res.append(array.get(i));
if(i != array.getSize()-1){
res.append(",");
}
}
res.append("] top");
return res.toString();
}
三.栈的括号匹配
思想:将一个字符串遍历,对于每一个字符如果为左括号就入栈,如果为右括号,就查看此时栈顶的元素是否为匹配的左括号,如果不是就return false,最后return stack.isEmpty();而不是true。
栈顶元素反映了在嵌套的层次关系中,最近的需要匹配的元素。
public boolean isValid(String s){
ArrayStack<Character> stack = new ArrayStack<>();
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; char topChar = stack.pop();
if(c == ')' && topChar != '(')
return false;
if(c == ']' && topChar != '[')
return false;
if(c == '}' && topChar != '{')
return false;
}
} return stack.isEmpty();
}