时间戳

首页 > 技术文章 > Stacks原理剖析

Stacks原理剖析

jinxiang1224 2016-07-09 22:49 原文

stack概述

stack是个“后进先出的”数据结构，STL中由class stack<>实作出这样的数据结构，我们可以使用push()将任意数量的元素置入stack中，也可以使用pop()将元素依其次序的反序从容器中移除(即后进先出， LIFO)，如图1所示。

图1 Stack的接口

在头文件<stack>中， class stack定义如下：

namesapce std
{
	template<class T, class Container = deque<T>>
	class stack;
}

第一个参数代表元素型别，第二个参数代表stack内部存放元素所用的实际容量，默认采用deque。因为deque在增加元素数量是不存在内存的重新分配，性能比vector高一些。

核心接口

实际上stack是个容器配接器，stack的核心接口就是三个成员函数：push(),top(), pop()，stack接口函数调用都是转化为内部容器成员函数的对应调用，如图2所示。

       图2 stack 内部接口

push()

  • 将一个元素置入stack内，成为最顶端元素
  • 函数无返回值
top()

  • 返回stack的最后被插入的元素
  • 调用者保证stack不空，否则会导致未定义行为
pop()

  • 移除stack最后被插入的元素
  • 调用者保证stack不空，否则可能导致未定义行为
  • 函数无返回值，若想处理被移除的元素，要先调用top函数

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

stack 运用实例

/****************************************************************
*函数名称：StackTest
*功    能：stack 使用说明
*作    者：Jin
*日    期：2016年7月1日
****************************************************************/
void StackTest()
{
    stack<int> st;
    //push three elements into the stack
    st.push(1);
    st.push(2);
    st.push(3);

    //pop and print two elements from the stacks
    cout << st.top() << ' ';
    st.pop();
    cout << st.top() << ' ';
    st.pop();
    
    //modify top element
    st.top() = 77;

    //push two new elements
    st.push(4);
    st.push(5);
    
    //pop one element without processing it
    st.pop();

    //pop and print remaining elements
    while (!st.empty())
    {
        cout << st.top() << ' ';
        st.pop();
    }
    
    cout << endl;
    //output: 3 2 4 77
}


自定义的Stack Class


标准的stack<> class  将运行速度置于方便性和安全性上，但使用上却不方便，若操作标准的stack，并且stack中无元素时会导致程序奔溃，出现程序未定义行为。我们可自己编写一个stack class，它可以有以下优势：

1.pop()会返回下一个元素

2.如果stack为空，pop()和top()会抛出异常。

3.可自行删增成员函数，简化操作方法

user_stack源码

它在.h文件中声明和实现，引用user_stack时，需要includ“user_stack.h”文件，其源码如下：

#ifndef  _USER_STACKH_
#define  _USER_STACKH_
#include <deque>
#include <exception>

template <class T>
class user_stack
{
public:
    class ReadEmptyStack: public std::exception
    {
    public:
        virtual const char * what() const throw()
        {
            return "read empty stack";
        }
    };

    //number of element
    typename std::deque<T>::size_type size() const
    {
        return c.size();   
    }

    //is stack empty
    bool empty() const
    {
        return c.empty();
    }

    //push element into stack
    void push(const T &elem)
    {
        c.push_back(elem);
    }

    //pop element out of stack and return is value
    T pop()
    {
        if (c.empty())
        {
            throw ReadEmptyStack();
        }

        T elem(c.back());

        c.pop_back();
        return elem;
    }

    //return top value
    T& top()
    {
        if (c.empty())
        {
            throw ReadEmptyStack();
        }

        return c.back();
    }
protected:
    std::deque<T> c;
};

#endif /*_USER_STACKH_*/

user_stack应用

/****************************************************************
*函数名称：UserStackTest
*功    能：user_stack模板使用实例
*作    者：Jin
*日    期：2016年7月9日
****************************************************************/
void UserStackTest()
{
    try
    {
        user_stack<int> UsersStack;

        //push three elements into the stack
        UsersStack.push(1);
        UsersStack.push(2);
        UsersStack.push(3);

        //pop and print two elements from the stack
        cout << UsersStack.pop() << ' ';
        cout << UsersStack.pop() << ' ';

        //modify top element
        UsersStack.top() = 77;

        //push two new elements
        UsersStack.push(4);
        UsersStack.push(5);

        //pop one element without processing it
        UsersStack.pop();

        //pop and print three elements

        cout << UsersStack.pop() << ' ';
        cout << UsersStack.pop() << endl;
        cout << UsersStack.pop() << endl;

    }
    catch (const exception& e)
    {
        cerr << "Exception : " << e.what() << endl;
    }

    //output：
    // 3 2 3 77
    // Exception : read empty stack
}


推荐阅读