栈-数组描述（C++）

定义

使用数组描述栈时，通常包含以下几个基本要素：

1. 栈顶指针（Top Pointer）：用于指示栈顶元素的位置。栈顶指针的初始值通常设置为-1，表示栈为空。
2. 栈底（Bottom）：数组的起始位置，通常固定。
3. 栈容量（Capacity）：栈可以容纳的最大元素个数，由数组的大小决定。

栈的基本操作包括：

• 压栈（Push）：将新元素添加到栈顶。
• 弹栈（Pop）：移除栈顶元素。
• 查看栈顶元素：获取栈顶元素但不移除它。
• 检查栈是否为空：判断栈顶指针是否为-1。

抽象类stack

template<typename T>
class stack
{
public:
    virtual   ~stack(){}
    virtual bool empty() const = 0;
    virtual int size() const = 0;
    virtual T& top() const = 0;
    virtual void push(const T& theElement) const = 0;
    virtual void pop() = 0;
};

派生类arrayStack

template <typename T>
class arrayStack : public stack<T>
{
public:
    arrayStack(int initialCapacity = 10);
    ~arrayStack();
    bool empty() const;
    int size() const;
    T &top() const;
    void push(const T &theElement);
    void pop();

private:
    int stackTop;
    int arrayLength;
    T* stack;
};

template<typename T>
arrayStack<T>::arrayStack(int initialCapacity)
{
    assert(initialCapacity > 0);
    arrayLength = initialCapacity;
    stack = new T[arrayLength];
    stackTop = -1;
}

template<typename T>
arrayStack<T>::~arrayStack()
{
    delete [] stack;
}

template<typename T>
bool arrayStack<T>::empty() const
{
    return stackTop == -1;
}

template<typename T>
int arrayStack<T>::size() const
{
    return stackTop + 1;
}

template<typename T>
T &arrayStack<T>::top() const
{
    if(stackTop == -1)
    {
        assert(stackTop > -1);
    }

    return stack[stackTop];

}

template<typename T>
void arrayStack<T>::push(const T &theElement)
{
    if(stackTop == arrayLength -1)
    {
        changeLength1D(stack,arrayLength,arrayLength*2);
        arrayLength *= 2;
    }

    stack[++stackTop] = theElement;
}

template<typename T>
void arrayStack<T>::pop()
{
    if(stackTop == -1)
    {
        assert(stackTop > -1);
    }

    stack[stackTop--].~T();
}