#include <cstdlib>
#include <iostream>
#include <assert.h>
using namespace std;
class mystack
{
public:
mystack(int _n)
{
n = _n;
arr = new int[_n];
memset(arr, 0, n);
size1 = -1;
size2 = _n;
}
void push1(int element)
{
if(size2 - size1 > 1)
{
size1++;
arr[size1] = element;
}
}
void pop1()
{
if(size1 >= 0)
{
arr[size1] = 0;
size1--;
}
}
int top1()
{
assert(size1 >= 0);
return arr[size1];
}
bool empty1()
{
return !(size1 >= 0);
}
/*第二个栈*/
void push2(int element)
{
if(size2 - size1 > 1)
{
size2--;
arr[size2] = element;
}
}
void pop2()
{
if(size2 <= n-1)
{
arr[size2] = 0;
size2++;
}
}
int top2()
{
assert(size2 <= n-1);
return (arr[size2]);
}
bool empty2()
{
return !(size2 < n);
}
~mystack()
{
delete []arr;
}
private:
int *arr;
int size1;
int size2;
int n;
};
int main(int argc, char *argv[])
{
mystack my(20);
for(int i=0; i<6; i++)
{
my.push1(i);
my.push2(20 - i);
}
while (!my.empty1())
{
cout<<my.top1()<<" ";
my.pop1();
}
cout<<endl;
while (!my.empty2())
{
cout<<my.top2()<<" ";
my.pop2();
}
cout<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}
算法思想:为了节省空间,叫两个栈共享一个数组,一个是从底部向上增长,一个是从上向下递减,当两个栈的栈顶相遇时,说明这个栈满了 |