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

前端之家收集整理的这篇文章主要介绍了【数据结构】 一个数组实现两个栈【面试】前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

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

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

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


wKiom1cTMZfzKERvAAAY6R1lJf4851.png


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

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

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

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


在这里,使用第一种方法实现:

#include<iostream>
usingnamespacestd;

template<classT>
classarrayWithTwoStack
{
public:
arrayWithTwoStack(intsize)
:top1(-1),top2(-1),_size(size)
{
_array=newT[size+1];
}

~arrayWithTwoStack()
{
if(_array)
{
delete[]_array;
}
}

public:
voidPush(intindex,Tdata)
{
if(_size%2==0)
{
if((top1>_size-2)||(top2>=_size-1))
{
cout<<"Stackisoverflow!"<<endl;
return;
}
}
else
{
if((top1>_size-1)||(top2>=_size-2))
{
cout<<"Stackisoverflow!"<<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;
}
}
}

TPop(intindex)
{
intret;
if(index==0)
{
if(top1<0)
{
return-1;
cout<<"Stackisunderflow!"<<endl;
}
else
{
ret=_array[top1];
top1-=2;
}
}
if(index==1)
{
if(top2<1)//top2从下标为1开始
{
return-1;
cout<<"Satckisunderflow!"<<endl;
}
else
{
ret=_array[top2];
top2-=2;
}
}
returnret;
}

Ttop(intindex)//返回栈顶元素
{
if(index==0&&top1>=0)
{
return_array[top1];
}

if(index==1&&top2>=1)
{
return_array[top2];
}

cout<<"NoTop!"<<endl;
exit(0);
}

boolisEmpty(intindex)
{
if(index==0&&top1<0)
returnfalse;
if(index==1&&top2<1)
returnfalse;

returntrue;
}

voidShow()
{
if(top1<0&&top2<1)
{
cout<<"Stackhasnodata!"<<endl;
return;
}
else
{
for(inti=0;i<_size;i++)
cout<<_array[i]<<"";
}
cout<<endl;
}

private:
Ttop1;
Ttop2;
int_size;
T*_array;

};


intmain()
{
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");
return0;
}

若有纰漏,欢迎指正。

本文出自 “Vs吕小布博客,请务必保留此出处http://www.jb51.cc/article/p-gdupegjj-ms.html

原文链接:https://www.f2er.com/datastructure/382488.html

猜你在找的数据结构相关文章