欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-05 22:56:17
一、简介 stack是一种容器适配器(STL的容器分为顺序容器和关联容器,容器适配器,是对这两类容器进行包装得到的具有更强的约束力的容器),被设计来用于操作先进后出(FILO)结...

一、简介

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算法,递归算法;上下文切换,进程调度,以及寄存器本身。