分享程序员开发的那些事...
更新时间：2022-08-22 08:46:25
3.3 栈就像叠盘子，当盘子叠得太高时，就会倾斜倒下。因此，在真实的世界中，当一叠盘子 (栈)超过了一定的高度时，我们就会另起一堆，再从头叠起。实现数据结构SetOfStacks 来模拟这种情况。SetOfStacks由几个栈组成，当前一栈超出容量时，需要创建一个新的栈 来存放数据。SetOfStacks.push()和SetOfStacks.pop()的行为应当和只有一个栈时 表现的一样。
进一步地，
实现函数popAt(int index)在指定的子栈上进行pop操作。
实现第一步：
#include<iostream> #include<new> using namespace std; //myStack表示一个栈 class myStack { private: int *buf; int capacity; int cur; public: myStack(int size=10) { buf=new int[size]; capacity=size; cur=-1; } ~myStack() { delete[] buf; } void push(int x) { buf[++cur]=x; } void pop() { cur--; } int top() { return buf[cur]; } bool empty() { return cur==-1; } bool full() { return cur==capacity-1; } }; //一个栈组成的数组 class SetOfStacks { private: myStack *st; int cur; int capacity; public: SetOfStacks(int cap=10) { st=new myStack[cap]; capacity=cap; cur=0; } ~SetOfStacks() { delete[] st; } void push(int x) { if(st[cur].full()) cur++; if(cur>capacity-1) return; st[cur].push(x); } void pop() { if(st[cur].empty()) cur--; if(cur<0) return; st[cur].pop(); } int top() { if(st[cur].empty()) cur--; if(cur<0) return 0; else return st[cur].top(); } bool empty() { return cur==0&&st[cur].empty(); } bool full() { return cur==capacity-1&&st[cur].full(); } }; int main() { SetOfStacks ss1; for(int i=0; i<3*10+1; ++i) { ss1.push(i); } while(!ss1.empty()) { cout<<ss1.top()<<endl; ss1.pop(); } return 0; }
当加入popAt函数，情况就变得复杂了。因为这时候的数据分布可能出现中间的某些子栈使 用popAt把它们清空了，而后面的子栈却有数据。为了实现方便，我们不考虑因为popAt 带来的空间浪费。即如果我用popAt把中间某些子栈清空了，并不把后面子栈的数据往前移 动。这样一来，cur指向操作的“最后”一个栈，它后面的子栈一定都是空的， 而它本身及前面的子栈由于popAt函数的缘故都有可能是空的。如果没有popAt函数， cur前面的子栈一定都是满的(见上面的例子)。这样一来，push仍然只需要判断一次当前子 栈是否为满。但是，pop函数则要从cur向前一直寻找，直到找到一个非空的子栈， 才能进行pop操作。同理，popAt，top，empty也是一样的。
#include<iostream> #include<new> using namespace std; //myStack表示一个栈 class myStack { private: int *buf; int capacity; int cur; public: myStack(int size=10) { buf=new int[size]; capacity=size; cur=-1; } ~myStack() { delete[] buf; } void push(int x) { buf[++cur]=x; } void pop() { cur--; } int top() { return buf[cur]; } bool empty() { return cur==-1; } bool full() { return cur==capacity-1; } }; //一个栈组成的数组 class SetOfStacks { private: myStack *st; int cur; int capacity; public: SetOfStacks(int cap=10) { st=new myStack[cap]; capacity=cap; cur=0; } ~SetOfStacks() { delete[] st; } void push(int x) { if(st[cur].full()) cur++; if(cur>capacity-1) return; st[cur].push(x); } void pop() { while(st[cur].empty()) cur--; if(cur<0) return; st[cur].pop(); } int top() { while(st[cur].empty()) cur--; if(cur<0) return 0; else return st[cur].top(); } bool empty() { while(cur>=0&&st[cur].empty()) cur--; return cur==-1; } bool full() { return cur==capacity-1&&st[cur].full(); } void popAt(int idx) { while(st[idx].empty()) --idx; st[idx].pop(); } }; int main() { SetOfStacks ss1; for(int i=0; i<3*10+1; ++i) { ss1.push(i); } for(int i=0; i<10; ++i) { ss1.popAt(0); //ss1.popAt(1); ss1.popAt(2); } while(!ss1.empty()) { cout<<ss1.top()<<endl; ss1.pop(); } return 0; }