Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1663218
  • 博文数量: 695
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 4027
  • 用 户 组: 普通用户
  • 注册时间: 2013-11-20 21:22
文章分类

全部博文(695)

文章存档

2018年(18)

2017年(74)

2016年(170)

2015年(102)

2014年(276)

2013年(55)

分类: C/C++

2013-12-22 13:41:54

STL容器之stack,queue操作

Stack不允许遍历,只有一个出口,只允许对最顶端的元素进行操作。

 

SGI STL默认以deque作为stack的底层结构

为什么要使用deque作为stack的底层结构呢?因为deque可以很容易的封住其中某个方向的接口,而且deque便于扩容,底层结合了list和vector,比起单一的使用list或者vector来实现stack更加方便高效。

由于stack是依赖底层容器完成其功能的,所以这种“修改某个物件的接口,形成另一种新的接口”的,叫做adapter

TemplateSequence=deque >

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& x, const stack& y)

{

Return x.c == y.c;

}

Template

Bool operator<(const stack& x, const stack& y)

{

Return x.c

}

 

47 因为stack所有元素都只能在顶部出入,所以不需要遍历,所以不需要迭代器

 

48 使用list作为stack的底层容器【这个可以作为参考比较!】

Stack s;

默认情况下,使用sequence=deque,作为stack的顶层容器

如果有容器也支持stack的基本操作的具体实现,如push_back等,也可以作为stack的容器,例如list

#include<stack>

#include<list>

#include

#include

Using namespace std;

Int main()

{

Stack > istack;          //我们平常使用的是默认的Stack> istack; 容器默认为deque

Istack.push(1);

Cout<< istack.size()<

Cout<

Istack.pop(); //pop无返回值

Cout<<.istack.top();

}

 

49 queue

Queue先进先出,有两个开口,尾部开口只允许入,而顶部开口只允许出,同样的queue也不允许有遍历操作,所以也没有所谓的迭代子,不能访问到里面的元素嘛

和stack一样,queue也是使用deque作为其底层容器

TemplateSequence=queue>

Class queue

{

Friend bool Operator==(const queue& q1,const queue& q2) ;

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也是双向的容器

阅读(417) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~