操作受限
的特殊线性表。
栈顶Top(线性表的尾端)
进行操作。
// 入栈个数 1/2/3/4
Ain Aout Bin Bout Cin Cout Din Dout --> ABCD
Ain Aout Bin Bout Cin Din Dout Cout --> ABDC
Ain Aout Bin Cin Cout Din Dout Bout --> ACDB
Ain Aout Bin Cin Cout Bout Din Dout --> ACBD
Ain Aout Bin Cin Din Dout Cout Bout --> ADCB
Ain Bin Bout Aout Cin Cout Din Dout --> BACD
Ain Bin Bout Aout Cin Din Dout Cout --> BADC
Ain Bin Bout Cin Cout Aout Din Dout --> BCAD
Ain Bin Bout Cin Cout Din Dout Aout --> BCDA
Ain Bin Bout Cin Din Dout Cout Aout --> BDCA
Ain Bin Cin Cout Din Dout Bout Aout --> CDBA
Ain Bin Cin Cout Bout Din Dout Aout --> CBDA
Ain Bin Cin Cout Bout Aout Din Dout --> CBAD
Ain Bin Cin Din Dout Cout Bout Aout --> DCBA
https://zhuanlan.zhihu.com/p/97619085
top == 0
top == stackElem.length
top
stackElem[top - 1]
public class SqStack {
private Object[] stackElem; //栈对象数组
private int top; //长度、下一个存储位置 等
}
public void push(Object x) {
if(top == stackElem.length) { //栈满
throw new RuntimeException("栈满");
} else {
stackElem[top] = x;
top++;
}
}
public void push(Object x) {
if(top == stackElem.length) { //栈满
throw new RuntimeException("栈满");
} else {
stackElem[top++] = x;
}
}
public class LinkStack {
private Node top; //栈顶指针
}
public void push(Object x) {
Node p = new Node(x); // 创建新结点p
p.next = top; // 1.p的指针域指向栈顶元素
top = p; // 2.栈顶指针top指向新结点p
}
public Object pop() {
if(top == null) { //空栈 isEmpty()
return null;
} else {
Node p = top; // 1 存放栈顶元素
top = top.next; // 2 将top指向栈顶的下一个元素
return p.data; // 3 返回栈顶元素数据
}
}
p76
9992992347234947324732498327427342472987427427984724274
+
9990920943824283492834824820984028348204209384029293
p79
逆波兰记法
中序:a+b 后缀:ab+ 中序:a + b - c 后缀:ab+c- 中序:a + b * c 后缀:abc*+
(
进行入栈操作
)
出栈直到(
中序表达式
转换成后续表达式
中序:8-(3+2*6)/5+2^2 后缀:8326*+5/-22^+
中序:2*9+3-2*(10-3)/14 后缀:29*3+2103-*14/-
中序:A+B*(C*D-E) 后缀:ABCD*E-*+
中序:a+b*c+(d*e+f)*g 后缀:abc*+de*f+g*+
中序:9+(3-1)*3+10/2 后缀:931-3*+102/+
共3个柱子,在一根柱子上,从下往上按照大小顺序摞着N片圆盘。把圆盘开始按大小顺序重新摆放在另一根柱子上
规定:在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
package hanoi;
/**
* @author 桐叔
* @email liangtong@itcast.cn
*/
public class TestHanoi {
private static int count = 0;
/**
*
* @param n 需要移动的盘子数
* @param x 第一个柱子 起始
* @param y 第二个柱子 过渡
* @param z 第三个柱子 最后
*/
public static void hanoi(int n, char x, char y , char z) {
if(n == 1) { //只有一个盘子
move(x, 1, z);
} else {
hanoi(n-1, x, z ,y); // n上面的盘子,从x柱子,通过z柱子,移动到y柱子
move(x, n, z); //n盘子,从x柱子,移动到z柱子
hanoi(n-1, y, x, z); // n上面的盘子目前在y柱子,从y柱子,通过x柱子,移动到z柱子。
}
}
/**
*
* @param x 第一个柱子
* @param n 需要移动的盘子号
* @param z 第三个柱子
*/
private static void move(char x, int n, char z) {
count++;
System.out.println("第"+count+"次移动"+n+"号盘子,从"+x+"柱子到"+z+"柱子");
}
public static void main(String[] args) {
hanoi(4,'x','y','z');
}
}
循环顺序队列
解决“假溢出”问题。
// 队列空 front == rear; // 队列满 (rear + 1) % maxSize == front; //余数操作 5 % 5 = 0; 2 % 5 = 2;
逻辑
上是一个循环,也就是队首和队尾连接。
public Class CircleQueue {
private Object[] queueElem; //物理数组
private int front; //队首
private int rear; //队尾
}
public void offer(Object x) {
if( (rear+1) % queueElem.length == front ) { // 1.判断,如果已经满了,抛异常
throw new RuntimeException('队列满了');
} else {
queueElme[ rear ] = x; // 2.没有满进行入队操作
rear = (rear + 1) % queueElem.length; // 3.队尾rear累加1,但最后时需要归零
}
}
public Object poll() {
if( front == rear ) { // 判断 空 返回null
return null;
}
Object data = queueElem[front]; // 如果不为空,获得队首front元素
front = (front + 1) % queueElem.length; // 队首+1,且需要归零
return data;
}
public class LinkQueue {
private Node front; //队首(出队/删除)
private Node rear; //队尾(入队/插入)
}
public void offer(Object x) {
Node p = new Node(x);
if(front == null) { //空
front = rear = p;
//front = p;
//rear = p;
} else { //非空
rear.next = p; //1.尾指针的指针域指向新结点
rear = p; //2.尾指针指向队尾
}
}
public Object poll() {
if(front != null) { //非空
Node p = front; //记录队首元素
front = front.next; //队首移动到下一个
if(p == rear) { //只有一个元素时,队首和队尾相同
rear = null; //队首已经是null,队尾也应该是null
}
return p.data; //返回之前队首元素的数据
} else { //空
return null;
}
}
关键字的值
进行排序的队列。
public void offer(PriorityData x) {
Node s = new Node(x); //构建新结点
// 如果空
if(front == null) { //空
front = rear = s;
} else { //非空
// 1) 移动:按照优先级进行移动,优先级大就需要继续移动
Node p = front; //用于记录前驱(之前的)
Node q = front; //用于记录下一个
while( q != null && (x.priority >= q.data.priority )) {
p = q; //记录前驱
q = p.next;
}
// 2) 插入
if(q==front) { // 2.1 队首
s.next = front; //新结点s指向队首front
front = s; //队首指针,指向队列的开始
} else if (q == null) { // 2.2 队尾
rear.next = s; //队尾指针域next,指向新结点
rear = s; //队尾指针,指向队尾
} else { // 2.3 中间
p.next = s;
s.next = q;
}
}
}
package recursion;
/**
* @author 桐叔
* @email liangtong@itcast.cn
*/
public class TestSum {
public static void main(String[] args) {
System.out.println(sum(10));
}
/**
* 求1-n的和
* @param n
* @return
*/
private static int sum(int n) {
if(n == 1) {
return 1;
}
return n + sum(n-1);
}
}
package recursion;
/** 测试阶乘:
* n! = 1 * 2 * 3 * 4 * .... * n
* @author 桐叔
* @email liangtong@itcast.cn
*/
public class TestFactorial {
public static void main(String[] args) {
System.out.println(factorial(4));
}
private static int factorial(int n) {
if(n == 1) {
return 1;
}
return n * factorial(n-1);
}
}
0、1、1、2、3、5、8、13、21、34 .... n
固定值
f(0) = 0
f(1) = 1
后面的每一项都是前两项的和
f(2) = f(0) + f(1)
f(n) = f(n-1) + f(n-2)
package recursion;
/**
* @author 桐叔
* @email liangtong@itcast.cn
*/
public class TestFibonacci {
public static void main(String[] args) {
// 斐波那契数列
for(int i = 0 ; i <= 10 ; i ++) {
System.out.print(fibonacci(i) + "、");
}
}
/**
* 计算斐波那契数列的第n项
* f(0) = 0
* f(1) = 1
* ...
* f(n) = f(n-1) + f(n-2)
* @param n
* @return
*/
private static int fibonacci(int n) {
if(n == 0) {
return 0;
}
if(n == 1) {
return 1;
}
return fibonacci(n-1) + fibonacci(n-2);
}
}