[DSA] Kiểm tra một dãy có tăng dần dùng Stack
Để kiểm tra xem một dãy số có tăng dần hay không sử dụng cấu trúc dữ liệu Stack, chúng ta có thể sử dụng thuật toán sau:
- Khởi tạo một Stack rỗng.
- Duyệt từng phần tử của dãy số, thực hiện các bước sau:
- Nếu Stack rỗng hoặc phần tử đang xét lớn hơn hoặc bằng phần tử ở đỉnh Stack, thêm phần tử đang xét vào Stack.
- Nếu phần tử đang xét nhỏ hơn phần tử ở đỉnh Stack, dừng duyệt và trả về "Không tăng dần".
- Nếu duyệt hết toàn bộ dãy số mà không gặp trường hợp nào như trên, trả về "Tăng dần".
Sau đây là mã nguồn tham khảo:
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;
void initStack(Stack *s) {
s->top = -1;
}
int isEmpty(Stack *s) {
return s->top == -1;
}
int isFull(Stack *s) {
return s->top == MAX_SIZE - 1;
}
void push(Stack *s, int value) {
if (isFull(s)) {
printf("Stack is full.\n");
return;
}
s->top++;
s->data[s->top] = value;
}
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
return -1;
}
int value = s->data[s->top];
s->top--;
return value;
}
int isIncreasing(Stack *s, int *arr, int n) {
for (int i = 0; i < n; i++) {
if (isEmpty(s) || arr[i] >= s->data[s->top]) {
push(s, arr[i]);
} else {
return 0; // Không tăng dần
}
}
return 1; // Tăng dần
}
int main() {
int arr[] = {1, 2, 0, 3, 4, 5};
int n = sizeof(arr) / sizeof(int);
Stack s;
initStack(&s);
if (isIncreasing(&s, arr, n)) {
printf("The sequence is increasing.\n");
} else {
printf("The sequence is not increasing.\n");
}
return 0;
}
Không có nhận xét nào