STL基础数据结构

最近在刷LeetCode，一直在用C实现上面的算法。但经常遇到题目，需要维护动态二维数组，需要队列、栈、map等数据结构时，用C实现时，需要很长的时间来完成这些数据结构的原型。无奈为了提高效率（偷懒~）决定转型C++解决上面的题目。

std::deque

类的原型

1	template < class T, class Alloc = allocator<T> > class deque;

它位于deque文件中，先看看它的类的声明。class Alloc = allocator<T> 这句话什么鬼？这可能要涉及到STL六大要素之分配器了，先跳过，以后涉及到再学。

概述

deque是C++的基本容器之一，即双端队列，它可以在两端进行插入和删除操作。不同的库可能有不同的实现方式，但通常以动态数组实现的，deque中的元素存储在不同的chunks。

deque提供的函数与vector相似，但对于在两端的插入和删除操作要比vector更有效率。还有需要注意的是，不像vector, deque不保证把所有的元素以线性的地址存储，即不能通过**指针++**的形式访问下一个元素，这将导致未定义的行为，这是与vector访问元素的区别。

还有一个区别用原文叙述比较好：While vectors use a single array that needs to be occasionally reallocated for growth, the elements of a deque can be scattered in different chunks of storage, with the container keeping the necessary information internally to provide direct access to any of its elements in constant time and with a uniform sequential interface (through iterators).

容器的特性

Sequence: Elements in sequence containers are ordered in a strict linear sequence. Individual elements are accessed by their position in this sequence.每个双端队列的元素是严格的按照线性序列排序的，每个元素可以通过它在队列中的位置直接访问到，有点像数组。
Dynamic array: Generally implemented as a dynamic array, it allows direct access to any element in the sequence and provides relatively fast addition/removal of elements at the beginning or the end of the sequence.哇，真是个好东西，程序员居家、撸代码必备的特性啊—动态数组，从此再也不用担心，容器的大小不够用了，也不用malloc、realloc等等坑爹的事情了。
Allocator-aware: The container uses an allocator object to dynamically handle its storage needs.也就是说，可以自己选择这个对象的内存分配器，allocator出现源于:对内存分配和对象构造分离的需求，因为new和delete的出现，不仅代表对象的销毁，也代表了内存的空间回收。

容器的使用

Iterators :

begin()
end() 顺序迭代器的对尾指针
rbegin()
rend() 逆序迭代器的对尾指针
cbegin()
cend() 顺序迭代器的常量指针，不能更该元素的内容
crbegin()
crend() 逆序迭代器的常量指针，不能更该元素的内容

Capacity :

size() 双端队列中元素的个数
max_size() 与平台有关，表示这种容器能容纳的最大数，通常很大
resize() 改变容器的大小，有点像remalloc函数
empty() 测试是否为空

Element access :

operator[]
at()
front()
back() 这些方法不会修改容器的内容

Modifiers :

void assign(InputIterator first, InputIterator last);
void assign(size_type n, const value_type & val);
void assign(initializer_list<value_type> il);

上述三个方法，把新的内容赋值给deque容器，并取代deque之前的内容，通常会修改容器的大小。

push_back
push_front
pop_back
pop_front
insert
erase
swap
clear
emplace
emplace_front
emplace_back

注意emplace函数与insert函数的区别在于：前者是将参数传递给元素类型的构造函数，而后者则是调用拷贝构造函数来进行操作。当容器里面存放的是某个类的对象的话，二者的区别就体现出来了。例如：

class student {
  public:
  string name;
  student(string username) : name(username) {}
};
...
...
deque<student> ST;
ST.insert(ST.end(), student("LiuChang"));
ST.emplace(ST.end(), "LiuChang");

参考：C++ Reference : deque

std::queue

类的原型

template < class T, class Container = deque<T> > class queue;
```  
从上述原型中，可以看出，其实queue是对deque双端队列的一种封装，它放在queue头文件中。
#### **基本操作**
- empty
- size
- front : 访问队首元素
- back  : 访问队尾元素
- push  : 在队尾插入元素
- pop   : 移除队首元素
- swap  : 交换俩个队列的内容  

#### 实例：二叉树的最大深度
题目来源于LeetCode:

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

这一题属于Easy级别，考虑到函数调用的开销，宜使用二叉树的层次遍历。  
```c++
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
      if ( root == NULL ) return 0;

      queue<TreeNode *> Q;
      int maxDepth = 0;

      Q.push(root);
      while(!Q.empty()) {
          ++maxDepth;
          for( int i = 0, n = Q.size(); i < n; i++ ) // 把当前层次的节点，全部弹出队列
          {
              TreeNode * q = Q.front();
              Q.pop();
              if( q->left ) Q.push(q->left);
              if( q->right ) Q.push(q->right);
          }
      }
      return maxDepth;
  }
};

std::stack

类的原型

1	template < class T, class Container = deque<T> > class stack;

它位于stack文件中，很明显，它也是对deque双端队列的封装。
基本操作

empty()
size()
top() 访问栈顶元素
push() 插入一个元素
emplace() 也是插入一个元素，以传参的方式
pop() 弹出元素
swap() 交换两个栈的内容

实例：合法的括号
题目来源于LeetCode:

1
2

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

这一题属于Easy级别，很容易想到使用栈这个数据结构。代码如下：

class Solution {
public:
    bool isValid(string s) {
        stack<char> S;
        for( int i = 0; i < s.size(); i++ ) {
            if( s[i] == '(' || s[i] == '[' || s[i] == '{' ) {
                S.push(s[i]);
            }
            else {
                if( S.empty() ) return false;
                else if( s[i] == ')' && S.top() != '(' ) return false;
                else if( s[i] == ']' && S.top() != '[' ) return false;
                else if( s[i] == '}' && S.top() != '{' ) return false;
                S.pop();
            }
        }
        if( S.empty() ) return true;
        return false;
    }
};