数据结构实战：栈、队列、优先级队列与哈希表应用

前 K 个高频单词

自定义比较器，优先按频率降序，频率相同时按字典序升序。利用哈希表统计词频，再配合优先级队列筛选 Top K。

class Solution {
    using psi = pair<string, int>;
    struct cmp {
        bool operator()(const psi& p1, const psi& p2) {
            if (p1.second == p2.second) return p1.first < p2.first;
            return p1.second > p2.second;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> ret(k);
        unordered_map<string, int> hash;
        for (auto& str : words) hash[str]++;
        priority_queue<psi, vector<psi>, cmp> pq;
        for (auto& e : hash) {
            pq.push(e);
            if (pq.size() > k) pq.pop();
        }
        while (!pq.empty()) {
            ret[--k] = pq.top().first;
            pq.pop();
        }
        return ret;
    }
};

数据流的中位数

使用两个堆维护中位数：一个大根堆存较小的一半，一个小根堆存较大的一半。保证两堆大小平衡，即可在 O(1) 时间获取中位数。

class MedianFinder {
    priority_queue<int> left; // 大根堆
    priority_queue<int, vector<int>, greater<int>> right; // 小根堆
public:
    MedianFinder() {}
    void addNum(int num) {
        if (left.size() == right.size()) {
            if (left.size() && num <= left.top()) left.push(num);
            else {
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        } else {
            if (num >= left.top()) right.push(num);
            else {
                left.push(num);
                right.push(left.top());
                left.pop();
            }
        }
    }
    double findMedian() {
        if (left.size() == right.size()) return (left.top() + right.top()) / 2.0;
        return left.top();
    }
};

2. 栈、队列

字符串消除问题

解决这类消除问题，直觉上会想到使用栈结构。不过既然最终需要返回字符串，直接使用 std::string 作为栈来操作可能更便捷，其接口丰富且无需额外转换。

注意边界情况，空串的处理返回值类型需严格匹配题目要求。

#include<iostream>
using namespace std;
int main() {
    string str, st;
    cin >> str;
    for (char ch : str) {
        if (!st.empty() && st.back() == ch) {
            st.pop_back();
            continue;
        }
        st.push_back(ch);
    }
    cout << (st.empty() ? "0" : st);
    return 0;
}

最小栈

定义一个主栈和一个辅助栈。主栈支持常规操作，辅助栈用于存储当前栈内的最小值。每当有新元素入栈，如果它小于等于辅助栈顶，则同步入栈；出栈时若主栈顶等于辅助栈顶，则辅助栈也出栈。

class MinStack {
public:
    MinStack() {}
    void push(int val) {
        _st.push(val);
        if (_minst.empty() || val <= _minst.top()) {
            _minst.push(val);
        }
    }
    void pop() {
        if (_st.top() == _minst.top()) {
            _minst.pop();
        }
        _st.pop();
    }
    int top() { return _st.top(); }
    int getMin() { return _minst.top(); }
private:
    stack<int> _st;
    stack<int> _minst;
};

栈的压入、弹出序列

模拟入栈过程，每压入一个元素就检查是否与弹出序列当前目标匹配。若匹配则立即弹出并移动弹出序列指针。遍历结束后若栈为空，说明序列合法。

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        int i = 0;
        for (int e : pushV) {
            _st.push(e);
            while (!_st.empty() && _st.top() == popV[i]) {
                _st.pop();
                ++i;
            }
        }
        return _st.empty();
    }
private:
    stack<int> _st;
};

用队列实现栈

利用队列先进先出的特性，通过辅助队列调整顺序。入栈时将所有元素依次移入辅助队列，再将新元素放入队头，最后交换两个队列的角色，确保栈顶始终在队头。

class MyStack {
    queue<int> q;
public:
    MyStack() {}
    void push(int x) {
        int n = q.size();
        q.push(x);
        while (n--) {
            q.push(q.front());
            q.pop();
        }
    }
    int pop() {
        int res = q.front();
        q.pop();
        return res;
    }
    int top() { return q.front(); }
    bool empty() { return q.empty(); }
};

用栈实现队列

利用双栈策略。一个栈专门负责入队，另一个栈专门负责出队。当出队栈为空时，将入队栈的所有元素倒入出队栈，此时队头元素即位于出队栈顶。

class MyQueue {
    stack<int> st1, st2;
    void out() {
        while (st1.size()) {
            st2.push(st1.top());
            st1.pop();
        }
    }
public:
    MyQueue() {}
    void push(int x) { st1.push(x); }
    int pop() {
        if (st2.empty()) out();
        int res = st2.top();
        st2.pop();
        return res;
    }
    int peek() {
        if (st2.empty()) out();
        return st2.top();
    }
    bool empty() { return st1.empty() && st2.empty(); }
};

图书整理 II

这是典型的用双栈模拟队列的场景，逻辑与上述'用栈实现队列'一致。

class CQueue {
    stack<int> st1, st2;
public:
    CQueue() {}
    void appendTail(int value) { st1.push(value); }
    int deleteHead() {
        if (st2.empty()) {
            while (st1.size()) {
                st2.push(st1.top());
                st1.pop();
            }
        }
        int res = -1;
        if (st2.size()) {
            res = st2.top();
            st2.pop();
        }
        return res;
    }
};

设计循环队列

使用数组实现循环队列时，通常多开一个空间以区分队空和队满状态。head 指向队首，tail 指向队尾下一个位置。通过取模运算实现索引回绕。

typedef struct {
    int* a;
    int head;
    int tail;
    int k;
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->head == (obj->tail + 1) % (obj->k + 1);
}

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    pq->a = (int*)malloc(sizeof(int) * (k + 1));
    pq->head = pq->tail = 0;
    pq->k = k;
    return pq;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) return false;
    obj->a[obj->tail++] = value;
    obj->tail %= obj->k + 1;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) return false;
    obj->head++;
    obj->head %= obj->k + 1;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) return -1;
    return obj->a[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) return -1;
    return obj->a[(obj->tail - 1 + obj->k + 1) % (obj->k + 1)];
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

3. 数组

删除有序数组中的重复项

采用快慢指针技巧。快指针遍历数组寻找不同元素，慢指针记录不重复元素的写入位置。由于数组已排序，只需比较相邻元素即可。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 1;
        for (int fast = 1; fast < nums.size(); ++fast) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};

数组中出现次数超过一半的数字

方法一：候选法 维护一个候选值和计数器。遍历数组，若计数为 0 则更新候选值，否则根据是否相等增减计数。若存在众数，最终留下的必是众数。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        int val = 0;
        int count = 0;
        for (int e : numbers) {
            if (0 == count) {
                val = e;
                ++count;
            } else {
                count = val == e ? ++count : --count;
            }
        }
        return val;
    }
};

方法二：排序法 若众数存在，排序后中间位置的元素一定是众数。虽然时间复杂度略高，但代码简洁。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        sort(numbers.begin(), numbers.end());
        return numbers[numbers.size() / 2];
    }
};

4. 哈希表

两数之和

经典的双指针或哈希查找问题。暴力枚举效率低，使用哈希表可以在一次遍历中完成查找，将时间复杂度优化至 O(N)。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) {
            if (hash.count(target - nums[i]))
                return {i, hash[target - nums[i]]};
            else
                hash[nums[i]] = i;
        }
        return {};
    }
};

判定是否互为字符重排

判断两个字符串是否为异位词。可以直接排序后比较，或者使用哈希表（或定长数组）统计字符频次。

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        int hash[26] = {};
        for (auto e : s1) hash[e - 'a']++;
        for (auto e : s2) {
            if (hash[e - 'a']) hash[e - 'a']--;
            else return false;
        }
        return true;
    }
};

存在重复元素

利用集合去重特性，或者排序后检查相邻元素。哈希表方案同样高效，遇到重复直接返回。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> hash;
        for (auto e : nums) {
            if (hash.count(e)) return true;
            else hash.insert(e);
        }
        return false;
    }
};

存在重复元素 II

在检查重复的同时，还需满足下标距离限制。哈希表记录每个数字最近出现的位置，计算差值即可。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) {
            if (hash.count(nums[i]) && abs(i - hash[nums[i]]) <= k)
                return true;
            else
                hash[nums[i]] = i;
        }
        return false;
    }
};

字母异位词分组

将字符串排序后作为 Key 存入哈希表，相同 Key 的字符串归为一组。这种方法能自动处理异位词的归类。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;
        for (auto& s : strs) {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(s);
        }
        vector<vector<string>> ret;
        for (auto& [a, b] : hash) ret.push_back(b);
        return ret;
    }
};