更多关于STL文章——STL学习笔记

容器适配器

stack

Class stack<> 实现出一个 stack(也称为LIFO,后进先出)。你可以使用 push() 将任意数量的元素放入 stack,也可以使用 pop() 将元素依其插入的相反次序从容器中移出(此即所谓“后进先出[LIFO]”)。

class stack 定义如下:

namespace std{
template <typename T, typename Container = deque<T>>
class stack;
}

第一个 template 参数代表元素类型。带有默认值的第二个 template 参数用来定义 stack 内部存放元素的实际容器,默认为 deque。之所以选择 deque 而非 vector ,是因为 deque 移除元素时会释放内存,并且不必在重分配,并且不必在重分配时复制全部元素。

Stack 的实现中只是很单纯地把各项操作转化为内部容器的对应调用。你可以使用任何sequence容器支持 stack,只要它们提供以下成员函数:back()、push_back() 和 pop_back()。

template<typename Tp, typename Sequence = deque<Tp> >
    class stack{
    public:
      typedef typename Sequence::value_type		value_type;
      typedef typename Sequence::reference		reference;
      typedef typename Sequence::const_reference	const_reference;
      typedef typename Sequence::size_type		size_type;
      typedef	       Sequence			container_type;
      }
类型名称定义
value_type元素的类型
reference用以指向元素之reference类型
const_reference用以指向只读元素之reference类型
size_type不带正负号的整数类型,用来表现大小
container_type内部容器的类型
  • 构造

explicit stack (const container_type& ctnr);
//构造一个stack,其内部容器被初始化为ctnr的副本。
explicit stack (container_type&& ctnr = container_type());
//构造一个stack,其内部容器通过移动构造来获取ctnr的值。
template <class Alloc> explicit stack (const Alloc& alloc);
//构造一个stack,其内部容器使用alloc作为参数构造。
template <class Alloc> stack (const container_type& ctnr, const Alloc& alloc);
//构造一个stack,其内部容器使用cntr和alloc作为参数构造。
template <class Alloc> stack (container_type&& ctnr, const Alloc& alloc);
//同上,移动构造
template <class Alloc> stack (const stack& x, const Alloc& alloc);
//构造一个stack,其内部容器使用x的内部容器作为第一个参数,而alloc作为第二个来构造。
template <class Alloc> stack (stack&& x, const Alloc& alloc);
//同上,移动构造

#include<iostream>
#include<stack>
#include<list>
#include<deque>
using namespace std;

int main()
{
    deque<int> mydeck (3,100);        //创建一个deque含3个100
    list<int> mylist (2,200);         //创建一个list含2个200

    stack<int> first;                 //创建一个空的堆栈
    stack<int> second (mydeck);       //用mydeck的拷贝作为堆栈的初始值
    //第二个参数模板默认即为 deque,因此可以不写。

    stack<int,list<int>> third; //空堆栈,列表作为底层容器
    stack<int,list<int>> fourth (mylist); //用mylist的拷贝作为堆栈的初始值

    cout << "size of first: " << first.size() << endl;
    cout << "size of second: " << second.size() << endl;
    cout << "size of third: " << third.size() << endl;
    cout << "size of fourth: " << fourth.size() << endl;

    return 0;
}

结果为:

size of first: 0
size of second: 3
size of third: 0
size of fourth: 2

下面为其成员函数:

  • empty
    判断容器是否为空

bool empty() const;

  • size
    返回当前的元素个数

size_type size() const;

  • top
    返回最后一个安插的元素

reference& top();
const_reference& top() const;

  • push
    安插一个元素

void push (const value_type& val);
void push (value_type&& val);

  • emplace
    构造与安插元素

template <class… Args> void emplace (Args&&… args);

  • pop
    移除容器内的下一个元素

void pop();

  • swap
    交换两个容器的内容

void swap (stack& x);

c语言中文网

图片来源:c语言中文网

一个stack的使用例子

题目来源:洛谷P1739

题目描述

假设一个表达式有英文字母(小写)、运算符(+,—,*,/)和左右小(圆)括号构成,以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配,若匹配,则返回“YES”;否则返回“NO”。表达式长度小于255,左圆括号少于20个。

输入格式

一行:表达式

输出格式

一行:“YES” 或“NO”

输入输出样例

输入 #1

2*(x+y)/(1-x)@

输出 #1

YES

输入 #2

(25+x)(a(a+b+b)@

输出 #2

NO

说明/提示

表达式长度小于255,左圆括号少于20个

#include<iostream>
#include<stack>
#include<string>
using namespace std;

int main()
{
    string str;
    getline(cin,str);
    stack<char> buf;
    for(auto& i:str){
        if(i=='(')   //如果等于 ( 进栈
            buf.push(i);
        else if(i==')'){  //如果等于 ) 进行判断
            if(!buf.empty())  //如果栈不为空,将最后一个进栈的 ( 弹出,说明该括号已经匹配
                buf.pop();
            else{ //如果此时栈为空,说明不匹配,直接输出NO 退出
                cout<<"NO"<<endl;
                return 0;
            }
        }
    }
    if(buf.empty())  //如果最后栈为空 说明全部匹配,输出 YES
        cout<<"YES"<<endl;
    else //如果最后栈里面还有 ( 说明未匹配,输出 NO
        cout<<"NO"<<endl;
    return 0;
}

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐