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

std::deque

类的原型

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).

容器的特性

容器的使用

Iterators :

Capacity :

Element access :

Modifiers :

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

注意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头文件中。

基本操作

实例:二叉树的最大深度

题目来源于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级别,考虑到函数调用的开销,宜使用二叉树的层次遍历。

/**
 * 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

类的原型

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

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

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

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

纸上得来终觉浅,绝知此事要躬行~