`
deepfuture
  • 浏览: 4321000 次
  • 性别: Icon_minigender_1
  • 来自: 湛江
博客专栏
073ec2a9-85b7-3ebf-a3bb-c6361e6c6f64
SQLite源码剖析
浏览量:79301
1591c4b8-62f1-3d3e-9551-25c77465da96
WIN32汇编语言学习应用...
浏览量:68099
F5390db6-59dd-338f-ba18-4e93943ff06a
神奇的perl
浏览量:101182
Dac44363-8a80-3836-99aa-f7b7780fa6e2
lucene等搜索引擎解析...
浏览量:280241
Ec49a563-4109-3c69-9c83-8f6d068ba113
深入lucene3.5源码...
浏览量:14534
9b99bfc2-19c2-3346-9100-7f8879c731ce
VB.NET并行与分布式编...
浏览量:65149
B1db2af3-06b3-35bb-ac08-59ff2d1324b4
silverlight 5...
浏览量:31183
4a56b548-ab3d-35af-a984-e0781d142c23
算法下午茶系列
浏览量:45067
社区版块
存档分类
最新评论

c++中stack,deque,queue

 
阅读更多

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初步(1)

    组成的库来说提供了更好的代码...在C++标准中,STL被组织为下面的几个头文件:、、、&lt;deque&gt;、、、、、、、&lt;queue&gt;、、&lt;stack&gt;和。文件中主要介绍了前面八个的使用,并且重点介绍了他们的属性和一些成员函数的使用。

    C++ STL 中文版

    迭代器,utility,iterator,memory,算法,algorithm,numeric,functional,vector,list,deque,set,map,stack,queue逐章介绍

    C++顺序容器,容器适配器,关联容器的操作

    包括顺序容器vector,string,list,forward,deque ,array;容器适配器stack,queue,priority_queue以及关联容器map,set,multimap,unordered_multimap等的增删查改操作。

    C++标准模板库STL初步(2)

    组成的库来说提供了更好的代码...在C++标准中,STL被组织为下面的几个头文件:、、、&lt;deque&gt;、、、、、、、&lt;queue&gt;、、&lt;stack&gt;和。文件中主要介绍了前面八个的使用,并且重点介绍了他们的属性和一些成员函数的使用。

    C++标准库(第2版)STL 源码

    STL(Standard Template Library,标准模板库)是惠普实验室开发的一系列软件的统称。现然主要出现在C++中,但在被引入...在C++标准中,STL被组织为下面的13个头文件:、&lt;deque&gt;、、、、、、、、&lt;queue&gt;、、&lt;stack&gt;和。

    c++中容器之总结篇

    顺序容器适配器:stack、queue和priority_queue。 关联容器:支持通过键来高效地查找和读取元素。主要有:pair、set、map、multiset和multimap。 接下来依次对于各种容器做详细的介绍。 一、顺序容器 1、顺序容器...

    C++进阶课程讲义_v1.0.4.pdf

    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++标准模板库源代码

    C++标准模板库源代码主要涉及下面几个内容: vector 向量 deque 双端队列 list 链表 map 映射 multiset 多重集合 queue 队列 set 集合 stack 堆栈。

    本人精心收集,c++头文件一览

    deque&gt; //STL 双端队列容器 #include &lt;exception&gt; //异常处理类 #include &lt;fstream&gt; #include &lt;functional&gt; //STL 定义运算函数(代替运算符) #include &lt;limits&gt; #include &lt;list&...

    C和C++头文件对比一览

    同时标准化委员会声明就有的C++头文件将不再列于被支持的名单之中了,而旧有的C头文件为了满足“对C的兼容性”这个古老契约,仍然将继续存活下去。 但是,那些编译器厂商不可能去推翻他们客户的旧有编译器(也跟本...

    C++ STL 开发技术导引(第6章)

    第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) -容器

    STL的代码从广义上讲分为三类:algorithm(算法)、container(容器)和iterator(迭代器),几乎所有的代码都采用了...在C++标准中,STL被组织为下面的13个头文件:、&lt;deque&gt;、、、、、、 、、&lt;queue&gt;、、&lt;stack&gt;和。

    本例程提供了C++的STL常用数据结构及其算法的使用范例,比如vector、string、list

    本例程提供了C++的STL常用数据结构及其算法的使用范例,比如vector、string、list、forward_list、deque、queue、stack、map、set、multimap、multiset、tuple、bitset的使用范例,以及algorithm常….zip

    C++容器类的简单介绍.doc

    deque 双队列,从前面或后面快速的插入与删除,直接访问任何元素 list 双链表,从任何地方快速插入与删除 关联容器 set 快速查找,不允许重复值 multiset 快速查找,允许重复值 map 一对一映射,基于关键字快速...

    leetcode叫数-DataStructure:常见数据结构C++(leetcode/牛客)

    线性结构是如deque,stack,queue这种数据结构,它们的存储方式可以有顺序存储方式,也可以有链式存储方式。 在内存中的存储方式不同,带来的结果也不同。 单链表/双链表/循环链表/十字链表 链表的插入、删除、创建...

    C++大学教程,一本适合初学者的入门教材(part1)

    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 ...

    C++ STL开发技术导引(第5章)

    第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开发技术导引(第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 内联函数 ...

    STL知识点思维导图

    组成的库来说提供了更好的代码...在C++标准中,STL被组织为下面的几个头文件:、、、&lt;deque&gt;、、、、、、、&lt;queue&gt;、、&lt;stack&gt;和。文件中主要介绍了前面八个的使用,并且重点介绍了他们的属性和一些成员函数的使用。

Global site tag (gtag.js) - Google Analytics