스택과 큐의 기본 개념

C++에서 std::stack과 std::queue는 컨테이너 자체가 아니라 컨테이너 어댑터(container adapter)이다. 이들은 std::deque를 기본 구현체로 사용하며, 반복자(iterator)를 제공하지 않아 요소를 순회할 수 없다.

역폴란드 표기법(후위 표기법) 계산

후위 표기법은 연산자를 피연산자 뒤에 배치하는 방식이다. 스택을 활용해 토큰을 순차적으로 처리하며, 피연산자는 스택에 push하고 연산자를 만나면 두 개의 피연산자를 pop하여 연산한 뒤 결과를 다시 push한다.

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (const string& tok : tokens) {
            if (tok == "+" || tok == "-" || tok == "*" || tok == "/") {
                int b = st.top(); st.pop();
                int a = st.top(); st.pop();
                if (tok == "+") st.push(a + b);
                else if (tok == "-") st.push(a - b);
                else if (tok == "*") st.push(a * b);
                else if (tok == "/") st.push(a / b);
            } else {
                st.push(stoi(tok));
            }
        }
        return st.top();
    }
};

주의할 점은 나눗셈과 뺄셈의 피연산자 순서다. 먼저 꺼낸 값이 두 번째 피연산자가 되므로 a - b, a / b 순서로 계산해야 올바른 결과를 얻을 수 있다.

슬라이딩 윈도우 최댓값

배열에서 크기 k인 윈도우가 한 칸씩 이동할 때, 각 윈도우의 최댓값을 구하는 문제다. 단순히 매번 최댓값을 탐색하면 O(nk)가 되지만, 단조 감소 데크(monotonic deque)를 사용하면 O(n)에 해결할 수 있다.

핵심 아이디어는 데크 내부를 내림차순으로 유지하는 것이다:

• push: 새 값이 데크의 후부 값보다 크면 기존 후부 값을 제거하고, 새 값보다 작거나 같은 값을 만날 때까지 반복한 뒤 push한다.
• pop: 윈도우에서 빠져나가는 값이 데크의 전단(front)과 같으면 전단을 제거한다.
• 데크의 전단이 항상 현재 윈도우의 최댓값이 된다.

class Solution {
private:
    class MonotonicDeque {
    public:
        deque<int> dq;

        void enqueue(int val) {
            while (!dq.empty() && val > dq.back()) {
                dq.pop_back();
            }
            dq.push_back(val);
        }

        void dequeue(int val) {
            if (!dq.empty() && val == dq.front()) {
                dq.pop_front();
            }
        }

        int getMax() {
            return dq.front();
        }
    };

public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MonotonicDeque md;
        vector<int> ans;

        for (int i = 0; i < k; ++i) {
            md.enqueue(nums[i]);
        }
        ans.push_back(md.getMax());

        for (int i = k; i < nums.size(); ++i) {
            md.enqueue(nums[i]);
            md.dequeue(nums[i - k]);
            ans.push_back(md.getMax());
        }
        return ans;
    }
};

단조 감소 데크를 사용하면 각 원소는 데크에 최대 한 번 들어가고 한 번 나오므로 전체 시간 복잡도는 O(n)이 된다. 결과는 각 윈도우 위치별 최댓값을 담은 벡터로 반환된다.