#堆栈总结(一)#

一.知识点总结

1.先简单的介绍两个数据结构：

(1)栈：栈的主要特点就是先进后出，只在栈顶进行入栈和出栈操作

(2)队列：队列主要特点是先进先出，队列可以分为一般队列和双端队列，一般队列可以实现对队列的队头 访问、队头出队和队尾插入；双端队列可以实现对队头队尾元素的访问、插入和删除。

利用c++的STL来实现队列和栈：
stack <type> name ; //栈的实现
type top() ; //栈顶元素访问
void pop() ; //出栈操作
void push(X) ; ///元素x入栈操作

queue <type> name ; //一般队列的实现
type front() ; //队头元素访问
void pop() ; //出队操作
void push(X) ; ///元素x入队操作

deque <type> name ; //双端队列的实现
void push_front(x):双端队列头部增加一个元素X
void push_back(x):双端队列尾部增加一个元素x
type front():返回队头元素
type back():返回队尾元素

2.对于两种基础的数据结构认识后，我们来了解一下二叉树：

(1)什么是二叉树

二叉树：是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。
对于二叉树有四种常考察的遍历方式：前序、中序、后序和层序遍历
前序遍历：先根，再左，最后右
中序遍历：先左，再根，最后右
后序遍历：先左，再右，最后根
层次遍历：按照树的层次依次遍历

对于前中后三种遍历方式可以利用递归快速实现，下面给出先序遍历的递归实现(剩下两种类似):

/*
先序遍历的实现
若二叉树是空树，则什么都不做；否则：
(1)访问根节点
(2)先序遍历左子树
(3)先序遍历右子树
*/
void preorder(TreeNode* t){
        if(t!=NULL) return ;
        visit(t);//假设访问函数visit已经访问过来，其中包含看对结点t的各种操作，如打印td
        xian(t->left);//先序遍历左子树
        xian(t->right);//先序遍历右子树
}
/*
只需要根据遍历顺序更改递归顺序即可
*/

(2)对于树的遍历的介绍

层序遍历的实现不同于前面三种利用递归实现，而是可以通过队列来实现的，下面给出伪代码：

void LevelOrder(BTree *t){
//利用队列来实现
    Queue Q;
    initQueue(Q);
    EnQueue(Q,t);
    while(!Empty(Q)){
        TNode*p=DeQueue(Q);
        //左右节点入队列
        if(p->lchird) EnQueue(Q,p->lchird);
        if(p->rchird) EnQueue(Q,p->rchird);
    }
}

上面有关对二叉树前中后和层数遍历都是笔者基于统一性和简便性提供的，并不是唯一的实现方法。

3.单调栈：是一个栈，不过栈内元素保证单调性。即，栈内元素要么从小到大，要么从大到小。 而单调栈维护的就是一个数前(后)第一个大于(小于)他的数。

单调栈的伪代码：

while(栈顶元素比入栈元素小且栈不空){
        栈顶元素弹出
}
元素入栈

首先要知道单调栈入栈的的是下标。对于入栈元素直接入栈会破坏单调性，所以需要栈顶元素出栈，后加入当前元素，使得我们当前的元素再加进去不会破坏它的单调性。

4.利用栈解决表达式求值的问题：我们要知道利用栈的先进后出的性质可以用来实现对于表达式求值，这也是栈的一个比较常见使用方式。

对于表达式求值需要引入三个有关表达式的基本概念：

对于算术表达式一般分成三种有：前缀、后缀和中缀
中缀表达式：救是我们常见的算术表达式，就是一眼看上去就能理解的表达式，例如：2*(5+8)
前缀表达式：形如"op A B"即操作数在两个运算数的前面
后缀表达式：形如"A B op"即操作数在两个运算数的后面

我们平时直观看见的就是中缀表达式，但是对于计算机而言其更容易计算的是后缀表达式的值，所以我们处理的总体思路就是：先将中缀表达式转换为 后缀表达式，然后对后缀表达式求值。

下面是实现思路：

中缀表达数转后缀表达式：
1.建立一个存储运算符的栈，对中缀表达式进行扫描。
(1)如果遇到一个数就直接存进后缀表达式中。
(2)如果遇到了一个左括号，就把左括号直接入栈。
(3)如果遇到右括号，不断取出栈顶并输出，直到栈顶为左括号，然后左括号出栈。
(4)如果遇到运算符，只需要栈顶符号的优先级补丁与新符号，就不断出栈并输出，然后将新符号入栈。
2.依次取出并存储栈中所有剩余的符号。

后缀表达式求值：
1.建立一个用于存储的数的栈，对后缀表达式进行依次扫描
(1)如果遇见一个数，那么就把这个数直接入栈
(2)如果遇到运算符，就取出栈顶的两个数进行计算，然后把结果入栈。
2.最后的栈顶元素就是表达式的值

5.链表：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。但是广义上链表实现有很多种，不仅仅可以通过指针，还可以通过数组来实现，c++的STL中也有链表的实现，链表相比于数组，更容易进行插入删除。

下面是利用指针实现链表的插入和删除操作：

插入：//链表的插入分为头插法和尾插法 分别表示从头部插入一个元素，还是尾部插入一个元素
x= p -> next;
p -> next = q;
q -> next = x;
删除：
x = p -> next;
p -> next = x -> next;
free(x);

6.滑动窗口：简单来说就是利用双指针来维护一个窗口，思路很简单但是对于左右两个指针的细节处理很困难，下面给出滑动窗口的框架模板：

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

7.sort函数：用于C++中，对给定区间所有元素进行排序，默认为升序，也可进行降序排序。

sort函数的介绍：sort函数用于C++中，对给定区间所有元素进行排序，默认为升序，
也可进行降序排序。sort函数进行排序的时间复杂度为n*log2n，比冒泡之类的排序算法效率要高

对于vector使用sort排序：
sort(vec.begin(),vec.end()); //可以实现对vector从小到大的排序
sort(vec.begin(),vec.end(),greater<int>()); //可以实现对vector从大到小的排序

对于vector<node>使用sort排序：
struct node {
	int id;
	string name;
}
sort(vec.begin(),vec.end(),cmp);
bool cmp(node a,node b){
	return a.id<b.id //对id进行排序，id小的再前面
}

8.大根堆和小根堆：

最大堆（大根堆）：根结点的键值是所有堆结点键值中最大者。
最小堆（小根堆）：根结点的键值是所有堆结点键值中最小者。

利用c++STL实现：
priority_queue<int> pq1 // 大根堆
priority_queue<int, vector<int>, greater<int>> pq2 // 小根堆

自定义比较函数：
struct cmp {bool operator()(int a,int b) {return a > b;}}; // 自定义小根堆
priority_queue<int, vector<int>, cmp> pq;	

二.小试牛刀

题目1：有效括号序列

利用栈实现有效序列的判断是栈一种比较常用的使用方法，利用栈先进后出的特点，从而实现对括号的有效配对，按照一下流程实现即可。

(1)当遇到左括号：'(', '[',,'{'或者栈为空时，就将当前位置的字符入栈。
(2)如果遇到右括号时，就比对当前字符和栈顶字符是不是对应的括号。
(3)如果不对应或者栈此时失控，那么直接返回false，说明这个字符串不是合法的括号序列
(4)如果是对应的括号，那么就把栈顶的字符出栈，进行下一次循环。 

题目2：包含min函数的栈

该题属于是栈的灵活运用，利用栈的特点实现对最小值栈的维护，要理解辅助栈的实现流程。

题目3：用两个栈实现队列

基于前面对于数据结构知识总结，我们知道队列的特点就是先进先出，所以该题可以利用queue来直接实现，也可以利用两个栈来实现，一个栈用来实现入队，一个栈用来实现出队，从而实现队列先进先出的特点。

题目4：按之字形顺序打印二叉树

首先是层次遍历确定无疑，那么主要是如何实现之字形打印，需要找到每一层的遍历顺序(提示：根据层数奇偶，遍历方向不同)，在层序遍历的基础上实现对其之字形打印，重点是如何处理正序和倒序。

题目5：序列化二叉树

序列化：
按照层次遍历将每个节点加入字符串中，当遇到空节点则加入null。
反序列化：
同样按照层次遍历的思想，首先构造头节点，然后再遍历节点的同时构造其左右子节点并入队列，当队列为空时，反序列化完毕。

由于对于遍历顺序没有什么太大的要求，所以怎么简单怎么来，但是有一个细节由于返回的是字符数组，但是大多数都是用string来进行处理，所以最后需要利用c_str()来实现string转换为字符数组。

问题6：滑动窗口的最大值

由于是要求最大值，但是由于区间长度的限制，所以我们在窗口收缩的时候不仅仅要注意最大值的维护，还要注意最大值是否在窗口中。

问题7：实现二叉树先序，中序和后序遍历

该题有点乱入，可以参考堆栈总结(一)，三种遍历方式都可以通过递归快速实现，条理清晰，代码容易实现。

问题8：表达式求值

栈最基本的实现，但是本题的细节仍然有很多需要注意的，特别是在字符串中对数字、符号的分离和栈中是否还有元素。

题目9：单调栈

题目要求做左边和右边的最小值，所以只需要进行两次遍历即可，一遍正序，一遍逆序，但是题目最后需要返回的是vecter<vecter>，所以可以提前分配空间进行存储。

题目10：合并k个已排序的链表

由于是k个有序链表，合并起来只需要每次将最值取出，插入到需要返回的链表中，最后就可以返回一个有序链表了。(提示：这里面可以使用尾插法哦！)

题目11：最小的K个数

最小的K个数很显然只需要排序后对k个数进行记录，然后返回。

题目12：寻找第K大

第K大的数很显然只需要在排序后返回第K个数。

题目13：数据流中的中位数

是栈的灵活应用，我们可以利用两个堆栈，分别去维护左边的最大值和最小值，进而求出中位数。