一. 数据结构
image.png
1.1 指针的原理
image.png
1.2 链表
image.png
链表的基本操作:
image.png
链表 VS 数组:
数组的长度是固定的，而且存储二项式很麻烦，所以底层用链表比较多。
image.png
栈和队列 都是通过 链表或数组来实现的
二. 栈
image.png
栈的应用:
- 函数或子程序调用
- 博弈树遍历
- 编辑器undo实现
三. 队列
image.png
四. 栈和栈实战
4.1 栈实战
http://poj.org/problem?id=2559
image.png
package com.suanfa.栈;
import java.util.Stack;
public class 最大矩形面积 {
public static void main(String[] args) {
int[] arr1 = {8,7,6,5,4,3,2};
int rst = 0;
rst = largestRectangleArea(arr1);
System.out.println(rst);
//bubbleSort2(arr1);
}
/**
* 遍历数组
* 1.栈为空则入栈
* 2.若h[i]>=栈顶元素,入栈
* 3.若h[i]<栈顶元素,则开始出栈计算面积,并将最后出栈的h[x]值改为h[i]再重新入栈
*
* @param heights 数组,本例会创建个新数组,在数组最后一个位置补个高度为0的图
* @return 最大面积值
*/
public static int largestRectangleArea(int[] heights) {
int max = 0;
Stack<Integer> s = new Stack<>();
int [] h = new int[heights.length + 1];
for (int i =0; i < h.length; i++) {
h[i] = i == heights.length ? 0 : heights[i];
//System.out.println("i="+i);
//System.out.println("h[i]=" + h[i]);
if (s.empty()) {
//空栈直接入栈
s.push( i );
continue;
}
//System.out.println("h[s.peek()]:"+h[s.peek()]);
if (h[i] < h[s.peek()]) {
//遇到小于栈顶的值，开始出栈，查找最大面积
int top = 0;
while (!s.empty() && h[s.peek()] > h[i]) {
//top等于栈移出的元素的值
top = s.pop();
max = Math.max(( i - top ) * h[top], max);
//System.out.println("top="+top);
//System.out.println("h[top]="+h[top]);
//System.out.println("max="+max);
}
//将最后出栈的高度改为h[i]重新入栈
h[top] = h[i];
System.out.println("top=" + top + ",");
s.push( top );
s.push( i );
} else {
s.push( i );
}
/*for (Integer s1 : s) {
System.out.print("栈:"+s1+",");
System.out.println();
}*/
//System.out.println("===================================");
}
return max;
}
}
4.2 队列实战
http://poj.org/problem?id=2259
题意：
维护一个team queue，每次入队列，如果跟这个元素在一个队里的元素已经在这个大队里，那么这个元素可以插到他们队友的后面。给出有几个队以及这些队里面包含的元素，输出要求出队的时候的元素。
分析:
按照题目输入的顺序，给队编号。因为属于同一个队的可以插队，所以在队列中，同一个队的必然在一起。所以一个总的队列，只用记录下来队伍的编号就可以了，再记录下来每个队伍中的顺序。
代码:
package com.suanfa.队列;
import java.util.*;
public class TeamQueue {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
TeamQueue tq = new TeamQueue();
int count = 1;
while (true) {
List<Set<String>> listSet = new ArrayList<Set<String>>();
List<Queue<String>> listQueue = new ArrayList<Queue<String>>();
Queue<Integer> indexs = new LinkedList<Integer>();
int n = sc.nextInt();
if (n == 0) {
break;
}
for (int i = 0; i < n; i++) {
int m = sc.nextInt();
Queue queue = new LinkedList();
listQueue.add(queue);
Set<String> set = new HashSet<String>();
listSet.add(set);
for (int j = 0; j < m; j++) {
listSet.get(i).add(sc.next());
}
}
System.out.println("Scenario #" + count);
count++;
while (true) {
String str = sc.next();
if (str.equals("ENQUEUE")) {//入队
String num = sc.next();
tq.add(num, listQueue, listSet, indexs);
} else if (str.equals("DEQUEUE")) {//出队
System.out.println(tq.remove(listQueue, indexs));
} else if (str.equals("STOP")) {//结束
break;
}
}
System.out.println();
}
}
public void add(String num, List<Queue<String>> listQueue, List<Set<String>> listSet, Queue<Integer> indexs) {//入队
int index = select(listSet, num);
if (listQueue.get(index).isEmpty()) {
indexs.add(index);
listQueue.get(index).add(num);
} else {
listQueue.get(index).add(num);
}
}
public String remove(List<Queue<String>> listQueue, Queue<Integer> indexs) {//出队
while (true) {
int index = indexs.peek();
String str = listQueue.get(index).poll();
if (listQueue.get(index).isEmpty()) {
indexs.remove();
}
return str;
}
}
public int select(List<Set<String>> listSet, String num) {//选队
for (int i = 0; i < listSet.size(); i++) {
if (listSet.get(i).contains(num)) {
return i;
}
}
return -1;
}
}
网友评论