更多关于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语言中文网

一个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;
}