implement 3 stack in an array - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

implement 3 stack in an array

implement 3 stack in an array# JobHunting - 待字闺中

c*n2013-05-19 07:05

1 楼

这个是career up 4th 上的一道题，我怎么觉得它上面的solution有问题？
哪个大侠给贴个正确的解？

s*s2013-05-19 07:05

2 楼

I think this link gives correct solution:
http://stackoverflow.com/questions/4770627/how-to-implement-3-s

b*72013-05-19 07:05

3 楼

注意左移右移就行了
第一个栈[0...capacity0 - 1)
第二、三个栈[capacity0,...,N)分别一个从头开始++，一个从尾开始--
当第一个栈满而第二、三个栈不满时，做右移操作
反过来，但第二、三个栈满，而第一个栈伟满时，做左移操作
template
class TripleStack{
public:
TripleStack()
{
head0 = 0;
head1 = capacity0 = N/3;
head2 = N-1;
}
void push0(const T & e)
{
if(!isSubStackFull(0))
arr[head0++] = e;
else if(!isSubStackFull(1))
{
shiftRight();
arr[head0++] = e;
}
else
throw runtime_error("stack overflow");
}
void push1(const T & e)
{
if(!isSubStackFull(1))
{
arr[head1++] = e;
}
else if(!isSubStackFull(0))
{
shiftLeft();
arr[head1++] = e;
}
else
throw runtime_error("stack overflow");
}
void push2(const T & e)
{
if(!isSubStackFull(2))
{
arr[head2--] = e;
}
else if(!isSubStackFull(0))
{
shiftLeft();
arr[head2--] = e;
}
else
throw runtime_error("stack overflow");
}
void pop0()
{
if(head0 == 0)
throw runtime_error("stack0 empty");
head0--;
}
void pop1()
{
if(head1 == capacity0)
throw runtime_error("stack1 empty");
head1--;
}
void pop2()
{
if(head2 == N-1)
throw runtime_error("stack2 empty");
head2++;
}
...
private:
void shiftLeft()
{
assert(!isSubStackFull(0));
//[capacity0,head1)--->[capacity0-1,head1-1)
for(int i = capacity0; i < head1; i++)
arr[i-1] = arr[i];
capacity0--;
head1--;
}
void shiftRight()
{
assert(!isSubStackFull(1));
//[capacity0,head1) --->[capacity0+1,head1+1)
for(int i = head1-1; i >= capacity0; i--)
arr[i+1] = arr[i];
capacity0++;
head1++;
}
bool isSubStackFull(int i) const//i = 0,1,2
{
assert(i>=0 && i<=2);
if(i==0)
return head0 == capacity0;
else
return head1 > head2;
}
private:
T arr[N];
int head0;//[0,head0)
int head1;//[capacity0,head1)
int head2;//(head2,N)
int capacity0;
};