堆栈知识详解(简单易懂).ppt

问题抽象 3个塔，n个碟子 初始：所有碟子放在1号塔，大的在底下，小的在上面 任务：把碟子移动到2号塔，顺序不变， 可用3号塔辅助 限制 每次只能移动一个碟子 总是大碟子在下，小的在上 递归解法 移动碟子的方法：move(n, t1, t2, t3)——将n个碟子从t1移到t2，t3辅助 可分解为3个步骤 将n-1个碟子从t1移到t3：move(n-1, t1, t3, t2) 将最大的碟子从t1移到t2 将n-1个碟子从t3移到t2：move(n-1, t3, t2, t1) 递归规则 基本情况 汉诺塔递归程序 void TowersOfHanoi(int n, int x, int y, int z) {// Move the top n disks from tower x to tower y. // Use tower z for intermediate storage. if (n 0) { TowersOfHanoi(n-1, x, z, y); cout Move top disk from tower x to top of tower y endl; TowersOfHanoi(n-1, z, y, x);} } ?moves(n)=2n-1——最少次数，Θ(2n) 汉诺塔的栈实现 #include iostream.h #include stack.h“ class Hanoi { friend void TowersOfHanoi(int); public: void TowersOfHanoi(int n, int x, int y, int z); private: Stackint *S[4]; // array of pointers to stacks }; 汉诺塔的栈实现 void Hanoi::TowersOfHanoi(int n, int x, int y, int z) { int d; // disk number if (n 0) { TowersOfHanoi(n-1, x, z, y); S[x]-Pop(d); // remove a disk from x S[y]-Push(d); // put this disk on tower y cout Move disk d from tower x to tower y endl; TowersOfHanoi(n-1, z, y, x);} } 汉诺塔栈实现 void TowersOfHanoi(int n) {// Preprocessor for Hanoi::TowersOfHanoi. Hanoi X; X.S[1] = new Stackint (n); X.S[2] = new Stackint (n); X.S[3] = new Stackint (n); for (int d = n; d 0; d--) // initialize X.S[1]-Pop(d); // add disk d to tower 1 X.TowersOfHanoi(n, 1, 2, 3); } 汉诺塔栈实现 void main(void) { cout Moves for a three disk problem are endl; TowersOfHanoi(3); } 火车车厢重排问题 货运列车，n节车厢，编号1~n 经过车站n～车站1，每站卸掉同号车厢 在始发站重新排列车厢，使得车厢按编号排列——每站卸掉最后一节车厢即可 转轨站——一个入轨、一个出轨、k个缓冲铁轨?完成重排 允许三种操作 入轨?缓冲轨 缓冲轨?出轨 入轨?出轨 图示 列车行进方向 H1.自定义的Stack类 templateclass T class Stack { public: Stack(int MaxStackSize = 10); ~Stack() {delete [] stack;} bool IsEmpty() const {return top == -1;} bool IsFull() const {return top == MaxTop;} T Top() const; StackT Push(const T x); Stac