用栈与线性表实现汉诺塔

汉诺塔问题是经典的递归问题，可以用栈和线性表来实现。

我们可以用一个栈来表示三个塔，另外一个栈用于存储要移动的盘子，用一个变量记录当前要移动的盘子编号和目标塔的编号。

具体实现步骤如下：

1. 初始化三个塔，将所有盘子都放在第一座塔上
2. 如果还有盘子需要移动，则执行以下步骤：
1）将当前要移动的盘子从原塔上取下来，放入待移动栈中
2）查看目标塔顶部的盘子编号，如果目标塔为空，或者当前盘子编号小于目标塔顶部盘子编号，则将盘子从待移动栈中取出来，放到目标塔上，并更新当前位置和目标位置
3）否则，将目标塔顶部的盘子取下来，放入待移动栈中，并更新当前位置和目标位置
4）重复执行以上步骤，直到所有盘子都移动到目标塔上

具体的代码实现可以参考如下：

#include <iostream>
#include <stack>

using namespace std;

void move(int& from, int& to, stack<int>& fromStack, stack<int>& toStack) {
    int num = fromStack.top();
    fromStack.pop();
    toStack.push(num);
    from = num;
    to = !from && !to ? 2 : from ^ to ^ 1;
}

void hanoi(int n) {
    stack<int> s[3];
    int from = 0, to = 0;
    for (int i = n; i > 0; --i) s.push(i);
    while (s.size() != n) {
        if (s[from].empty() || (!s[to].empty() && s[from].top() > s[to].top())) {
            move(to, from, s[to], s[from]);
        }
        else {
            move(from, to, s[from], s[to]);
        }
    }
}

int main() {
    hanoi(3);
    return 0;
}