C++容器用法简介之stack容器适配器

一、简介

stack是一种容器适配器(STL的容器分为顺序容器和关联容器，容器适配器，是对这两类容器进行包装得到的具有更强的约束力的容器)，被设计来用于操作先进后出(FILO)结构的情景，在这种情况下， 元素的插入和删除都只能在容器的尾部进行。

stack通过容器适配器来实现，是一种将特定的容器类作为其最底层的容器的类，它提供了一些特定的成员函数来访问自己的元素，元素只能在这个特定容器的后面，也就是栈的顶部，进行出栈和入栈操作。

最底层的容器可以是任意一种标准的容器模板类，或者是一些有明确目的的容器类，他们应该支持以下操作：

empty(判断是否为空)size (返回栈的元素个数)back (返回栈顶元素)push_back (入栈)pop_back (出栈) 标准的容器类，比如vector，deque，list，满足以上需求。如果没有明确指定需要使用的容器，默认情况下将会使用deque。

二、函数用法示例

1、构造与析构(C++11版本)

view plain copy

initialize(1)explicitstack(constcontainer_type&ctnr);

move-initialize(2)explicitstack(container_type&&ctnr=container_type());

allocator(3)templateexplicitstack(constAlloc&alloc);

init+allocator(4)templatestack(constcontainer_type&ctnr,constAlloc&alloc);

move-init+allocator(5)templatestack(container_type&&ctnr,constAlloc&alloc);

copy+allocator(6)templatestack(conststack&x,constAlloc&alloc);

move+allocator(7)templatestack(stack&&x,constAlloc&alloc);

(1)初始化构造方式

构造一个内部元素都是ctnr的拷贝的容器适配器

(2)move-initialization constructor

构造一个内部元素都是通过移动方式获得ctnr的值的容器适配器

剩下几个带分配器的我还没有看懂，就不乱说了

cplusplus的例子：

view plain copy

//constructingstacks#include//std::cout

#include//std::stack#include//std::vector

#include//std::deque

intmain(){

std::dequemydeque(3,100);//dequewith3elementsstd::vectormyvector(2,200);//vectorwith2elements

std::stackfirst;//emptystack

std::stacksecond(mydeque);//stackinitializedtocopyofdeque

std::stack>third;//emptystackusingvectorstd::stack>fourth(myvector);

std::cout

2、empty()

返回当前栈是否为空(当它的大小是0的时候)，empty()函数并不能清空栈，只是一个返回bool型的const函数

view plain copy

stacks;s.push(1);

s.push(2);cout<

3、size()

返回容器中元素的个数，时间复杂度O(1)，返回值类型是size_type，也就是unsigned int。size()函数不能改变栈的大小

例如上面的代码段应该输出 2

4、top()

返回栈顶元素的引用。

由于栈是一种先进后出的结构，所以最顶部的元素就是最后插入栈的元素。

(C++11中会自动根据元素类型返回reference或者是const_reference，对一个空的栈调用top函数，会异常终止，所以应该使用empty()函数提前检查)

view plain copy

stacks;s.push(1);

s.push(2);cout

5、push() 和 emplace() (C++11)

push()函数和emplace()都是在栈这个容器的顶部插入一个新的元素。

push()，实际上是调用的底层容器的push_back()函数，新元素的值是push函数参数的一个拷贝。

emplace()，实际上是调用的底层容器的emplace_back()函数，新元素的值是在容器内部就地构造的，不需要移动或者拷贝。

stack的emplace也可以用在普通的基本类型上。

view plain copy

structNode{

Node(intx):x(x){}

intx;};

intmain()

{stacks1;

s1.emplace(1);s1.push(Node(2));

stacks2;

s2.emplace(1);//OKreturn0;

}

6、pop()

删除最顶部的元素，使栈的大小减小

这个被删除的元素，是刚刚插入栈的元素，这个元素和top函数的返回值是一致的。这个函数会调用对象的析构函数(如果有的话)，pop()实际上是用过底层容器的pop_back()函数实现的。

(对一个空栈进行pop()，会导致程序异常终止，应该使用empty提前检查)

view plain copy

stacks;s.push(1);

s.push(2);s.push(3);

cout

栈没有clear或者erase函数，如果想要清空一个栈，需要循环的调用出栈函数。

view plain copy

stacks;//s.erase();//error

//s.clear();//errors.push(1);

s.push(2);s.push(3);

cout

7、swap()

交换两个栈的内容(所有元素)，这个函数通过非成员函数swap()来交换底层容器，时间复杂度O(1)

cplusplus的例子

view plain copy

//stack::swap#include//std::cout

#include//std::stack

intmain(){

std::stackfoo,bar;foo.push(10);foo.push(20);foo.push(30);

bar.push(111);bar.push(222);

foo.swap(bar);

std::cout

}

8、运算符重载

view plaincopy

(1)==用于比较两个栈是否相等，首先判断大小是否相等，然后再通过operator==判断元素之间是否相等，将会在第一个不相等的地方停止

templatebooloperator==(conststack&lhs,conststack&rhs);

(2)!=和==是相反的。只要大小不同或者有一个元素不一样就是不相等的

template

booloperator!=(conststack&lhs,conststack&rhs);

(3)从第一元素开始比较当发现大于或者等于时停止，如果一个栈是另一个栈的前缀，那么长的栈大。下同

template

booloperator&lhs,conststack&rhs);

(4)

template

booloperator<=(conststack&lhs,conststack&rhs);

(5)

template

booloperator>(conststack&lhs,conststack&rhs);

(6)

template

booloperator>=(conststack&lhs,conststack&rhs);

view plaincopy

stackl1;l1.emplace(1);

l1.emplace(2);l1.emplace(3);

stackl2;l2.emplace(1);

l2.emplace(2);cout

四、结语

栈是一种特别常用的数据结构，在各种编程语言或者是操作系统内部，都能见到。常见的DFS算法，递归算法;上下文切换，进程调度，以及寄存器本身。