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;
    }
}