STL栈实现及书本对比

data_structure

返回目录

栈是一种只允许在一端进行插入与移除的数据结构。

一、课本分析

书本上的栈，主要分为两种实现

• 顺序栈
• 链栈

顺序栈需要事先指定元素，空间固定。
链栈随用随申请，一般不会出现空间问题。

栈实现比较简便，功能明确，

• top() 获取栈顶元素
• push(T x) 向栈中压入元素
• pop() 弹出栈顶元素
• size() 返回元素个数
• empty() 判断栈是否为空

具体实现可以参见：顺序栈以及双栈的设计与测试

二、STL栈

文章内容参考：STL系列之二 stack栈

下面，贴出在VS中，stack的定义

template<class _Ty, class _Container = deque<_Ty> >
class stack
{   // LIFO queue implemented with a container
public:
    typedef _Container container_type;
    typedef typename _Container::value_type value_type;
    typedef typename _Container::size_type size_type;
    typedef typename _Container::reference reference;
    typedef typename _Container::const_reference const_reference;
    stack() : c()
    {   // construct with empty container
    }
    explicit stack(const _Container& _Cont) : c(_Cont)
    {   // construct by copying specified container
    }
    bool empty() const
    {   // test if stack is empty
        return (c.empty());
    }
    size_type size() const
    {   // test length of stack
        return (c.size());
    }
    reference top()
    {   // return last element of mutable stack
        return (c.back());
    }
    const_reference top() const
    {   // return last element of nonmutable stack
        return (c.back());
    }
    void push(const value_type& _Val)
    {   // insert element at end
        c.push_back(_Val);
    }
    void pop()
    {   // erase last element
        c.pop_back();
    }
    const _Container& _Get_container() const
    {   // get reference to container
        return (c);
    }
protected:
    _Container c;   // the underlying container
};

不难发现，栈并没有提供自身的函数，而是封装了其他的数据结构，提供了对外的接口函数。

在c++面向对象实用教程一书中，第275页，讲述了stack和queue本身都不是独立的容器，默认条件下，是用的deque的容器来构造的。

在C++ Primer中第九章详细介绍了容器类型，deque双向队列是一种双向开口的连续线性空间，可以高效的在头尾两端插入和删除元素。

相比之下，STL栈并没有实现判满操作，因为，其使用容器类，不存在空间分配问题。同时，由于其余功能均采用容器，提供接口访问。在头部插入和删除的效率很高。使用时，仅需要包含其头文件即可。