学习栈的原理 熟悉链表的构建与使用,利用链表实现栈 利用栈求解汉诺塔问题 问题描述 汉诺塔问题: 现有三个塔座,在塔1上叠有64个碟子,所有碟子按从大到小的次序从塔底堆放至塔顶。在塔1旁边还有另外两个塔座(塔2和塔3)。 要求每次移动一个碟子,将塔1上的64个碟子借助塔3全部移到塔2上,且在任何时候都不能把一个碟子放在比它小的碟子上。 实验要求: 1.由于从每个塔上移走碟子是按照LIFO的方法进行的,因此可以把每个塔表示成一个堆栈。 2.三座塔在任何时候都总共拥有n个碟子,因此使用链表形式的堆栈总共只需要申请n个元素所需要的空间,但是使用公式化描述的堆栈时,塔1和塔2的容量都必须是n,而塔3的容量必须是n-1,故总共需要3n-1的空间。 3.本次实验要求使用链表形式的栈。 4.链表的每个节点存储数据信息和指向下一个节点的指针 5.栈中保存每次移动后的状态