数据结构的C/C++描述03.01:单调栈 木灵的炼金工作室

写在前边:读本文您至少得知道栈是什么,并用栈写过一点C++程序。

单调栈

单调栈是时刻保持栈内元素遵守某种单调顺序的栈数据结构。为了维持这种单调性质,当压入一个破坏了它单调性质的元素时,栈会弹出一部分元素使其重新遵守单调性质。比如,有一个整数类型的递增单调栈:1,2,3,5,9,10,15,25,现在压入一个整数7,单调栈会将25,15,10,9弹出,再将7压入,产生1,2,3,5,7的结果。

实现

template<class elementType>
class monotoneStack {
private:
    std::stack<elementType> data;
    bool (*compare)(elementType const &a, elementType const &b);
    bool static _compare(elementType const &a, elementType const &b) const { return a > b; };
    elementType bottom;
public:
    monotoneStack(bool (*cmp)(elementType const, elementType const) = _compare) : compare(cmp) {};

    elementType top() const { return data.top(); }
    elementType bottom() const;
    unsigned int size() const { return data.size(); }
    bool empty() const { return data.empty(); }
    void push(elementType val);
    void pop() { data.pop(); }
};

template<class elementType>
void monotoneStack<elementType>::push(elementType val) {
    while (size() && !compare(val, data.top()))
        data.pop();
    if (empty()) bottom = val;
    data.push(val);
}

template<class elementType>
elementType monotoneStack<elementType>::bottom() const {
    if (size()) return bottom;
    else throw("empty stack");
}

相似地,也存在着单调队列的数据结构,但我们一般会以优先队列(二叉堆)来实现。


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn