栈是一种很有意思的数据结构,它的特点是先入后出。大家可以想象一下弹夹,先被压入弹夹的子弹反而会后射出。
栈的特点
- 先入后出
- 只能从一端入栈或出栈
栈的构造
// 顺序栈
public class ArrayStack {
private String[] items; // 栈内元素
private int current; // 栈顶下标,-1代表空栈
private int size; //栈的大小
// 构建一个容量为size的栈
public ArrayStack(int size) {
this.items = new String[size];
this.size = size;
this.current = -1;
}
// 入栈操作
public boolean push(String item) {
// 当栈顶下标等于容量-1时标识栈满,直接返回false,入栈失败。
if (current == size-1) {
return false;
}
// 移动栈顶指针
current++
// 将item放到栈顶
items[current] = item;
return true;
}
// 出栈操作
public String pop() {
// 栈为空,则直接返回null
if (current == -1) {
return null;
}
// 返回栈顶元素
String tmp = items[current];
current--;
return tmp;
}
// 查看栈顶元素
public String peek() {
if (current == -1) {
return null;
}
return items[current];
}
}
可以看出不管是入栈还是出栈,空间复杂度和时间复杂度都是O(1)
栈的应用
栈适用于需要知道最近一次操作或者数据的场合。如leetCode第20题:
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
解题思路:
遍历字符,遇到左扩号则压栈,遇到右扩号则弹出栈顶元素和有扩号进行匹配,若匹配成功则继续遍历,匹配失败则直接返回字符串非法
推荐练习
leetCode 20: 有效的扩号
leetCode 739: 每日温度
leetCode 227: 基本计算器2
网友评论