常用数据结构

常用数据结构

栈

特点和基本思想

后进先出的数据结构:last-in-first-out
可以用单链表实现

支持API

pop():弹出栈顶元素
peek():查看栈顶元素
push(Element e):压栈
empty():栈是否为空
search(Object o):在栈中的位置。栈顶元素为1

应用场景

只关心上一次的操作
处理完上一次操作后,能在O(1)时间内找到更前一次的操作

力扣题目-739

每日温度

队列

特点和基本思想

先进先出:first-in-first-out

应用场景

需要按照一定的顺序对数据进行操作,而操作的数据在不断的变换中的时候
广度优先搜索-第六节课详细介绍

力扣题目

双端队列

特点和基本思想

先进先出:first-in-first-out
利用双链表实现
可以在O(1)的时间内对链表的头尾进行数据的查看、添加和删除

支持API

Insert 头部插入和尾部插入
add和offer的区别在于,当队列有长度约束时,是否会抛出异常
void addFirst(Element e);
boolean offerFirst(Element e);
void addLast(Element e);
booolean offerLast(Element e);
Remove 头部删除和尾部删除
remove和poll的区别在于,当队列对空,是否会抛出异常
E removeFirst();
E pollFirst();
E removeLast();
E pollLast();
Examinse 检查头部和尾部
get和peek的别在于,当队列对空,是否会抛出异常。
E getFirst();
E peekFirst();
E getLast();
E peekLast();

应用场景

长度动态变换的窗口或者连续区间

力扣题目-239滑动窗口最大值

树

树的共性

树的问题大多和递归有关

树的形状

普通二叉树
平衡二叉树:左右子树高度不超过1二叉排序树
完全二叉树:与满二叉树的编号位置完全相同。
四叉树
多叉树

树的遍历

前序遍历:从根部开始,根-左-右
中序遍历:从根部开始,左-根-右
后续遍历:从根部开始,左-右-跟

力扣题目-230二叉搜索中第K小的元素

评论

暂无评论