3.1 描述如何只用一个数组来实现三个栈。
解答
我们可以很容易地用一个数组来实现一个栈，压栈就往数组里插入值，栈顶指针加1； 出栈就直接将栈顶指针减1；取栈顶值就把栈顶指针指向的单元的值返回； 判断是否为空就直接看栈顶指针是否为-1。
如果要在一个数组里实现3个栈，可以将该数组分为3个部分。如果我们并不知道哪个栈将装 入更多的数据，就直接将这个数组平均分为3个部分，每个部分维护一个栈顶指针， 根据具体是对哪个栈进行操作，用栈顶指针去加上相应的偏移量即可。
C++实现代码：
#include<iostream>
#include<new>
using namespace std; class stack3
{
private:
int top[];//仅仅用来记录偏移量
int size;
int *buf;
public:
stack3(int size=)
{
buf=new int[*size];
this->size=size;
top[]=top[]=top[]=-;
}
~stack3()
{
delete []buf;
}
void push(int stackNum,int val)
{
top[stackNum]++;
int idx=top[stackNum]+stackNum*size;
buf[idx]=val;
}
void pop(int stackNum)
{
top[stackNum]--;
}
int gettop(int stackNum)
{
int idx=top[stackNum]+stackNum*size;
return buf[idx];
}
bool empty(int stackNum)
{
return top[stackNum]==-;
}
}; int main()
{
stack3 mystack;//stack3 mystack;
for(int i=; i<; ++i)
mystack.push(, i);
for(int i=; i<; ++i)
mystack.push(, i);
for(int i=; i<; ++i)
mystack.push(, i);
for(int i=; i<; ++i)
cout<<mystack.gettop(i)<<" ";
cout<<endl;
for(int i=; i<; ++i)
{
mystack.pop(i);
cout<<mystack.gettop(i)<<" ";
}
mystack.push(, );
mystack.push(, );
mystack.push(, );
for(int i=; i<; ++i)
cout<<mystack.gettop(i)<<" ";
return ;
}