数据结构与算法笔记 | 栈和队列

栈和队列是使用相当广泛的两种数据结构，它们都属于线性数据结构。
栈结构的特点是FILO（First In Last Out），队列结构的特点是FIFO（First In First Out）。性质随简单易懂，但真正掌握灵活运用还是需要一定功夫的。面试时候考察也多以结合其他算法数据结构（如串、树、动态规划等）来进行考察。本篇接下来主要介绍栈和队列相结合的一些考察点，之后再介绍一些特殊的栈/队列结构，如双端队列和单调栈/队列。

栈和队列的结合

使用栈实现队列

用两个栈实现一个队列，方法是数据常存在一个主栈中，出队列操作会用到另一个辅助栈，出队列操作主栈和辅助栈地位相互调换。入队列操作即为入主栈操作。

使用队列实现栈

用两个队列实现一个栈

既用到栈又用到队列的一道题 —— 反转字符串中的元音字母

题目让反转字符串中的元音字母，其余字母照常输出。而栈天生就具备这种反转的性质。所以考虑元音字母使用一个栈保存，而元音字母所在序号恰好可以用队列存，这样便使元音字母从栈依次弹出时，队列序号能依次指向对应位置。
LeetCode链接

string reverseVowels(string s) {
    stack<char> vowels;
    queue<int> indices;
    for(int i=0; i<s.size(); ++i) {
        if(isVowel(s[i])) {
            indices.push(i);
            vowels.push(s[i]);
        }
    }
    while(!vowels.empty()) {
        s[indices.front()] = vowels.top();
        vowels.pop();
        indices.pop();
    }
    return s;
}

inline bool isVowel(char c) {
    c = tolower(c);
    return c=='a'||c=='e'||c=='i'||c=='o'||c=='u';
}

一些特殊的栈/队列结构

1. 双端队列 —— 更加广义的栈和队列

双端队列既可以当作栈用，也可以当作队列用，实际上C++ std库中stack和queue的底层实现就是这玩意。来一道题感受一下双端队列的强大之处：

2. 单调队列和单调栈

单调队列可以解决滑动窗口最大值的问题。

例题：包含min函数的栈
牛客网链接 和 AC代码

运用单调栈的经典问题当属曼哈顿天际线问题