一個數組模拟兩個棧

#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;

}

算法思想：為了節省空間，叫兩個棧共享一個數組，一個是從底部向上增長，一個是從上向下遞減，當兩個棧的棧頂相遇時，說明這個棧滿了