STL包含一些为满足特殊需求而设计的容器,
他们提供简单而清晰的接口:
1.Stack
2.Queue
3.Priority Queue
4.bitset
本文介绍Stack.
Stack(也称LIFO,即后进先出)的声明如下:
template<typename _Tp, typename _Sequence = deque<_Tp> >
class stack;
第一个template代表元素类型
第二个template代表stack内部存放元素所用的实际容器,缺省用deque。
之所以选择deque而不是vector是因为:
1.deque移除元素时候会释放内存,
2.deque不必在重新分配内存是复制全部元素
实际上,stack只是很单纯的把各项操作转换为内部容器的对应调用。这从其实现代码也可以看出,下面是stack的源代码,这里去掉了value_type等声明和构造析构函数等,主要列举了几个常用的接口:
protected:
_Sequence c; ///内部容器
public:
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference top() ///注意top返回的是reference
{
__glibcxx_requires_nonempty();
return c.back();
}
const_reference top() const
{
__glibcxx_requires_nonempty();
return c.back();
}
void push(const value_type& __x)
{ c.push_back(__x); }
void pop()
{
__glibcxx_requires_nonempty();
c.pop_back();
}
我们可以使用任何序列式容器来支持stack,
只要他们支持back(),push_back(),pop_back()等动作就行。
如以vector支持stack可定义: stack<int,vector<int> > intStack;
核心接口(源代码中可以看出其实现):
1.push()
2.pop()
3.top()
4.size()
5.empty()
6.comparision(const stack& s1,const stack& s2) ///两个同型stack的比较,
comparision可以是:==,!=,<,>,<=,>=
(如果两个stack的size()相等并且对应元素也相等则它们相等;比较基于字典序,参考lexicographical_compare())
下面是stack的一个简单的应用:
void testStack()
{
stack<int> intStack;
for(int i=1;i<10;++i)
intStack.push(i);
cout<<"Size = "<<intStack.size()<<endl;
string empty = intStack.empty()?"True":"False";
cout<<"Empty = "<<empty<<endl;
cout<<"Stack top() = "<<intStack.top()<<endl;
intStack.top() = 100; ///利用top()返回reference修改top值
cout<<"Stack All Elements: ";
while(!intStack.empty())
{
cout<<intStack.top()<<" ";
intStack.pop();
}
cout<<endl;
}
c++中stack,deque,queue对比
stack堆栈,没有迭代器,支持push()方法。后进先出,top()返回最顶端的元素,pop()剔除最顶元素
deque双端队列,支持迭代器,有push_back()方法,跟vector差不多,比vector多了个pop_front,push_front方法
queue队列,先进先出,不支持迭代器,有push()方法,pop()剔除第一个元素,front()返回第一个元素
代码如下:
#include<iostream>
#include<stack>
#include<string>
using namespace std;
int main(){
stack<int>s;
for(int i=1;i<=10;++i){
s.push(i);
}
for(int j=0;j<10;++j){
cout<<s.top()<<" ";
s.pop();
}
cout<<endl;
system("pause");
return 0;
}
#include<iostream>
#include<string>
#include<deque>
using namespace std;
int main(){
deque<int>q;
for(int i=0;i<10;++i){
q.push_back(i);
}
cout<<q.front()<<endl;
for(deque<int>::iterator iter=q.begin();iter!=q.end();++iter){
cout<<*iter<<" ";
}
cout<<endl;
cout<<q.back()<<endl;
system("pause");
return 0;
}
#include<iostream>
#include<queue>
#include<string>
using namespace std;
int main(){
queue<int>q;
for(int i=0;i<10;++i){
q.push(i);
}
for(int i=0;i<10;++i){
cout<<q.front()<<" ";
q.pop();
}
cout<<endl;
system("pause");
return 0;
}
分享到:
相关推荐
组成的库来说提供了更好的代码...在C++标准中,STL被组织为下面的几个头文件:、、、<deque>、、、、、、、<queue>、、<stack>和。文件中主要介绍了前面八个的使用,并且重点介绍了他们的属性和一些成员函数的使用。
迭代器,utility,iterator,memory,算法,algorithm,numeric,functional,vector,list,deque,set,map,stack,queue逐章介绍
包括顺序容器vector,string,list,forward,deque ,array;容器适配器stack,queue,priority_queue以及关联容器map,set,multimap,unordered_multimap等的增删查改操作。
组成的库来说提供了更好的代码...在C++标准中,STL被组织为下面的几个头文件:、、、<deque>、、、、、、、<queue>、、<stack>和。文件中主要介绍了前面八个的使用,并且重点介绍了他们的属性和一些成员函数的使用。
STL(Standard Template Library,标准模板库)是惠普实验室开发的一系列软件的统称。现然主要出现在C++中,但在被引入...在C++标准中,STL被组织为下面的13个头文件:、<deque>、、、、、、、、<queue>、、<stack>和。
顺序容器适配器:stack、queue和priority_queue。 关联容器:支持通过键来高效地查找和读取元素。主要有:pair、set、map、multiset和multimap。 接下来依次对于各种容器做详细的介绍。 一、顺序容器 1、顺序容器...
10.2.4stack容器 101 10.2.5Queue容器 103 10.2.6List容器 105 10.2.7优先级队列priority_queue 110 10.2.8Set和multiset容器 111 10.2.9Map和multimap容器 118 10.2.10容器共性机制研究 123 10.2.11其他 124 10.3...
C++标准模板库源代码主要涉及下面几个内容: vector 向量 deque 双端队列 list 链表 map 映射 multiset 多重集合 queue 队列 set 集合 stack 堆栈。
deque> //STL 双端队列容器 #include <exception> //异常处理类 #include <fstream> #include <functional> //STL 定义运算函数(代替运算符) #include <limits> #include <list&...
同时标准化委员会声明就有的C++头文件将不再列于被支持的名单之中了,而旧有的C头文件为了满足“对C的兼容性”这个古老契约,仍然将继续存活下去。 但是,那些编译器厂商不可能去推翻他们客户的旧有编译器(也跟本...
第1章 C++编程技术 2 1.1 类和对象 2 1.2 类的继承 5 1.3 函数重载 5 1.4 访问控制 7 1.5 操作符重载 8 1.6 显式类型转换 9 1.7 异常处理 13 1.8 名字空间 17 1.9 友员函数 20 1.10 内联函数 ...
STL的代码从广义上讲分为三类:algorithm(算法)、container(容器)和iterator(迭代器),几乎所有的代码都采用了...在C++标准中,STL被组织为下面的13个头文件:、<deque>、、、、、、 、、<queue>、、<stack>和。
本例程提供了C++的STL常用数据结构及其算法的使用范例,比如vector、string、list、forward_list、deque、queue、stack、map、set、multimap、multiset、tuple、bitset的使用范例,以及algorithm常….zip
deque 双队列,从前面或后面快速的插入与删除,直接访问任何元素 list 双链表,从任何地方快速插入与删除 关联容器 set 快速查找,不允许重复值 multiset 快速查找,允许重复值 map 一对一映射,基于关键字快速...
线性结构是如deque,stack,queue这种数据结构,它们的存储方式可以有顺序存储方式,也可以有链式存储方式。 在内存中的存储方式不同,带来的结果也不同。 单链表/双链表/循环链表/十字链表 链表的插入、删除、创建...
20.2.3 deque顺序容器 20.3 关联容器 20.3.1 multiset关联容器 20. 3.2 set关联容器 20.3.3 mdtimap关联容器 20.3.4 map关联容器 20.4 容器适配器 20.4.1 stack适配器 20.4.2 queue适配器 20.4.3 ...
第1章 C++编程技术 2 1.1 类和对象 2 1.2 类的继承 5 1.3 函数重载 5 1.4 访问控制 7 1.5 操作符重载 8 1.6 显式类型转换 9 1.7 异常处理 13 1.8 名字空间 17 1.9 友员函数 20 1.10 内联函数 ...
第1章 C++编程技术 2 1.1 类和对象 2 1.2 类的继承 5 1.3 函数重载 5 1.4 访问控制 7 1.5 操作符重载 8 1.6 显式类型转换 9 1.7 异常处理 13 1.8 名字空间 17 1.9 友员函数 20 1.10 内联函数 ...
组成的库来说提供了更好的代码...在C++标准中,STL被组织为下面的几个头文件:、、、<deque>、、、、、、、<queue>、、<stack>和。文件中主要介绍了前面八个的使用,并且重点介绍了他们的属性和一些成员函数的使用。