1.栈
First In Last Out，顺序栈和链栈，六种方法，声明使用方式。
1.1 概论
-
栈，是一个先进先出的一个数据结构。如图：
1.2 顺序栈和链栈
- 顺序栈就是一般的栈。
-
链栈就是使用链表将栈存储起来的由上一元素的节点指向下一元素。 如图所示：
1.3 六种基本方法
- 构造空栈：初始化一个栈。 InitStack(S)
- 判断空：判断是否为空。StackEmpty(S)
- 判断满：判断是否满。StackFull(S)
- 入栈：将x放入栈中。Push(S,x)
- 出栈：栈顶元素出栈。Pop(S)
- 取栈：取栈顶元素。StackTop(S)
1.4 声明使用方式
1.4.1 栈
- c++
#include<stack>
stack<int> stk;
s.empty()如果栈为空返回true，否则返回false
s.size()返回栈中元素的个数
s.pop()删除栈顶元素但不返回其值
s.top()返回栈顶的元素，但不删除该元素
s.push()在栈顶压入新元素
- java
importjava.util.Stack;
Stack stack = new Stack(); // 创建堆栈对象
stack.push(数据) 在栈顶压入新元素
stack.pop() 删除栈顶元素并且返回其值
stack.empty() 如果栈为空返回true，否则返回false
stack.peek() 返回栈顶的元素，但不删除该元素
stack.search() 查找stack里的元素，返回元素到栈顶的距离。
2.汉诺塔问题
将圆盘移动到另外一个柱子上
在小圆盘上不能放大圆盘
在三根柱子之间一次只能移动一个圆盘。
解法思路：要移动1个盘子，直接从A移动到C
-
要移动2个盘子，
- 将盘1从A移动到B。
- 将盘2从A移动到C。
- 将盘1从B移动到C。
-
要移动3个盘子，
- 将盘1从A移动到C，再将盘2从A移动到B，将盘1从C移动到B。
- 将盘3从A移动到C。
- 将盘1从B移动到A，将盘2从B移动到C，将盘1从A移动到C。
-
要移动n个盘子
- 将盘1~n-1从A上移动到B上。
- 将盘n移动到C上。
- 将盘1~n-1从B上移动到C上。
-
过程如图：
-
递归解法：
- 因为在将盘1~n-1从A移动到B的过程中，从A不断的移动到B，C，这其中是交替进行的。所以，第一个递归就用hanoi(n,A,C,B)的交替传入C,B，然后进行移动。
- 中间的必须是从A到C。
- 第二个递归同样，在将盘1~n-1从B移动到C的过程中，也是交替进行的，所以第二个递归就使用hanoi(n,B,A,C)的交替传入B,A，然后进行移动。
public class HanoiRecursion {
public static void main(String[] args){
hanoi(4,'A','B','C');
}
public static void hanoi(int n,char A,char B,char C){
if(n==1){
move(A,C);
}
else{
hanoi(n-1,A,C,B);
move(A,C);
hanoi(n-1,B,A,C);
}
}
public static void move(char A,char C){
System.out.println(A+"->"+C);
}
}
- 栈解法：
- 将原始问题先入栈。
-
每次将栈顶元素出栈，然后解决栈顶元素，拆分为子问题或结果。知道栈内没有元素。如图：
public class HanoiStack {
public static void main(String[] args) {
Stack hanoi = new Stack();
hanoi.push(new Problem(4, 'A', 'B', 'C'));
Problem myProblem = null;
while (!hanoi.isEmpty() && (myProblem = (Problem) hanoi.pop()) != null) {
if (myProblem.n == 1) {
System.out.println(myProblem.A+"->"+myProblem.C);
} else {
hanoi.push(new Problem(myProblem.n-1, myProblem.B, myProblem.A, myProblem.C));
hanoi.push(new Problem(1, myProblem.A, myProblem.B, myProblem.C));
hanoi.push(new Problem(myProblem.n-1, myProblem.A, myProblem.C, myProblem.B));
}
}
}
}
class Problem {
int n;
char A, B, C;
public Problem(int n, char A, char B, char C) {
this.n = n;
this.A = A;
this.B = B;
this.C = C;
}
}
