第2章 栈、队列、链表
第1节 解密QQ号–队列
一串加密的数字"6317 5892 4"，解密规则是先删除第一个数，然后将第二个数放到末尾，删除第3个数，再把第4个数放在末尾…直到剩下最后一个数，将最后一个数也删除。按照删除的顺序，就是原来的数字了(6 1 5 9 4 7 2 8 3 )。
这种解密的过程类似队列，
package aha; public class Queue1 { public static void main(String[] args) { int[] q= {0,6,3,1,7,5,8,9,2,4,0,0,0,0,0,0,0,0,0,0,0}; int head,tail; head = 1; tail = 10;//队尾的下一个 while(head<tail) { System.out.print(q[head]+" "); head++; q[tail]=q[head]; tail++; head++; } } }
//封装一下,其实入队列，出队列也可以封装成方法 package aha; import java.util.Scanner; public class Queue2 { public int[] data = new int[100]; public int head; public int tail; public static void main(String[] args) { Queue2 q = new Queue2(); q.head = 1; q.tail = 1; Scanner sc = new Scanner(System.in); for(int i=0;i<9;i++) { q.data[q.tail]= sc.nextInt(); q.tail++; } while(q.head<q.tail) { System.out.print(q.data[q.head]+" "); q.head++; q.data[q.tail] = q.data[q.head]; q.tail++; q.head++; } } }
第2节 解密回文–栈
回文字符串就是正着读和反着读一样的字符串，如"aha".
借助栈可以判断字符串是否是回文。
栈是一种先进后出的数据结构，类似弹夹，先装的子弹最后打出来，最后装的第一个被打出去。实现起来可以是一个数组和一个栈顶指针top。
//回文字符串判断 //为了演示栈的用法，有些地方没有用方法简化。 package aha; import java.util.Scanner; public class Stack { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String string = sc.next(); int top = -1;//栈顶指针 char[] s = new char[string.length()]; char[] reverse = new char[string.length()]; //入栈 for(int i=0;i<string.length();i++) { s[++top] = string.charAt(i); } //出栈 for(int i=0;i<string.length();i++) { reverse[i] = s[top--]; } String reverse_s = new String(reverse); System.out.println(reverse_s.equals(string)); } }
第3节 纸牌游戏–小猫钓鱼
桌牌上的牌进行的操作可以用栈模拟，打牌的两个人的操作可以用两个队列来模拟。
package aha; import java.util.Scanner; public class Xiaomao { public static void main(String[] args) { queue q1 = new queue(); queue q2 = new queue(); Stack s = new Stack(); int[] book = new int[10]; //玩家拿牌 Scanner sc = new Scanner(System.in); for(int i=1;i<=6;i++) { q1.data[q1.tail++]=sc.nextInt(); } for(int i=1;i<=6;i++) { q2.data[q2.tail++]=sc.nextInt(); } while(q1.head<q1.tail && q2.head<q2.tail) { int t = q1.data[q1.head]; //q1出牌 if(book[t] ==0) { q1.head++; s.top++; s.data[s.top]=t; book[t]=1; } else { q1.head++; q1.data[q1.tail]=t; q1.tail++; while(s.data[s.top]!=t) { book[s.data[s.top]] = 0; q1.data[q1.tail]=s.data[s.top]; q1.tail++; s.top--; } } t = q2.data[q2.head]; //q2出牌 if(book[t] ==0) { q2.head++; s.top++; s.data[s.top]=t; book[t]=1; } else { q2.head++; q2.data[q2.tail]=t; q2.tail++; while(s.data[s.top]!=t) { book[s.data[s.top]] = 0; q2.data[q2.tail]=s.data[s.top]; q2.tail++; s.top--; } } } //判断q2,和q1过程一样 if(q2.head==q2.tail) { System.out.println("q1Win"); System.out.println("q1:"); for(int i=q1.head;i<=q1.tail-1;i++) { System.out.print(" "+q1.data[i]); } if(s.top>0) { System.out.println("桌面上的牌:"); for(int i=1;i<=s.top;i++) { System.out.print(" "+s.data[i]); } }else { System.out.println("桌面上没有牌了"); } }else { System.out.println("q2Win"); System.out.println("q2的牌:"); for(int i=q2.head;i<=q2.tail;i++) { System.out.print(" "+q2.data[i]); } if(s.top>0) { System.out.println("桌面上的牌:"); for(int i=1;i<=s.top;i++) { System.out.print(" "+s.data[i]); } }else { System.out.println("桌面上没有牌了"); } } } } class queue{ public int []data = new int[1000]; public int head; public int tail; public queue() { this.head = 1; this.tail = 1; } } class Stack{ public int[] data = new int[10]; public int top; public Stack() { this.top = 0; } }
第4节 链表
1.结点
结点含两部分，数据data和下一结点next
2.链表
就是使用结点连接成一个表。每个结点的next指向下一个结点。
package aha; import java.util.Scanner; public class List1 { public static void main(String[] args) { node head = null;//头 node q = head;//当前 Scanner sc = new Scanner(System.in); int n = sc.nextInt(); head = null; for(int i=0;i<n;i++) { //读入n个数 int a = sc.nextInt(); node p = new node(); p.data = a; p.next = null; if(head==null) { head = p; q = p; } else { q.next = p; q=p; } } int a = sc.nextInt(); //待插入的数 node t = head; while(t!=null) { if(t.next.data>a) { node p = new node(a,t.next); t.next=p; break;//插入完成 } t=t.next; } t=head; while(t!=null) { System.out.print(" "+t.data); t=t.next; } } } class node{ public int data; public node next; public node() { this.data = 0; this.next = null; } public node(int data,node next) { this.data = data; this.next = next; } }
第5节 模拟链表
使用两个数组，一个数组data存放数据，另一个right存放当前序列的每一个元素的右边元素的在data中位置。 就是把node拆开成两个数组，
