目录
操作受限
的特殊线性表。
栈顶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
进出栈是最经典的卡特兰数
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;
}
}
算法1:
public Object pop(){
if(top == 0){
return null;
}else{
top--;
return statckElem[top];
}
}
算法2:
public boolean isEmpty(){
return top == 0;
}
public Object pop(){
if(isEmpty()){
return null;
}else{
return statckElem[--top];
}
}
public class LinkStack {
private Node top; //栈顶指针
}
public void push(Object x){
Node p = new Node(x);
p.next = top;
top = p;
}
需求:弹出栈顶元素,需要返回数据
public Object pop(){
if(top == null){
return null;
}else{
Node p = top;
top = top.next;
return p.data;
}
}
9992992347234947324732498327427342472987427427984724274 + 9990920943824283492834824820984028348204209384029293
中序表达式:日常生活中编写的都是中序表达式。
a + b - c
后缀表达式:把运算符写在后面的表达式,也称为逆波兰记法
中序: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;
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;
}
链队列:使用链式存储的队列,使用不带头结点head的单链表。
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.尾指针指向队尾
}
}
分析:空队列、一个元素、很多元素
一个元素:需要额外的处理队尾,将其设置成null
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;
}
}
关键字的值
进行排序的队列。
插入操作:数字小的优先级越高
数据对象:数据元素的值、结点的优先级
/*
{ elem: a, priority: 1}
*/
public class PriorityData {
public Object elem; //数据元素的值
public int priority; //结点的优先级
}
队列对象
public class PriorityQueue {
private Node front; //队首
private Node rear; //队尾
}
数据之间关系
node.next //指针域 node.data //数据域,存放的数据类型是 PriorityData
情况2:队尾插入 (q为null 或 p等于队尾rear)
情况3:剩余的中间
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;
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;
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;
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);
}
}