1/*
2 * μ€νκ³Ό ν (Stack and Queue)
3 * Stack, Queue, Deque, Monotonic Stack/Queue
4 *
5 * μ ν μλ£κ΅¬μ‘°μ νμ©μ
λλ€.
6 */
7
8#include <iostream>
9#include <vector>
10#include <stack>
11#include <queue>
12#include <deque>
13#include <string>
14#include <unordered_map>
15
16using namespace std;
17
18// =============================================================================
19// 1. μ€ν κΈ°λ³Έ νμ©
20// =============================================================================
21
22// κ΄νΈ μ ν¨μ± κ²μ¬
23bool isValidParentheses(const string& s) {
24 stack<char> st;
25 unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
26
27 for (char c : s) {
28 if (c == '(' || c == '[' || c == '{') {
29 st.push(c);
30 } else {
31 if (st.empty() || st.top() != pairs[c])
32 return false;
33 st.pop();
34 }
35 }
36
37 return st.empty();
38}
39
40// νμ νκΈ°λ² κ³μ°
41int evalRPN(const vector<string>& tokens) {
42 stack<int> st;
43
44 for (const string& token : tokens) {
45 if (token == "+" || token == "-" || token == "*" || token == "/") {
46 int b = st.top(); st.pop();
47 int a = st.top(); st.pop();
48
49 if (token == "+") st.push(a + b);
50 else if (token == "-") st.push(a - b);
51 else if (token == "*") st.push(a * b);
52 else st.push(a / b);
53 } else {
54 st.push(stoi(token));
55 }
56 }
57
58 return st.top();
59}
60
61// μ€μ β νμ λ³ν
62string infixToPostfix(const string& infix) {
63 stack<char> st;
64 string postfix;
65 unordered_map<char, int> precedence = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
66
67 for (char c : infix) {
68 if (isalnum(c)) {
69 postfix += c;
70 } else if (c == '(') {
71 st.push(c);
72 } else if (c == ')') {
73 while (!st.empty() && st.top() != '(') {
74 postfix += st.top();
75 st.pop();
76 }
77 st.pop(); // '(' μ κ±°
78 } else {
79 while (!st.empty() && st.top() != '(' &&
80 precedence[st.top()] >= precedence[c]) {
81 postfix += st.top();
82 st.pop();
83 }
84 st.push(c);
85 }
86 }
87
88 while (!st.empty()) {
89 postfix += st.top();
90 st.pop();
91 }
92
93 return postfix;
94}
95
96// =============================================================================
97// 2. λͺ¨λ
Έν λ μ€ν (Monotonic Stack)
98// =============================================================================
99
100// λ€μ ν° μμ (Next Greater Element)
101vector<int> nextGreaterElement(const vector<int>& nums) {
102 int n = nums.size();
103 vector<int> result(n, -1);
104 stack<int> st; // μΈλ±μ€ μ μ₯
105
106 for (int i = 0; i < n; i++) {
107 while (!st.empty() && nums[st.top()] < nums[i]) {
108 result[st.top()] = nums[i];
109 st.pop();
110 }
111 st.push(i);
112 }
113
114 return result;
115}
116
117// νμ€ν κ·Έλ¨μμ κ°μ₯ ν° μ§μ¬κ°ν
118int largestRectangleArea(const vector<int>& heights) {
119 stack<int> st;
120 int maxArea = 0;
121 int n = heights.size();
122
123 for (int i = 0; i <= n; i++) {
124 int h = (i == n) ? 0 : heights[i];
125
126 while (!st.empty() && heights[st.top()] > h) {
127 int height = heights[st.top()];
128 st.pop();
129 int width = st.empty() ? i : i - st.top() - 1;
130 maxArea = max(maxArea, height * width);
131 }
132 st.push(i);
133 }
134
135 return maxArea;
136}
137
138// μΌμΌ μ¨λ (Daily Temperatures)
139vector<int> dailyTemperatures(const vector<int>& temperatures) {
140 int n = temperatures.size();
141 vector<int> result(n, 0);
142 stack<int> st;
143
144 for (int i = 0; i < n; i++) {
145 while (!st.empty() && temperatures[st.top()] < temperatures[i]) {
146 result[st.top()] = i - st.top();
147 st.pop();
148 }
149 st.push(i);
150 }
151
152 return result;
153}
154
155// =============================================================================
156// 3. ν νμ©
157// =============================================================================
158
159// BFSμ© ν (κ°λ¨ μμ)
160vector<int> bfsOrder(const vector<vector<int>>& graph, int start) {
161 vector<int> result;
162 vector<bool> visited(graph.size(), false);
163 queue<int> q;
164
165 q.push(start);
166 visited[start] = true;
167
168 while (!q.empty()) {
169 int node = q.front();
170 q.pop();
171 result.push_back(node);
172
173 for (int neighbor : graph[node]) {
174 if (!visited[neighbor]) {
175 visited[neighbor] = true;
176 q.push(neighbor);
177 }
178 }
179 }
180
181 return result;
182}
183
184// =============================================================================
185// 4. λ± (Deque) νμ©
186// =============================================================================
187
188// μ¬λΌμ΄λ© μλμ° μ΅λκ°
189vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
190 deque<int> dq; // μΈλ±μ€ μ μ₯
191 vector<int> result;
192
193 for (int i = 0; i < (int)nums.size(); i++) {
194 // μλμ° λ²μ΄λ μμ μ κ±°
195 while (!dq.empty() && dq.front() <= i - k) {
196 dq.pop_front();
197 }
198
199 // νμ¬ μμλ³΄λ€ μμ μμ μ κ±°
200 while (!dq.empty() && nums[dq.back()] < nums[i]) {
201 dq.pop_back();
202 }
203
204 dq.push_back(i);
205
206 if (i >= k - 1) {
207 result.push_back(nums[dq.front()]);
208 }
209 }
210
211 return result;
212}
213
214// =============================================================================
215// 5. λ μ€νμΌλ‘ ν ꡬν
216// =============================================================================
217
218class MyQueue {
219private:
220 stack<int> input, output;
221
222 void transfer() {
223 if (output.empty()) {
224 while (!input.empty()) {
225 output.push(input.top());
226 input.pop();
227 }
228 }
229 }
230
231public:
232 void push(int x) {
233 input.push(x);
234 }
235
236 int pop() {
237 transfer();
238 int val = output.top();
239 output.pop();
240 return val;
241 }
242
243 int peek() {
244 transfer();
245 return output.top();
246 }
247
248 bool empty() {
249 return input.empty() && output.empty();
250 }
251};
252
253// =============================================================================
254// 6. μ΅μ μ€ν (Min Stack)
255// =============================================================================
256
257class MinStack {
258private:
259 stack<int> st;
260 stack<int> minSt;
261
262public:
263 void push(int val) {
264 st.push(val);
265 if (minSt.empty() || val <= minSt.top()) {
266 minSt.push(val);
267 }
268 }
269
270 void pop() {
271 if (st.top() == minSt.top()) {
272 minSt.pop();
273 }
274 st.pop();
275 }
276
277 int top() {
278 return st.top();
279 }
280
281 int getMin() {
282 return minSt.top();
283 }
284};
285
286// =============================================================================
287// ν
μ€νΈ
288// =============================================================================
289
290void printVector(const vector<int>& v) {
291 cout << "[";
292 for (size_t i = 0; i < v.size(); i++) {
293 cout << v[i];
294 if (i < v.size() - 1) cout << ", ";
295 }
296 cout << "]";
297}
298
299int main() {
300 cout << "============================================================" << endl;
301 cout << "μ€νκ³Ό ν μμ " << endl;
302 cout << "============================================================" << endl;
303
304 // 1. κ΄νΈ κ²μ¬
305 cout << "\n[1] κ΄νΈ μ ν¨μ± κ²μ¬" << endl;
306 cout << " \"()[]{}\" : " << (isValidParentheses("()[]{}") ? "μ ν¨" : "무ν¨") << endl;
307 cout << " \"([)]\" : " << (isValidParentheses("([)]") ? "μ ν¨" : "무ν¨") << endl;
308
309 // 2. νμ νκΈ°λ²
310 cout << "\n[2] νμ νκΈ°λ²" << endl;
311 vector<string> rpn = {"2", "1", "+", "3", "*"};
312 cout << " [\"2\",\"1\",\"+\",\"3\",\"*\"] = " << evalRPN(rpn) << endl;
313
314 cout << " \"a+b*c\" β \"" << infixToPostfix("a+b*c") << "\"" << endl;
315
316 // 3. λͺ¨λ
Έν λ μ€ν
317 cout << "\n[3] λͺ¨λ
Έν λ μ€ν" << endl;
318 vector<int> nums = {2, 1, 2, 4, 3};
319 cout << " λ°°μ΄: [2,1,2,4,3]" << endl;
320 cout << " λ€μ ν° μμ: ";
321 printVector(nextGreaterElement(nums));
322 cout << endl;
323
324 vector<int> heights = {2, 1, 5, 6, 2, 3};
325 cout << " νμ€ν κ·Έλ¨ [2,1,5,6,2,3] μ΅λ μ§μ¬κ°ν: " << largestRectangleArea(heights) << endl;
326
327 vector<int> temps = {73, 74, 75, 71, 69, 72, 76, 73};
328 cout << " μΌμΌ μ¨λ [73,74,75,71,69,72,76,73]: ";
329 printVector(dailyTemperatures(temps));
330 cout << endl;
331
332 // 4. μ¬λΌμ΄λ© μλμ° μ΅λκ°
333 cout << "\n[4] μ¬λΌμ΄λ© μλμ° μ΅λκ°" << endl;
334 vector<int> window = {1, 3, -1, -3, 5, 3, 6, 7};
335 cout << " λ°°μ΄: [1,3,-1,-3,5,3,6,7], k=3" << endl;
336 cout << " μ΅λκ°: ";
337 printVector(maxSlidingWindow(window, 3));
338 cout << endl;
339
340 // 5. λ μ€νμΌλ‘ ν
341 cout << "\n[5] λ μ€νμΌλ‘ ν ꡬν" << endl;
342 MyQueue q;
343 q.push(1);
344 q.push(2);
345 cout << " push(1), push(2)" << endl;
346 cout << " peek(): " << q.peek() << endl;
347 cout << " pop(): " << q.pop() << endl;
348 cout << " empty(): " << (q.empty() ? "true" : "false") << endl;
349
350 // 6. μ΅μ μ€ν
351 cout << "\n[6] μ΅μ μ€ν" << endl;
352 MinStack ms;
353 ms.push(-2);
354 ms.push(0);
355 ms.push(-3);
356 cout << " push(-2), push(0), push(-3)" << endl;
357 cout << " getMin(): " << ms.getMin() << endl;
358 ms.pop();
359 cout << " pop() ν getMin(): " << ms.getMin() << endl;
360
361 // 7. 볡μ‘λ μμ½
362 cout << "\n[7] 볡μ‘λ μμ½" << endl;
363 cout << " | μ°μ° | μ€ν | ν | λ± |" << endl;
364 cout << " |--------------|-------|-------|-------|" << endl;
365 cout << " | push/enqueue | O(1) | O(1) | O(1) |" << endl;
366 cout << " | pop/dequeue | O(1) | O(1) | O(1) |" << endl;
367 cout << " | peek/front | O(1) | O(1) | O(1) |" << endl;
368
369 cout << "\n============================================================" << endl;
370
371 return 0;
372}