[DSA] Tìm phần tử nhỏ nhất dùng Stack

Để triển khai một ngăn xếp có thể trả về phần tử nhỏ nhất trong thời gian O(1), chúng ta có thể sử dụng hai ngăn xếp: một để lưu trữ các phần tử và một ngăn xếp khác để lưu trữ phần tử nhỏ nhất hiện tại. Ở đây không dùng tới vòng for để duyệt và kiểm tra các phần tử trong hàm get_min nên độ phức tạp thời gian là O(1)

#include <stdio.h>

#define MAX_SIZE 100

int stack[MAX_SIZE];

int min_stack[MAX_SIZE];

int top = -1;

int min_top = -1;

void push(int x) {

if (top >= MAX_SIZE - 1) {

printf("Stack Overflow\n");

return;

}

top++;

stack[top] = x;

if (min_top == -1 || x <= min_stack[min_top]) {

min_top++;

min_stack[min_top] = x;

}

}

void pop() {

if (top == -1) {

printf("Stack Underflow\n");

return;

}

if (stack[top] == min_stack[min_top]) {

min_top--;

}

top--;

}

int get_min() {

if (min_top == -1) {

printf("Stack is empty\n");

return -1;

}

return min_stack[min_top];

}

int main() {

push(3);

push(1);

push(4);

push(2);

push(5);

printf("Minimum element in stack: %d\n", get_min()); // Output: 1

pop();

pop();

printf("Minimum element in stack: %d\n", get_min()); // Output: 1

pop();

push(-5);

push(15);

printf("Minimum element in stack: %d\n", get_min()); // Output: -5

push(-25);

printf("Minimum element in stack: %d\n", get_min()); // Output: -25

pop();

push(-35);

printf("Minimum element in stack: %d\n", get_min()); // Output: -35

return 0;

}