1/*
2 * μ€νκ³Ό ν (Stack and Queue)
3 * Stack, Queue, Deque, Monotonic Stack
4 *
5 * κΈ°λ³Έ μλ£κ΅¬μ‘°μ μμ© μκ³ λ¦¬μ¦μ
λλ€.
6 */
7
8#include <stdio.h>
9#include <stdlib.h>
10#include <string.h>
11#include <stdbool.h>
12
13/* =============================================================================
14 * 1. μ€ν ꡬν
15 * ============================================================================= */
16
17typedef struct {
18 int* data;
19 int top;
20 int capacity;
21} Stack;
22
23Stack* stack_create(int capacity) {
24 Stack* s = malloc(sizeof(Stack));
25 s->data = malloc(capacity * sizeof(int));
26 s->top = -1;
27 s->capacity = capacity;
28 return s;
29}
30
31void stack_free(Stack* s) {
32 free(s->data);
33 free(s);
34}
35
36bool stack_is_empty(Stack* s) {
37 return s->top == -1;
38}
39
40bool stack_is_full(Stack* s) {
41 return s->top == s->capacity - 1;
42}
43
44void stack_push(Stack* s, int value) {
45 if (!stack_is_full(s)) {
46 s->data[++s->top] = value;
47 }
48}
49
50int stack_pop(Stack* s) {
51 if (!stack_is_empty(s)) {
52 return s->data[s->top--];
53 }
54 return -1;
55}
56
57int stack_peek(Stack* s) {
58 if (!stack_is_empty(s)) {
59 return s->data[s->top];
60 }
61 return -1;
62}
63
64/* =============================================================================
65 * 2. ν ꡬν (μν ν)
66 * ============================================================================= */
67
68typedef struct {
69 int* data;
70 int front;
71 int rear;
72 int size;
73 int capacity;
74} Queue;
75
76Queue* queue_create(int capacity) {
77 Queue* q = malloc(sizeof(Queue));
78 q->data = malloc(capacity * sizeof(int));
79 q->front = 0;
80 q->rear = -1;
81 q->size = 0;
82 q->capacity = capacity;
83 return q;
84}
85
86void queue_free(Queue* q) {
87 free(q->data);
88 free(q);
89}
90
91bool queue_is_empty(Queue* q) {
92 return q->size == 0;
93}
94
95bool queue_is_full(Queue* q) {
96 return q->size == q->capacity;
97}
98
99void queue_enqueue(Queue* q, int value) {
100 if (!queue_is_full(q)) {
101 q->rear = (q->rear + 1) % q->capacity;
102 q->data[q->rear] = value;
103 q->size++;
104 }
105}
106
107int queue_dequeue(Queue* q) {
108 if (!queue_is_empty(q)) {
109 int value = q->data[q->front];
110 q->front = (q->front + 1) % q->capacity;
111 q->size--;
112 return value;
113 }
114 return -1;
115}
116
117int queue_front(Queue* q) {
118 if (!queue_is_empty(q)) {
119 return q->data[q->front];
120 }
121 return -1;
122}
123
124/* =============================================================================
125 * 3. λ± κ΅¬ν (Double-ended Queue)
126 * ============================================================================= */
127
128typedef struct {
129 int* data;
130 int front;
131 int rear;
132 int size;
133 int capacity;
134} Deque;
135
136Deque* deque_create(int capacity) {
137 Deque* d = malloc(sizeof(Deque));
138 d->data = malloc(capacity * sizeof(int));
139 d->front = 0;
140 d->rear = 0;
141 d->size = 0;
142 d->capacity = capacity;
143 return d;
144}
145
146void deque_free(Deque* d) {
147 free(d->data);
148 free(d);
149}
150
151bool deque_is_empty(Deque* d) {
152 return d->size == 0;
153}
154
155void deque_push_front(Deque* d, int value) {
156 if (d->size < d->capacity) {
157 d->front = (d->front - 1 + d->capacity) % d->capacity;
158 d->data[d->front] = value;
159 d->size++;
160 }
161}
162
163void deque_push_back(Deque* d, int value) {
164 if (d->size < d->capacity) {
165 d->data[d->rear] = value;
166 d->rear = (d->rear + 1) % d->capacity;
167 d->size++;
168 }
169}
170
171int deque_pop_front(Deque* d) {
172 if (!deque_is_empty(d)) {
173 int value = d->data[d->front];
174 d->front = (d->front + 1) % d->capacity;
175 d->size--;
176 return value;
177 }
178 return -1;
179}
180
181int deque_pop_back(Deque* d) {
182 if (!deque_is_empty(d)) {
183 d->rear = (d->rear - 1 + d->capacity) % d->capacity;
184 d->size--;
185 return d->data[d->rear];
186 }
187 return -1;
188}
189
190int deque_front(Deque* d) {
191 if (!deque_is_empty(d)) {
192 return d->data[d->front];
193 }
194 return -1;
195}
196
197int deque_back(Deque* d) {
198 if (!deque_is_empty(d)) {
199 return d->data[(d->rear - 1 + d->capacity) % d->capacity];
200 }
201 return -1;
202}
203
204/* =============================================================================
205 * 4. κ΄νΈ κ²μ¬
206 * ============================================================================= */
207
208bool is_valid_parentheses(const char* s) {
209 Stack* stack = stack_create(strlen(s));
210
211 for (int i = 0; s[i]; i++) {
212 char c = s[i];
213 if (c == '(' || c == '{' || c == '[') {
214 stack_push(stack, c);
215 } else {
216 if (stack_is_empty(stack)) {
217 stack_free(stack);
218 return false;
219 }
220 char top = stack_pop(stack);
221 if ((c == ')' && top != '(') ||
222 (c == '}' && top != '{') ||
223 (c == ']' && top != '[')) {
224 stack_free(stack);
225 return false;
226 }
227 }
228 }
229
230 bool valid = stack_is_empty(stack);
231 stack_free(stack);
232 return valid;
233}
234
235/* =============================================================================
236 * 5. νμ νκΈ°μ κ³μ°
237 * ============================================================================= */
238
239int evaluate_postfix(const char* expr) {
240 Stack* stack = stack_create(strlen(expr));
241
242 for (int i = 0; expr[i]; i++) {
243 char c = expr[i];
244
245 if (c >= '0' && c <= '9') {
246 stack_push(stack, c - '0');
247 } else if (c == ' ') {
248 continue;
249 } else {
250 int b = stack_pop(stack);
251 int a = stack_pop(stack);
252 int result;
253
254 switch (c) {
255 case '+': result = a + b; break;
256 case '-': result = a - b; break;
257 case '*': result = a * b; break;
258 case '/': result = a / b; break;
259 default: result = 0;
260 }
261 stack_push(stack, result);
262 }
263 }
264
265 int result = stack_pop(stack);
266 stack_free(stack);
267 return result;
268}
269
270/* =============================================================================
271 * 6. λͺ¨λ
Έν λ μ€ν - λ€μμΌλ‘ ν° μμ
272 * ============================================================================= */
273
274int* next_greater_element(int arr[], int n) {
275 int* result = malloc(n * sizeof(int));
276 Stack* stack = stack_create(n);
277
278 for (int i = n - 1; i >= 0; i--) {
279 while (!stack_is_empty(stack) && stack_peek(stack) <= arr[i]) {
280 stack_pop(stack);
281 }
282 result[i] = stack_is_empty(stack) ? -1 : stack_peek(stack);
283 stack_push(stack, arr[i]);
284 }
285
286 stack_free(stack);
287 return result;
288}
289
290/* =============================================================================
291 * 7. μ¬λΌμ΄λ© μλμ° μ΅λκ° (λ± νμ©)
292 * ============================================================================= */
293
294int* sliding_window_max(int arr[], int n, int k, int* result_size) {
295 *result_size = n - k + 1;
296 int* result = malloc((*result_size) * sizeof(int));
297 Deque* dq = deque_create(n);
298
299 for (int i = 0; i < n; i++) {
300 /* μλμ° λ²μ λ° μ κ±° */
301 while (!deque_is_empty(dq) && deque_front(dq) <= i - k) {
302 deque_pop_front(dq);
303 }
304
305 /* νμ¬ κ°λ³΄λ€ μμ μμ μ κ±° */
306 while (!deque_is_empty(dq) && arr[deque_back(dq)] < arr[i]) {
307 deque_pop_back(dq);
308 }
309
310 deque_push_back(dq, i);
311
312 if (i >= k - 1) {
313 result[i - k + 1] = arr[deque_front(dq)];
314 }
315 }
316
317 deque_free(dq);
318 return result;
319}
320
321/* =============================================================================
322 * 8. νμ€ν κ·Έλ¨μμ κ°μ₯ ν° μ§μ¬κ°ν
323 * ============================================================================= */
324
325int largest_rectangle_histogram(int heights[], int n) {
326 Stack* stack = stack_create(n + 1);
327 int max_area = 0;
328
329 for (int i = 0; i <= n; i++) {
330 int h = (i == n) ? 0 : heights[i];
331
332 while (!stack_is_empty(stack) && heights[stack_peek(stack)] > h) {
333 int height = heights[stack_pop(stack)];
334 int width = stack_is_empty(stack) ? i : i - stack_peek(stack) - 1;
335 int area = height * width;
336 if (area > max_area) max_area = area;
337 }
338
339 stack_push(stack, i);
340 }
341
342 stack_free(stack);
343 return max_area;
344}
345
346/* =============================================================================
347 * ν
μ€νΈ
348 * ============================================================================= */
349
350void print_array(int arr[], int n) {
351 printf("[");
352 for (int i = 0; i < n; i++) {
353 printf("%d", arr[i]);
354 if (i < n - 1) printf(", ");
355 }
356 printf("]");
357}
358
359int main(void) {
360 printf("============================================================\n");
361 printf("μ€νκ³Ό ν (Stack and Queue) μμ \n");
362 printf("============================================================\n");
363
364 /* 1. μ€ν */
365 printf("\n[1] μ€ν κΈ°λ³Έ μ°μ°\n");
366 Stack* s = stack_create(10);
367 stack_push(s, 1);
368 stack_push(s, 2);
369 stack_push(s, 3);
370 printf(" Push: 1, 2, 3\n");
371 printf(" Top: %d\n", stack_peek(s));
372 printf(" Pop: %d\n", stack_pop(s));
373 printf(" Pop: %d\n", stack_pop(s));
374 stack_free(s);
375
376 /* 2. ν */
377 printf("\n[2] ν κΈ°λ³Έ μ°μ°\n");
378 Queue* q = queue_create(10);
379 queue_enqueue(q, 1);
380 queue_enqueue(q, 2);
381 queue_enqueue(q, 3);
382 printf(" Enqueue: 1, 2, 3\n");
383 printf(" Front: %d\n", queue_front(q));
384 printf(" Dequeue: %d\n", queue_dequeue(q));
385 printf(" Dequeue: %d\n", queue_dequeue(q));
386 queue_free(q);
387
388 /* 3. κ΄νΈ κ²μ¬ */
389 printf("\n[3] κ΄νΈ κ²μ¬\n");
390 printf(" '()[]{}': %s\n", is_valid_parentheses("()[]{}") ? "valid" : "invalid");
391 printf(" '([)]': %s\n", is_valid_parentheses("([)]") ? "valid" : "invalid");
392 printf(" '{[()]}': %s\n", is_valid_parentheses("{[()]}") ? "valid" : "invalid");
393
394 /* 4. νμ νκΈ°μ */
395 printf("\n[4] νμ νκΈ°μ κ³μ°\n");
396 printf(" '2 3 + 4 *' = %d\n", evaluate_postfix("2 3 + 4 *"));
397 printf(" '5 1 2 + 4 * + 3 -' = %d\n", evaluate_postfix("5 1 2 + 4 * + 3 -"));
398
399 /* 5. λ€μμΌλ‘ ν° μμ */
400 printf("\n[5] λ€μμΌλ‘ ν° μμ (λͺ¨λ
Έν λ μ€ν)\n");
401 int arr5[] = {4, 5, 2, 25};
402 int* nge = next_greater_element(arr5, 4);
403 printf(" λ°°μ΄: [4, 5, 2, 25]\n");
404 printf(" NGE: ");
405 print_array(nge, 4);
406 printf("\n");
407 free(nge);
408
409 /* 6. μ¬λΌμ΄λ© μλμ° μ΅λκ° */
410 printf("\n[6] μ¬λΌμ΄λ© μλμ° μ΅λκ°\n");
411 int arr6[] = {1, 3, -1, -3, 5, 3, 6, 7};
412 int result_size;
413 int* max_vals = sliding_window_max(arr6, 8, 3, &result_size);
414 printf(" λ°°μ΄: [1,3,-1,-3,5,3,6,7], k=3\n");
415 printf(" μ΅λκ°: ");
416 print_array(max_vals, result_size);
417 printf("\n");
418 free(max_vals);
419
420 /* 7. νμ€ν κ·Έλ¨ */
421 printf("\n[7] νμ€ν κ·Έλ¨ μ΅λ μ§μ¬κ°ν\n");
422 int heights[] = {2, 1, 5, 6, 2, 3};
423 printf(" λμ΄: [2,1,5,6,2,3]\n");
424 printf(" μ΅λ λμ΄: %d\n", largest_rectangle_histogram(heights, 6));
425
426 /* 8. μλ£κ΅¬μ‘° λΉκ΅ */
427 printf("\n[8] μλ£κ΅¬μ‘° λΉκ΅\n");
428 printf(" | μλ£κ΅¬μ‘° | μ½μ
| μμ | νΉμ§ |\n");
429 printf(" |----------|---------|---------|------------------|\n");
430 printf(" | μ€ν | O(1) | O(1) | LIFO |\n");
431 printf(" | ν | O(1) | O(1) | FIFO |\n");
432 printf(" | λ± | O(1) | O(1) | μμͺ½ μ½μ
/μμ |\n");
433
434 printf("\n============================================================\n");
435
436 return 0;
437}