当前位置： 面试刷题>> 用栈模拟汉诺塔问题 (经典算法题500道)
### 题目描述补充
汉诺塔（Tower of Hanoi）是一个经典的递归问题，目的是将一系列不同大小的盘子从一个塔（我们称之为A）通过另一个塔（B）移动到第三个塔（C），在移动过程中需要遵循以下规则：
1. 每次只能移动一个盘子。
2. 在任何时候，每个塔上的盘子都必须保持大盘在下，小盘在上。
虽然汉诺塔问题通常通过递归算法来解决，但本题要求使用栈（Stack）这种数据结构来模拟整个过程。栈是一种后进先出（LIFO）的数据结构，这使得它非常适合用来模拟汉诺塔的移动过程，尽管这种方法的直观性可能不如递归方法。
### 示例代码
以下是使用PHP、Python和JavaScript编写的使用栈模拟汉诺塔问题的示例代码。
#### PHP 示例
```php
class Stack {
private $items = [];
public function push($item) {
$this->items[] = $item;
}
public function pop() {
return array_pop($this->items);
}
public function isEmpty() {
return empty($this->items);
}
}
function hanoi($n, $from, $to, $aux, $stacks) {
if ($n == 1) {
$stacks[$to]->push($stacks[$from]->pop());
echo "Move disk 1 from $from to $to\n";
return;
}
hanoi($n-1, $from, $aux, $to, $stacks);
$stacks[$to]->push($stacks[$from]->pop());
echo "Move disk $n from $from to $to\n";
hanoi($n-1, $aux, $to, $from, $stacks);
}
// 初始化栈
$stacks = [
'A' => new Stack(),
'B' => new Stack(),
'C' => new Stack()
];
// 填充源栈A
for ($i = $n; $i > 0; $i--) {
$stacks['A']->push($i);
}
// 执行汉诺塔操作
hanoi(3, 'A', 'C', 'B', $stacks);
```
**注意**：PHP示例中的栈用于表示三个塔，但真正的盘子移动是通过直接操作栈和打印消息来模拟的，没有实际显示栈的内容变化。
#### Python 示例
```python
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def is_empty(self):
return len(self.items) == 0
def hanoi(n, from_rod, to_rod, aux_rod, stacks):
if n == 1:
stacks[to_rod].push(stacks[from_rod].pop())
print(f"Move disk 1 from {from_rod} to {to_rod}")
return
hanoi(n-1, from_rod, aux_rod, to_rod, stacks)
stacks[to_rod].push(stacks[from_rod].pop())
print(f"Move disk {n} from {from_rod} to {to_rod}")
hanoi(n-1, aux_rod, to_rod, from_rod, stacks)
# 初始化栈
stacks = {'A': Stack(), 'B': Stack(), 'C': Stack()}
# 填充源栈A
for i in range(3, 0, -1):
stacks['A'].push(i)
# 执行汉诺塔操作
hanoi(3, 'A', 'C', 'B', stacks)
```
#### JavaScript 示例
```javascript
class Stack {
constructor() {
this.items = [];
}
push(item) {
this.items.push(item);
}
pop() {
return this.items.pop();
}
isEmpty() {
return this.items.length === 0;
}
}
function hanoi(n, from, to, aux, stacks) {
if (n === 1) {
stacks[to].push(stacks[from].pop());
console.log(`Move disk 1 from ${from} to ${to}`);
return;
}
hanoi(n - 1, from, aux, to, stacks);
stacks[to].push(stacks[from].pop());
console.log(`Move disk ${n} from ${from} to ${to}`);
hanoi(n - 1, aux, to, from, stacks);
}
// 初始化栈
const stacks = {
A: new Stack(),
B: new Stack(),
C: new Stack()
};
// 填充源栈A
for (let i = 3; i > 0; i--) {
stacks.A.push(i);
}
// 执行汉诺塔操作
hanoi(3, 'A', 'C', 'B', stacks);
```
码小课网站中有更多相关内容分享给大家学习，包括数据结构、算法设计等进阶知识，欢迎大家访问。