【数据结构】 一个数组实现两个栈【面试】

以前，我们实现一个栈，轻轻松松，无需考虑太多因素，即可实现。

现在，要求在一个数组里实现两个栈，那么在数组里怎么实现栈呢？

无非就是下标索引，方法也不局限一种，例如：用奇数下标作为栈s1的结构，用偶数作为s2的结构；再者：一前一后的结构，栈s1从前往后，栈s2从后往前。

本人只想到了使用这两中方法实现，当然，这两种方法各有利弊。

第一种方法，倘若其中一个栈只入了一个元素，而另一个入了很多元素，那么会造成内存碎片，但是此方法有利于数组增容；

第二种方法，空间利用率很高，但是不有利于数组增容。

虽然各有利弊，但是实现的机制相同。

在这里，使用第一种方法实现：

#include?<iostream>
using?namespace?std;

template?<class?T>
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<int>?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;
}

（编辑：西双版纳站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!