以前，我们实现一个栈，轻轻松松，无需考虑太多因素，即可实现。
创新互联公司-专业网站定制、快速模板网站建设、高性价比高阳网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式高阳网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖高阳地区。费用合理售后完善，10年实体公司更值得信赖。
现在，要求在一个数组里实现两个栈，那么在数组里怎么实现栈呢？
无非就是下标索引，方法也不局限一种，例如：用奇数下标作为栈s1的结构，用偶数作为s2的结构；再者：一前一后的结构，栈s1从前往后，栈s2从后往前。
本人只想到了使用这两中方法实现，当然，这两种方法各有利弊。
第一种方法，倘若其中一个栈只入了一个元素，而另一个入了很多元素，那么会造成内存碎片，但是此方法有利于数组增容；
第二种方法，空间利用率很高，但是不有利于数组增容。
虽然各有利弊，但是实现的机制相同。
在这里，使用第一种方法实现：
#include
using namespace std;
template
class arrayWithTwoStack
{
public:
arrayWithTwoStack(int size)
: top1(-1)
, top2(-1)
, _size(size)
{
_array = new T[size + 1];
}
~arrayWithTwoStack()
{
if (_array)
{
delete[] _array;
}
}
public:
void Push(int index, T data)
{
if (_size % 2 == 0)
{
if ((top1 > _size - 2) || (top2 >= _size - 1))
{
cout << "Stack is overflow!" << endl;
return;
}
}
else
{
if ((top1 > _size - 1) || (top2 >= _size - 2))
{
cout << "Stack is overflow!" << endl;
return;
}
}
0是一号栈， 1是二号栈
if (index == 0)
{
if (top1 == -1)
{
top1 = 0;
_array[top1] = data;
}
else
{
top1 += 2;
_array[top1] = data;
}
}
if (index == 1)
{
if (top2 == -1)
{
top2 = 1;
_array[top2] = data;
}
else
{
top2 += 2;
_array[top2] = data;
}
}
}
T Pop(int index)
{
int ret;
if (index == 0)
{
if (top1 < 0)
{
return -1;
cout << "Stack is underflow!" << endl;
}
else
{
ret = _array[top1];
top1 -= 2;
}
}
if (index == 1)
{
if (top2 < 1) // top2从下标为1开始
{
return -1;
cout << "Satck is underflow!" << endl;
}
else
{
ret = _array[top2];
top2 -= 2;
}
}
return ret;
}
T top(int index) // 返回栈顶元素
{
if (index == 0 && top1 >= 0)
{
return _array[top1];
}
if (index == 1 && top2 >= 1)
{
return _array[top2];
}
cout << "No Top!" << endl;
exit(0);
}
bool isEmpty(int index)
{
if (index == 0 && top1 < 0)
return false;
if (index == 1 && top2 < 1)
return false;
return true;
}
void Show()
{
if (top1 < 0 && top2 < 1)
{
cout << "Stack has no data!" << endl;
return;
}
else
{
for (int i = 0; i < _size; i++)
cout << _array[i] << " ";
}
cout << endl;
}
private:
T top1;
T top2;
int _size;
T* _array;
};
int main()
{
arrayWithTwoStack s(10);
s.Push(0, 0);
s.Push(0, 2);
s.Push(0, 4);
s.Push(1, 1);
s.Push(1, 3);
s.Push(1, 5);
s.Push(1, 7);
s.Push(0, 6);
s.Push(0, 8);
s.Push(1, 9);
s.Push(0, 10);
s.Show();
cout << s.Pop(0) << " ";
cout << s.Pop(0) << " ";
cout << s.Pop(0) << " ";
cout << s.Pop(0) << endl;
cout << s.Pop(1) << " ";
cout << s.Pop(1) << " ";
cout << s.Pop(1) << " ";
cout << s.Pop(1) << endl;
cout << s.top(0) << endl;
cout << s.top(1) << endl;
s.Pop(0);
cout << (s.isEmpty(0) ? "Yes" : "No") << endl;
cout << (s.isEmpty(1) ? "Yes" : "No") << endl;
system("pause");
return 0;
}
若有纰漏，欢迎指正。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
本文标题：【数据结构】一个数组实现两个栈【面试】-创新互联
标题URL：
http://bjjierui.cn/article/coepio.html
