|
前几天，回了老家，怠惰了几天，把云图看了，还看了一季的King of the hill ，简直爽爆，回来了，又要开始学习了，今天我们来学习几种极为常见的数据结构，分别是背包、队列还有栈。
1.3.1：
知识点：
泛型：在java中，我们可以规定集合类型的一个关键属性，像这样（Bag<pig> bag=new Bag<pig>），那么这个包就只能往里放pig类型的对象，当你往里面放入其他类型时，就会编译报错，能自动装箱转换的类型除外。
自动装箱：由于泛型只能设置为引用类型的数据，当我们想限制集合只能是某原始数据类型，如int，float，double之类的，我们只能先将它们变成对应的引用类型，如Int，Float，Double，这样就能成为泛型，当我们设置了这些引用类型时，我们往集合存数据，就会自动装箱，将该原始数据类型转成他的引用类型，简称自动装箱。
下面就进入数据结构的学习：
背包：
背包是一种不支持删除元素的集合类型，主要用于收集元素，迭代遍历所有元素。光进不出，想看可以，拿走？不可能。
队列：
队列遵循先进先出，先进队列的，能先提取出来，就像排队一样，不多说了。
栈：
栈的话遵循后进先出，先进去的被压在底下，后进去的在面上，就想做蛋糕，最后放的那层水果最先吃，蛋糕胚子最后。
讲个例子：算术运算符压栈之后怎么处理？在p81其实讲的非常清晰，整条运算式子从左往右扫描，左括号忽略，数值和运算符分别压栈，当出现右括号时，数值栈出栈两个，运算符栈出栈一个，运算结果入栈，直到扫描完成，得到最终结果。
1.3.2：
定容栈：即在实例化的时候，设定好了栈的大小，超出栈大小的时候，不会再往里压数据。
迭代器的api：hasnext，检查栈内元素个数是否大于1，next将一个元素出栈。
动态调整数组的栈：由于栈用数组实现，数通组有固定大小，当栈大小达到上线时，可以更换更大的数组，然后将数据转移，更换引用对象，从而动态调整栈的大小。
1.3.3：
链表：
链表并不是java直接支持的一种数据结构，C++上用链表方便多了，在java上链表，我们就需要自己写链表的类，设置它的API，我们需要时根据不同的链表，设计不同的节点（当单向链表时，我们设计node的时候，我们只需要设计一个指向下一个node的成员变量，还有一个成员变量要指向一个自己的元素，双向链表的话就还要设计一个指向上一个节点的成员变量）
链表的操作：①表头插入节点，将表头的next指向该节点，该节点的next指向原来的首节点。
②表头删除节点，将表头指向首节点.next，结束。
③表尾插入节点，这个就比较难处理了，我们需要创建一个引用指向末节点，当我们需要在表尾添加节点时，用该引用找到末节点，设置末节点的next，而且修改对末节点的引用变量的引用，改为引用新加入的节点。
④其他节点的插入，想插在那个节点后面则，先将要插入节点的next设置为插入位置的next对应的节点，再讲插入的位置的next设置为要插入节点。
接下来就是做题部分了，这个章节的题目好像有点多哦，开工
1.3.1 我们看回p82，定容栈是用数组实现的，我们要想知道，栈是否满，我们只需要比较一下size是否等于栈的定容就好了，不给代码了，大概知道知道意思就好了。
1.3.2 没什么好说的
1.3.3 对于这个问题，我们能凭借自己的大脑记忆来判断栈出入是否正确，但是若果出入栈的数字变多了呢，100你能记忆吗？
所以我们要从中找到其规律，以下是我参照网络之后的思路，我们将入栈序列和出栈序列同时入栈，然后讲一个引用指向各自的栈顶，当引用的数字相同时出栈，不一样时，入栈的引用往后移，若最后两个栈都空了，则序列合法，两个栈不为空则不合法，我还是我代码整出来吧。
public boolean isLegal(int[] in, int[] out) {
if (in.length != out.length || in.length == 0) {
return false;
}
//输入的栈
LinkedList<Integer> ins=new LinkedList<Integer>();
int j=0;
for (int i = 0; i < in.length; i++) {
//输入压栈
ins.push(in[i]);
//然后在输出上找当前栈顶是否匹配当前输出位置
while(ins.size()>0&&ins.peek()==out[j]){
ins.pop();
j++;
}
}
return ins.size()>0?false:true;
}
1.3.4 这个问题跟前面提到的算术式的压栈其实非常类似的，我就直接上代码吧
public boolean Parenthess(String s){
char[] chars = s.toCharArray();
LinkedList<Character> inS=new LinkedList<Character>();
//为了防止空栈直接进一个右边括号，peek的时候出错
inS.push(' ');
for(int i=0;i<chars.length;i++){
//若是右边部分，就进行配对，配上了就出栈,配不上就绝对是不合法的
if(chars[i]==')'){
if(inS.peek()=='('){
inS.pop();
continue;
}else {
return false;
}
}
if(chars[i]==']'){
if(inS.peek()=='['){
inS.pop();
continue;
}else {
return false;
}
}
if(chars[i]=='}'){
if(inS.peek()=='{'){
inS.pop();
continue;
}else {
return false;
}
}
//若不是右边部分就正常压栈
inS.push(chars[i]);
}
//最后看看有没有没被匹配出栈的左边的括号，有就返回错，无则返回true
if(inS.size()>1){
return false;
}else {
return true;
}
}
1.3.7 peek：stack上有一个first栈头，返回first.item就好了。
1.3.9 补全左括号，跟那个运算式子有点关系，直接上代码吧
public void becomeWhole(String s){
String[] strings = s.split("");
Stack<String> whole=new Stack<String>();
Stack<String> operaters=new Stack<String>();
//正则，用来匹配数字和运算符
String pattern="[0-9]";
String pattern1="(\\+|\\-|\\*|\\/)";
Pattern p=Pattern.compile(pattern);
Pattern p1=Pattern.compile(pattern1);
Matcher matcher;
Matcher matcher1;
for(int i=0;i<strings.length;i++){
//如果是0-9的话压进全栈
//如果是+-*/就压进运算符栈
matcher=p.matcher(strings[i]);
matcher1=p1.matcher(strings[i]);
if(matcher1.find()){
operaters.push(strings[i]);
continue;
}
if(matcher.find()){
whole.push(strings[i]);
continue;
}
//如果是），whole弹两个，运算符弹一个，加上括号组成真正的运算式
if(strings[i].equals(")")){
String s1=whole.pop();
String s2=whole.pop();
String o1=operaters.pop();
whole.push("("+s2+o1+s1+")");
}
}
System.out.println(whole.pop());
}
1.3.10 中序换成后序，我们首先思考一个问题，什么是前序，中序，后序，这就跟我们运算值和运算符的摆放位置有关系了。
我一般都用的是中序，例如1+2，运算符在运算值中间，前序则是+12，后续则是12+，好吧，其实超简单的，讲我上面的代码稍微改一下就好了。
1.3.11 跟运算式入栈基本无差，好吧
public void EvaluatePostfix(String s){
String[] strings = s.split("");
Stack<Integer> whole=new Stack<Integer>();
Stack<String> operaters=new Stack<String>();
String pattern="[0-9]";
String pattern1="(\\+|\\-|\\*|\\/)";
Pattern p=Pattern.compile(pattern);
Pattern p1=Pattern.compile(pattern1);
Matcher matcher;
Matcher matcher1;
for(int i=0;i<strings.length;i++){
//如果是0-9的话压进全栈
//如果是+-*/就压进运算符栈
matcher=p.matcher(strings[i]);
matcher1=p1.matcher(strings[i]);
if(matcher1.find()){
operaters.push(strings[i]);
continue;
}
if(matcher.find()){
whole.push(Integer.parseInt(strings[i]));
continue;
}
//如果是），whole弹两个，运算符弹一个，加上括号组成真正的运算式
if(strings[i].equals(")")){
int n1=whole.pop();
int n2=whole.pop();
String o1=operaters.pop();
if(o1.equals("+")){
whole.push(n2+n1);
}
if(o1.equals("-")){
whole.push(n2-n1);
}
if(o1.equals("*")){
whole.push(n2*n1);
}
}
}
System.out.println(whole.pop());
}
1.3.12 利用迭代器，将数据取出，在塞进副本，完成在传出来
public Stack<String> copy(Stack<String> s){
Stack<String> copy=new Stack<>();
Iterator<String> iterator=s.iterator();
while (iterator.hasNext()){
String next = iterator.next();
System.out.print(next);
copy.push(next);
}
return copy;
}
1.3.13 看1.3.3吧。
1.3.14 直接上代码吧，因为是数组实现的数组，所以节点就不需要next了
public class ResizingArrayQueueOfStrings {
class Node{
String s;
public Node(String s) {
this.s = s;
}
public String getS() {
return s;
}
public void setS(String s) {
this.s = s;
}
}
int size;
//队头和队尾
int f=0;
int l=0;
public ResizingArrayQueueOfStrings(int size) {
this.size = size;
queue=new Node[size];
}
private Node[] queue;
//进队列
public void push(String s){
if((l)==size){
resizing();
}
Node n=new Node(s);
queue[l]=n;
l++;
}
//出队列
public void pop(){
System.out.println(queue[f]);
f++;
}
//每次扩容将容量X2，引用新的数组
private void resizing(){
size=size*2;
Node[] noeq=new Node[size];
for(int i=0;i<queue.length;i++){
noeq[i]=queue[i];
}
queue=noeq;
}
}
1.3.15 毫无技术难度，好吧
public String getdesc(int n){
if(n>(l-f)){
System.out.println("无该字符");
return "error";
}else {
return queue[l-n].s;
}
}
1.3.16 em。。。。
public class ResizingArrayQueueOfDates {
private Date[] queue;
int size;
//队头和队尾
int f=0;
int l=0;
public ResizingArrayQueueOfDates(int size) {
this.size = size;
queue=new Date[size];
}
class Date {
int year;
int month;
int day;
public Date(String s) {
String[] datepart = s.split("/");
this.year = Integer.parseInt(datepart[0]);
this.month = Integer.parseInt(datepart[1]);
this.day = Integer.parseInt(datepart[2]);
}
}
public void input(String s){
String[] dates=s.split(" ");
for(String d:dates){
if((l)==size){
resizing();
}
Date date=new Date(d);
queue[l]=date;
l++;
}
}
//每次扩容将容量X2，引用新的数组
private void resizing(){
size=size*2;
Date[] noeq=new Date[size];
for(int i=0;i<queue.length;i++){
noeq[i]=queue[i];
}
queue=noeq;
}
}
1.3.17 跟上面那题基本一样的思路就不整了
1.3.19
public void deLinkedListL(){
Node find=first;
//找链表last节点的前一个节点
while(find.next!=last){
find=find.next;
}
//将其的last设为空，将其设为last
find.next=null;
last=find;
System.out.println("删除表尾节点完成");
}
1.3.20 直接看代码吧
public void deleteN(int n){
Node del=first;
//比如我要删除第五个，那我就要先读到第四个，然后将第四个的后面隔一个赋值到第四个的next上，那就可以吧第五个跳过了，
// 然后GC就把第五个收走了，因为链表从1开始，那就到一就删。
while(n>1){
if(del.next!=null){
del=del.next;
n--;
}else{
System.out.println("节点不足");
return;
}
}
System.out.println(del.i);
del.next=del.next.next;
}
1.3.21 直接往下遍历，有就返回true，若是最后都没有找到就返回false
public boolean find(int key){
Node find=first;
while (find.next!=null){
if(find.i==key){
return true;
}
find=find.next;
}
return false;
}
1.3.24 这个用我上面写的那个deleteN就能实现，n+1就好了，他说的拿个无需操作，那就忽视的我的sout吧。
1.3.25 先遍历，找到之后，保存该节点的next，将新增节点插进去后，新增节点的next设为保存的节点
public void insertAfter(int key,int node){
Node find=first;
while (find.next!=null){
if(find.i==key){
Node temp=find.next;
find.next=new Node(node);
find.next.next=temp;
return;
}
find=find.next;
}
}
1.3.26 遍历，查看自己的next时候符合key，是的话就删，不是继续走
public void remove(int key){
Node find=first;
while(find.next!=null){
if(find.next.i==key){
find.next=find.next.next;
}
find=find.next;
}
}
1.3.27 遍历，然后逐一比较，冒泡一遍求最大
public void getMax(){
Node find=first;
int max=find.i;
while (find.next!=null){
if(find.next.i>max){
max=find.next.i;
}
find=find.next;
}
System.out.println(max);
}
1.3.28 递归手法求出求上一问
public int getMax(Node n,int max){
if(n.i>max){
max=n.i;
}
if(n.next==null){
return max;
}
return getMax(n.next,max);
}
public void go(){
System.out.println(getMax(first,first.i));
}
1.3.29 将last的next设成first就好了，没什么技术难度。
1.3.31 这个将node设置成双向的就好了，一个next指向下一个节点，一个last指向上一个节点。
1.3.32 Steque
public class Steque {
class Node{
int i;
Node next;
public Node(int i) {
this.i = i;
}
}
Node first;
Node last;
public Steque() {
Node n=new Node(0);
first=n;
last=n;
}
public Node pop(){
//将first传给first.next,然后把first传进去
if(first!=null){
Node p=first;
first=first.next;
return p;
}else {
System.out.println("链表为空");
return null;
}
}
public void push(int i){
//将新的节点的next设成原来的first节点，然后将新的节点设成first节点
Node n=new Node(i);
n.next=first;
first=n;
}
public void enqueue(int i){
//把之前的尾节点的next赋值新进的节点，再把新节点设成尾节点
Node n=new Node(i);
last.next=n;
last=n;
}
}
1.3.33Deque的api，用数组太蠢了，每次表头插入，得整个数组移动一位，表头删除又要数组向前一位，我用的直接引用的形式
public class Deque {
Node first;
Node end;
class Node{
int i;
Node next;
Node last;
public Node(int i) {
this.i = i;
}
}
public void push(int i){
Node n=new Node(i);
if(first==null){
first=n;
end=n;
}else {
first.last=n;
n.next=first;
first=n;
}
show();
}
public Node pop(){
if(first==null){
System.out.println("队列没东西，别闹了");
return null;
}else {
Node n=first;
first.next.last=null;
first=first.next;
show();
return n;
}
}
public void pushEnd(int i){
Node n=new Node(i);
if(first==null){
first=n;
end=n;
}else {
end.next=n;
n.last=end;
end=n;
show();
}
}
public Node popEnd(){
if(first==null){
System.out.println("队列没东西，别闹了");
return null;
}
Node n=end;
end.last.next=null;
end=end.last;
show();
return n;
}
void show(){
Node n=first;
do {
System.out.print("\t"+n.i);
n=n.next;
}while(n!=null);
System.out.println("\t"+"f---"+first.i+"\t"+"e---"+end.i);
}
}
1.3.34 随机背包，在迭代器里将其乱序展示
public class RandomBag {
int[] bag=new int[100];
int size;
class Iterator{
int[] rBag;
int size;
public Iterator(int[] bag,int size) {
this.size=size;
Random random=new Random();
rBag=new int[size];
for(int i=0;i<size;i++){
rBag[i]=bag[i];
}
int temp=0;
for(int i=0;i<size;i++){
int r = random.nextInt(size);
temp=rBag[i];
rBag[i]=rBag[r];
rBag[r]=temp;
}
}
public void show(){
for(int i=0;i<size;i++){
System.out.print("\t"+rBag[i]);
}
System.out.println();
}
}
public boolean idEmpty(){
if(bag[0]==0){
return false;
}else {
return true;
}
}
public int size(){
return size;
}
public void add(int i){
bag[size]=i;
size++;
}
public void iteratorShow(){
new Iterator(bag,size).show();
}
}
1.3.35 随机队列
package chapter1_3;
import java.util.Random;
public class RandomQueue {
Card[] cards;
int size;
int last;
public RandomQueue(int size) {
this.size = size;
cards=new Card[size];
last=0;
}
public void resizing(int size){
this.size=size;
Card[] temp=new Card[size];
for(int i=0;i<last;i++){
temp[i]=cards[i];
}
cards=temp;
}
public void enqueue(String num, String huase){
Card c=new Card(num,huase);
//若果尾巴也有数据就扩张
if(cards[size-1]!=null){
resizing(size*2);
}
cards[last]=c;
last++;
}
public Card dequeue(){
Card c=cards[0];
last--;
for(int i=0;i<last;i++){
cards[i]=cards[i+1];
}
//如果中间也是空的就收缩
if(cards[(size/2)-1]==null){
resizing(size/2);
}
//抽卡的时候触发置换,用末尾的话，初期发牌太有规律了，根本没有起到洗牌的功能，所以我换成了头部置换
Random random=new Random();
int r = random.nextInt(last);
Card temp=cards[r];
cards[r]=cards[0];
cards[0]=temp;
// System.out.println("r"+cards[r]);
// System.out.println("l"+cards[0]);
return c;
}
public Card sqmple(){
Random random=new Random();
int r = random.nextInt(last);
return cards[r];
}
public void start(){
String num;
String huase="";
for(int i=0;i<4;i++){
if(i==0){
huase="方块";
}
if(i==1){
huase="梅花";
}
if(i==2){
huase="红心";
}
if(i==3){
huase="黑桃";
}
for(int j=1;j<14;j++){
if(j==11){
num="J";
}else if(j==12){
num="Q";
}else if(j==13){
num="K";
}else {
num=""+j;
}
enqueue(num,huase);
}
}
}
}
1.3.36 这个我就不写了，没多大意思，数组遍历呗
1.3.37 经典题目：约瑟夫环，我打算用一个环形的链表解决这个问题
public class Josephus {
Node start;
Node last;
int kill;
class Node{
int name;
Node next;
public Node(int name) {
this.name = name;
}
}
public Josephus(int size,int kill) {
this.kill=kill;
for(int i=0;i<size;i++){
enqueue(i+1);
}
}
public void enqueue(int name){
Node n=new Node(name);
//当前链表为空的时候，将该节点设为start
if(start==null){
start=n;
last=n;
n.next=n;
}else{
last.next=n;
n.next=start;
last=n;
}
}
public void startKill(){
int k;
Node getKilled=last;
while(true){
k=kill;
while (k>1){
//按着开枪间隔往后走
getKilled=getKilled.next;
k--;
}
System.out.println(getKilled.next.name);
if(getKilled.next==getKilled){
System.out.println("结束");
break;
}
//把要死的节点的前面的节点的next设为死的节点的next，节点死掉
getKilled.next=getKilled.next.next;
}
}
}
1.3.38 说下思路吧，就不写代码了，先是链表，有个int类型标明进来过多少个节点，每个节点进入的时候都会有个int类型的数据，上面标明该节点是第几进来的，关于这个delete方法，获取了k之后，直接搜索队列，int数据类型=k，直接拿出来。
1.3.39 环形缓存器
public class RingBuffer {
Node start;
Node last;
int capacity;
int now;
class Node{
public Node(int name) {
this.name = name;
}
Node next;
int name;
}
public RingBuffer(int capacity) {
this.capacity = capacity;
now=0;
}
void enqueue(int name){
Node n=new Node(name);
if(start==null){
start=n;
last=n;
n.next=n;
now++;
}else {
last.next=n;
n.next=start;
last=n;
now++;
}
if(now==capacity){
consume();
}
}
public void product(int i){
System.out.println("生产"+i+"个");
while(i-->0){
enqueue(now);
}
}
void consume(){
Node n=start;
System.out.println("启动缓存消耗");
for(int i=0;i<capacity;i++){
System.out.print(n.name);
n=n.next;
}
System.out.println();
start=null;
last=null;
}
}
1.3.40 前移编码，又是一个非常简单的，不上代码了，每次输入的时候，进行链表节点逐个校对，无就存，有就删掉，从头的部分重新进入一次，以前做的find功能修改一下就可以用了。
1.3.41和1.3.42基本一致思路，就是将需要被复制的队列或者栈，通过构造器，遍历复制一遍就好了。
1.3.43 文件列表
public class FileList {
File[] files;
int p=0;
int maxl;
class File{
String name;
int level;
public File(String name, int level) {
this.name = name;
this.level = level;
}
}
public FileList() {
files=new File[100];
this.maxl=0;
}
public void search(String filePath,int level){
if(level>maxl){
maxl=level;
}
java.io.File f=new java.io.File(filePath);
java.io.File[] list = f.listFiles();
for (java.io.File s:list
) {
files[p]=new File(s.getName(),level);
p++;
}
for(java.io.File s:list){
if (s.isDirectory()){
search(s.getPath(),level+1);
}
}
}
public void show() {
int layer = maxl+1;
while (layer-- > 0) {
for (int i = 0; i < p; i++) {
if (files[i].level == maxl - layer) {
System.out.print("\t" + files[i].name+"\t");
}
}
System.out.println();
}
}
}
1.3.44 文本编辑缓冲区，说下思路吧，两个栈来进行存储，一个栈是光标左边的字符，另一个栈是光标右边的字符，光标往左移则右边的栈出栈，出栈的字符入栈右边，往右边动则blabla，删除的话，就左边出栈，然后输出出来，插入字符则是往左边的栈进栈。
1.3.45 设定一个整型变量，进栈+1，出栈-1，一直往后度，整型变量一小于一，就返回报错。
1.3.46 入栈问题，入栈的次序决定了出栈的先后，不管怎么进其他的数据都一样
1.3.47 连接队列，一个方法获取两个队列，将第二个队列的数据出列，入列第二个队列，最后得到一个链接完成的队列
连接栈的话就麻烦点，其中一个栈的全部提取出来存在数组里，在逆序压入另一个栈
1.3.48 双向队列里一开始有一个节点叫做bottom，左边压一个栈，右边压一个，取到碰到bottom则是栈已取空
1.3.49 嗯。。。。两个栈，现将队列所有数据压入一栈，再出栈压入二栈，要出列的话，则直接二栈出栈，要入队列的话，就先将二栈所有出栈，入栈一栈，需要入队列的的数据直接压入一栈
1.3.50 一种乐观锁的手法，认为一般不会有人改我的数据，但是上锁被改过之后，就会报异常
| 
转播
