全部博文(695)
分类: C/C++
2013-12-22 13:41:54
Stack不允许遍历,只有一个出口,只允许对最顶端的元素进行操作。
SGI STL默认以deque作为stack的底层结构。
为什么要使用deque作为stack的底层结构呢?因为deque可以很容易的封住其中某个方向的接口,而且deque便于扩容,底层结合了list和vector,比起单一的使用list或者vector来实现stack更加方便高效。
由于stack是依赖底层容器完成其功能的,所以这种“修改某个物件的接口,形成另一种新的接口”的,叫做adapter。
Template
Class stack
{
Friend bool operator == __STL_NULL_TMPL_ARGS (const stack&,const stack&);
Friend bool operator< __STL_NULL_TMPL_ARGS(const stack&, const stack&);
Public:
//取Sequence底层容器来定义,不需要自己再重新定义这些类型信息
Typedef typename Sequence::value_type value_type;
Typedef typename Sequence::size_type size_type;
Typedef typename Sequence::reference reference;
Typedef typename Sequence::const_reference const_reference;
//deque中的定义是这样的,利用容器模板类的类型信息定义
//
//Typedef T value_type;
//Typedef Ptr pointer;
//Typedef Ref reference;
//Typedef size_t size_type;
//Typedef ptrdiff_t difference_type;
Protected:
Sequence c; // 底层使用deque来实现数据分配和操作等
Public:
Bool empty() const {return c.empty();}
Size_type size() const {return c.size();}
Reference top(){ return c.back();} //只暴露和top有关的操作
Const_reference top() const {return c.back();}
Void push( const value_type& x) { c.push_back(x);}
Void pop(){c.pop_back();}
};
Template
Bool operator == (const stack
{
Return x.c == y.c;
}
Template
Bool operator<(const stack
{
Return x.c
}
47 因为stack所有元素都只能在顶部出入,所以不需要遍历,所以不需要迭代器
48 使用list作为stack的底层容器【这个可以作为参考比较!】
Stack
默认情况下,使用sequence=deque
,作为stack的顶层容器 如果有容器也支持stack的基本操作的具体实现,如push_back等,也可以作为stack的容器,例如list
#include<stack>
#include<list>
#include
#include
Using namespace std;
Int main()
{
Stack
Istack.push(1);
Cout<< istack.size()<
Cout<
Istack.pop(); //pop无返回值
Cout<<.istack.top();
}
49 queue
Queue先进先出,有两个开口,尾部开口只允许入,而顶部开口只允许出,同样的queue也不允许有遍历操作,所以也没有所谓的迭代子,不能访问到里面的元素嘛
和stack一样,queue也是使用deque作为其底层容器
Template
Class queue
{
Friend bool Operator==(const queue
Friend bool operator<(..) ;
Public :
Typedef sequence ::value_type value_type ;
Typedef sequence::reference reference;
Typedef sequence::const_reference const_reference;
Protected:
Sequence c;
Public:
Bool empty() const{return c.empty();}
Size_type size() const{return c.size();}
Reference front() {return c.front();}
Const_reference front() const{return c.front();}
Reference back() {return c.back();}
Const_reference back() const{return c.back();}
Void push(const value_type& x){c.push_back(x);}
Void pop(){c.pop_front():}
}
和stack一样,queue也可以使用list作为底层容器,因为list也是双向的容器