表、栈和队列
抽象数据类型
概念
抽象数据类型（ Abstract Data Type，ADT）是带有一组操作的一些对象的集合，是数学的抽象。
实例
表、图、集合以及他们各自的操作（添加、删除等）一起形成的对象。
表 ADT
数组实现
- 连续存储、固定容量
- 线性时间操作
- 打印
- 插入与删除
- 常数时间操作
- 查找
链表实现
- 不连续存储
- 线性时间操作
- 查找
- 打印
- 常数时间操作
- 插入与删除
* 删除最后一项时：
- 找到指向最后节点的项并将其 next 链修改为 null
- 更新持有最后节点的链
Java Collections API 中的表
Collection 接口
public interface Collection<T> extends Iterable<T> {
int size();
boolean isEmpty();
void clear();
boolean contains(T x);
boolean add(T x);
boolean remove(T x);
java.util.Iterator<T> iterator();
}
- 接口并不规定集合如何决定某一元素是否属于集合，需要由实现该接口的具体类来确定
Collection 接口扩展了 Iterable 接口，实现了该接口的类可以拥有增强的 for 循环，该循环施加于这些类之上以观察它们所有的项。
public static <T> void print(Collection<T> coll) {
for ( T item : coll ) {
System.out.println(item);
}
}
Iterator 接口
实现 Iterator 接口的集合需要提供 iterator 方法，通过该方法，每个集合均可创建并返回给用户一个实现了 Iterator 接口的对象并将当前位置的概念在对象内部存储下来。
public interface Iterator <T> {
boolean hasNext(); // 判断下一项是否存在
T next(); // 调用集合的下一项
void remove(); // 删除由 next() 最新返回的项
}
- remove() 在调用一次后不可再调用直至下一次调用 next() 完成。该方法与 Collection 接口的 remove() 方法相比，效率更高。
- 若不使用该接口的 remove() 方法而是自定义操作使得集合结构改变则会导致迭代器不再合法，若继续使用则会抛出并发修改异常。
public static <T> void print(Collection<T> coll) {
Iterator<T> itr = coll.iterator();
while ( itr.hasNext() ) {
T item = itr.next();
System.out.println(item);
}
}
List 接口及其具体实现类
public interface List<T> extends Collection<T> {
T get(int index);
T set(int index, T newVal);
void add(int index, T x);
void remove(int index);
ListIterator<T> listIterator(int pos);
}
ArrayList 类
提供了 List ADT 一种可增长数组的实现，可在需要时自动增加基础数组的容量。
- 优点：对 get 与 set 操作花费常数时间
- 缺点：新项的插入与现有项的删除代价昂贵
LinkedList 类
提供了 List ADT 的双链表实现
- 优点：假定变动项位置已知，新项的插入与现有项的删除均开销很小，常数时间
- 缺点：不易作索引，对 get 的调用代价昂贵
对于搜索而言，Collection 的 contains() 与 remove() 方法对于上述两种实现均花费线性时间，低效。
ListIterator 接口
public interface ListIterator<T> extends Iterator<T> {
boolean hasPrevious();
T previous();
void add(T x);
void set(T newVal);
}
栈 ADT
概念
栈（stack）是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，记作栈顶（top），又称作后进先出表（LIFO）。
栈顶元素是整个模型中唯一可见的元素。
基本操作：
- 进栈（push）：插入元素
- 出栈（pop）：删除并返回最后插入的元素
实现
任何实现表的方法都能实现栈，其中多用 ArrayList 与 LinkedList。
- 链表实现：利用单链表
- 数组实现：模仿 ArrayList 实现
基于上述实现的操作可以非常快的常数时间运行
应用
平衡符号（括号的开闭）、后缀表达式、中缀到后缀的转换、方法调用（方法调用与方法返回基本上类似于开括号和闭括号）
队列 ADT
概念
队列也是表，使用时插入在一端进行而删除则在另一端进行，先进先出（FIFO）。
基本操作：
- 入队（enqueue）：在表的末端（队尾 rear）插入元素
- 出队（dequeue）：删除并返回在表的开头（队头 front）的元素
实现
与栈的情形类似。
数组实现
潜在问题：数组前部可能已经有元素出列，数据并未满位，此时 back 标识可能移动到数组的最后一个下标位置，下一次入队的元素则会存放失败。
解决：循环数组实现，只要 front 或是 back 到达数组的尾端则又将其放回开头。
应用
- 文件服务器：使用其他计算机的用户是按照先到先得的原则访问文件，因此其数据结构是一个队列。
优先队列
根据元素的优先级值决定元素的弹出顺序，实质结构为堆结构，并不是线性结构。
相关的图遍历方式
深度优先遍历 DFS
宽度优先遍历 BFS
高频面试题
查询最值
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的 min 函数。
（时间复杂度应为 O（1））
思路
应用一个辅助栈
压入规则：
- 数据栈直接压入
- 辅助栈增加判断，若栈为空直接压入；否则若将要压入的元素小于栈顶元素则压入
弹出规则：
数据栈弹出时对辅助栈顶进行判断，若栈顶元素与数据栈将要弹出的元素相同，则一起弹出。否则仅弹出数据栈顶。以保证两栈一致性。
实现
public class GetMinDemo {
Stack<Integer> dataStack = new Stack();
Stack<Integer> minStack = new Stack();
public void push(int node) {
dataStack.push(node);
if (minStack.isEmpty() || minStack.peek() > node)
minStack.push(node);
}
public void pop() {
if (minStack.peek() == dataStack.peek())
minStack.pop();
dataStack.pop();
}
public int top() {
return dataStack.peek();
}
public int min() {
return minStack.peek();
}
}
双栈模拟队列
编写一个类，只能用两个栈结构实现队列，支持队列的基本操作 (push，pop)。
给定一个操作序列 ope 及它的长度 n，其中元素为正数代表 push 操作，为 0 代表 pop 操作，
保证操作序列合法且一定含 pop 操作，请返回 pop 的结果序列。
测试样例: [1,2,3,0,4,0], 6
返回： [1,2]
思路
关键点：
- 如果 stackPush 要往 stackPop 中倒入数据，那么必须要把 stackPush 中的所有数据一次性全倒完
- 如果 stackPop 中存在数据（非空），则不能发生倒数据的行为
实现
public class Stack2Queue {
Stack<Integer> stackPush = new Stack<>();
Stack<Integer> stackPop = new Stack<>();
public void push(int node) {
if (stackPop.isEmpty()) {
stackPop.push(node);
} else {
while (!stackPop.isEmpty()) {
int tmp = stackPop.pop();
stackPush.push(tmp);
}
stackPop.push(node);
while (!stackPush.isEmpty()) {
int tmp = stackPush.pop();
stackPop.push(tmp);
}
}
}
public int pop() {
if (stackPop != null)
return stackPop.pop();
else return -1;
}
public int[] twoStack(int[] ope, int n) {
int count = 0;
for(int i = 0; i < n; i++) {
if (ope[i] == 0)
count++;
}
int[] res = new int[count];
int j = 0;
for(int i = 0; i < n; i++) {
if (ope[i] > 0) {
push(ope[i]);
} else res[j++] = pop();
}
return res;
}
}
栈的反转
实现一个栈的逆序，但是只能用递归函数和这个栈本身的 pop 操作来实现，
而不能自己申请另外的数据结构。
给定一个整数数组 A 即为给定的栈，同时给定它的大小 n，请返回逆序后的栈。
思路
利用递归函数传递值
- 获取栈底元素函数
- 弹出并保存栈顶元素
- 判断栈此时是否为空
- 若为空：直接返回保存的栈顶元素
- 若非空：则递归调用本函数，并将步骤 1 获取的栈顶元素重新压入栈中，返回步骤 2.2 递归得到的返回值
- 逆序栈函数
- 获取栈底元素
- 递归调用自身，逆序除栈底元素外的栈
- 将步骤 1 得到的栈底元素再次压入栈顶
实现
// 解法 1
// 移除栈底元素并返回
public int getBottom(Stack<Integer> myStack) {
int res = myStack.pop();
if (myStack.isEmpty()) {
return res;
} else {
int last = getBottom(myStack);
// 压入上一个值
myStack.push(res);
return last;
}
}
// 将栈中元素逆序
public void reverse(Stack<Integer> myStack) {
if (myStack.isEmpty()) return;
int i = getBottom(myStack);
reverse(myStack);
myStack.push(i);
}
// 主调用函数
public int[] reverseStack(int[] A, int n) {
Stack<Integer> myStack = new Stack<>();
for (int i = 0; i < n; i++) {
myStack.push(A[i]);
}
reverse(myStack);
for (int i = 0; i < n; i++) {
A[i] = getBottom(myStack);
}
return A;
}
// 解法 2
public int[] reverseStack1(int[] A, int n) {
if (n == 0)
return null;
int node = A[n - 1];
reverseStack1(A, n - 1);
A[A.length - n] = node;
return A;
}
双栈排序
请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），
要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。
给定一个 int [] numbers，其中第一个元素为栈顶，请返回排序后的栈。
请注意这是一个栈，意味着排序过程中你只能访问到第一个元素。
思路
利用辅助栈实现：
辅助栈压入规则：
- 若辅助栈为空，直接弹出数据栈栈顶元素并压入到辅助栈
- 若辅助栈非空，则比较辅助栈栈顶元素与数据栈栈顶元素的大小
- 若辅助栈栈顶元素小于数据栈栈顶元素，则将数据栈栈顶元素弹出并压入到辅助栈
- 否则先弹出数据栈栈顶元素并保存成临时变量，反复将辅助栈中元素弹出并压入到数据栈中直到满足 2.1 条件，此时将临时变量压入到辅助栈中
当数据栈为空时再将辅助栈中所有元素压入至数据栈，实现排序
实现
// 解法 1： 利用栈实现
public ArrayList<Integer> twoStacksSort1(int[] numbers) {
Stack<Integer> helpStack = new Stack<>();
Stack<Integer> dataStack = new Stack();
for (int i = 0; i < numbers.length; i++) {
dataStack.push(numbers[i]);
}
while (!dataStack.empty()) {
if (helpStack.empty() || dataStack.peek() > helpStack.peek()) {
helpStack.push(dataStack.pop());
}
else {
int temp = dataStack.pop();
while (!helpStack.empty() && helpStack.peek() > temp) {
dataStack.push(helpStack.pop());
}
helpStack.push(temp);
}
}
for (Integer integer : helpStack) {
dataStack.push(integer);
}
ArrayList<Integer> res = new ArrayList<>();
while (!dataStack.isEmpty()) res.add(dataStack.pop());
return res;
}
// 解法 2：利用数组实现
public ArrayList<Integer> twoStacksSort(int[] numbers) {
int len = numbers.length;
// 辅助
int[] help = new int[len];
int i = 0, j = len, current;
while (i < len) {
current = numbers[i++];
if (j == len || current <= help[j]) {
help[--j] = current;
} else if (current > help[j]) {
while (j < len && current > help[j]) {
numbers[--i] = help[j++];
}
help[--j] = current;
}
}
ArrayList<Integer> res = new ArrayList<>();
int k = 0;
while (k < len) res.add(help[len - k++ - 1]);
return res;
}
滑动窗口
有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边，
窗口每次向右边滑一个位置。 返回一个长度为 n-w+1 的数组 res，
res [i] 表示每一种窗口状态下的最大值。 以数组为 [4,3,5,4,3,3,6,7]，w=3 为例。
因为第一个窗口 [4,3,5] 的最大值为 5，第二个窗口 [3,5,4] 的最大值为 5，第三个窗口 [5,4,3] 的最大值为 5。第四个窗口 [4,3,3] 的最大值为 4。第五个窗口 [3,3,6] 的最大值为 6。第六个窗口 [3,6,7] 的最大值为 7。
所以最终返回 [5,5,5,4,6,7]。
给定整形数组 arr 及它的大小 n，同时给定 w，请返回 res 数组。
保证 w 小于等于 n，同时保证数组大小小于等于 500。
思路
利用辅助队列（存放数组下标）实现：
入队规则：
- 若队列为空或队尾对应元素大于当前元素直接插入
- 若队尾元素小于当前元素，则反复出队直到队尾对应元素大于当前元素或队为空时插入当前元素，以保证队头为最大值
出队规则：
- 若队头元素下标超出窗口范围则出队
结果保存：队头为最大值，每个窗口存一个结果
实现
public int[] slide(int[] arr, int n, int w) {
// 存放数组下标
ArrayList<Integer> queue = new ArrayList<>();
int[] res = new int[n - w + 1];
int count = 0, j = 0;
for (int i = 0; i < n; i++, count++) {
// 若队列为空或队尾对应元素大于当前元素直接插入
if (queue.isEmpty() || arr[queue.get(queue.size() - 1)] > arr[i]) {
queue.add(i);
} else {
// 反复出队直到队尾对应元素大于当前元素或队为空时插入当前元素
while (!queue.isEmpty() && arr[queue.get(queue.size() - 1)] <= arr[i])
queue.remove(queue.size() - 1);
queue.add(i);
}
// 若队头元素下标超出窗口范围则移出
if (queue.get(0) == i - w)
queue.remove(0);
// 队头为最大值，每个窗口存一个结果
if (count == w - 1) {
res[j++] = arr[queue.get(0)];
count = w - 2;
}
}
return res;
}
数组变树
对于一个没有重复元素的整数数组，请用其中元素构造一棵 MaxTree，
MaxTree 定义为一棵二叉树，其中的节点与数组元素一一对应，
同时对于 MaxTree 的每棵子树，它的根的元素值为子树的最大值。
现有一建树方法，对于数组中的每个元素，
其在树中的父亲为数组中它左边比它大的第一个数和右边比它大的第一个数中更小的一个。
若两边都不存在比它大的数，那么它就是树根。请设计 O (n) 的算法实现这个方法。
给定一个无重复元素的数组 A 和它的大小 n，请返回一个数组，
其中每个元素为原数组中对应位置元素在树中的父亲节点的编号，若为根则值为 - 1。
测试样例： [3,1,4,2], 4 | 返回：[2,0,-1,2]
思路
利用辅助栈实现（存放数组下标）：
- 若当前元素小于栈顶元素，则当前元素的父节点为栈顶元素
- 若当前元素大于栈顶元素，则栈顶元素出栈，当前元素继续与新的栈顶元素比较，直到 a）栈为空（当前元素无父节点），当前元素入栈；b）当前元素小于栈顶元素，同（1）操作。
实现
public int[] buildMaxTree(int[] arr, int n) {
Stack<Integer> stack = new Stack<>();
int[] res = new int[n];
// 从左起左半部分判断
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
stack.pop();
}
if (stack.isEmpty()) {
res[i] = -1;
} else {
res[i] = stack.peek();
}
stack.push(i);
}
// 清空辅助栈
stack.clear();
// 从右起右半部分判断
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
stack.pop();
}
if (!stack.isEmpty()) {
if (res[i] != -1)
// 左右两边选择较小的那个
res[i] = arr[stack.peek()] < arr[res[i]] ? stack.peek() : res[i];
else res[i] = stack.peek();
}
stack.push(i);
}
return res;
}
京公网安备 11010502036488号