用一个数组实现一个栈&&元素出栈，入栈的合法性

用一个数组实现一个栈
采用如下图示方法：以两头向中间增长，push的时候将插入的数据压入到size1或size2的位置，size1++，size2–；pop的时候刚好相反，size1–，size2++；
取top的时候需要判断size1大于0，size2是否越界，小于_capacity
因为这里使用数组进行实现的，会牵扯到扩容得问题，这里在扩容的时候需要新开辟一块新的空间，将size1大小的数据拷贝到新空间的前面，将size2大小的数据拷贝到新空间的后面(注意size2的计算)，将原空间释放

代码实现：

//用一个数组实现两个栈
//解决的方案是从两头开始向中间增长，因为是数组所以特别注意的是容量是否满了
template<class T>
class Stack
{
public:
    Stack()
        :_arr(new int [2])
        , size1(0)
        , size2(1)
        , _capacity(2)
    {}

    ~Stack()
    {
        if (_arr != NULL)
        {
            delete[] _arr;
            _arr = NULL;
            size1 = 0;
            size2 = 0;
            _capacity = 0;
        }
    }

    void Push1(const T& x)
    {
        CheckCapacity();
        _arr[size1] = x;
        size1++;
    }

    void Push2(const T& x)
    {
        CheckCapacity();
        _arr[size2] = x;
        size2--;
    }

    void Pop1()
    {
        if (size1 > 0)
        {
            size1--;
        }
    }

    void Pop2()
    {
        if (size2 != _capacity - 1)
        {
            size2++;
        }
    }

    T& Top1()
    {
        if (size1 > 0)
        {
            return _arr[size1];
        }
    }

    T& Top2()
    {
        if (size2 > 0)
        {
            return _arr[size2];
        }
    }
private:
    void CheckCapacity()
    {
        if (size1 + size2 <= _capacity)
        {
            int newCapacity = _capacity + 10;

            T* tmp = new T[newCapacity];

            int k = newCapacity - 1;
            //将前后两个数据段进行拷贝
            for (int i = 0; i < size1; ++i)
            {
                tmp[i] = _arr[i];
            }
            for (int i = _capacity - 1; i>_capacity - size2; --i)
            {
                tmp[k] = _arr[i];
                k--;
            }

            delete[] _arr;
            size2 = newCapacity - (_capacity - size2);
            _capacity = newCapacity;
            _arr = tmp;
        }

    }

    T* _arr;
    int size1;
    int size2;
    int _capacity;
};

元素出栈,入栈的合法性判断

代码实现：

//元素出栈，入栈顺序的合法性
template<class T>
class Check
{
public:
    bool Check_Output(T* input, T* output, size_t len1, size_t len2)
    {
        assert(input);
        assert(output);
        if (len1 != len2)
        {
            return false;
        }

        stack<T> s;
        int j = 0;
        for (int i = 0; i < len1; ++i)
        {
            s.push(input[i]);

            while (s.size()>0 && s.top() == output[j])
            {
                s.pop();
                j++;
            }
        }
        return s.size() > 0 ? false : true;
    }
};
int main()
{
    int arr1[] = { 1, 2, 3, 4, 5 };
    size_t len1 = sizeof(arr1) / sizeof(arr1[0]);
    int arr2[] = { 4, 5, 2, 2, 1 };
    size_t len2 = sizeof(arr2) / sizeof(arr2[0]);
    Check<int> c;
    cout << c.Check_Output(arr1, arr2, len1, len2) << endl;
    system("pause");
}