剑指offer之队列

一、了解队列
首先是要了解队列，队列就是一种先进先出(FIFO)的数据结构。
常用的几种队列有：queue,deque,priority_queue
其中queue是普通队列，从队尾进，队头出，且pop掉的只能是队头
而deque是双向队列，可以从队头或队尾进出，也可以从队头或队尾出。
另外，priortity_queue优先队列是据有一定功能的队列，元素进队列后会按一定原则排好，类似大小顶堆。
二、优先队列
(1) 如何使用：
定义：priority_queue<Type, Container, Functional>
Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式,一般用仿函数实现。

 //升序队列，小顶堆
 priority_queue <int,vector<int>,greater<int> > q;
 //降序队列，大顶堆
 priority_queue <int,vector<int>,less<int> >q; 
//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

怎么理解其中的less和greater仿函数：less表示小的在队列底部，因此为大顶堆，greater表示大的在底部，所以是小顶堆。
注意，缺省Functional时，默认为less，即大顶堆。
(2) 启示：
可以看出优先队列具有排序的功能，因此，除了用sort函数外，也可以利用优先队列来实现排序。
不过，sort函数的原则可以用仿函数，lambda表达式，函数指针实现，而优先队列只能使用仿函数实现，
但是，仿函数可以利用less和greater函数，实现对多维数据的排序。
三、刷题总结
(1) JZ22 从上往下打印二叉树

解：其实就是层序遍历，不多说了。

    vector<int> PrintFromTopToBottom(TreeNode* root) {
       //其实就是层序遍历
        if(!root)    return {};
        vector<int>res;
        queue<TreeNode *>q;q.push(root);
        while(!q.empty()){
            TreeNode *cur=q.front();q.pop();
            res.push_back(cur->val);
            if(cur->left)    q.push(cur->left);
            if(cur->right)    q.push(cur->right);
        }
        return res;
    }

(2) JZ61 序列化二叉树

解：
很麻烦，尤其是，用了char*，很烦人，先去吃饭。

试题链接：
JZ22 从上往下打印二叉树
JZ61 序列化二叉树