[DSA] Tìm cặp số dùng Stack

 Viết chương trình C để tìm tất cả các cặp số trong một mảng sao cho số đầu tiên nhỏ hơn số thứ hai, sử dụng cấu trúc dữ liệu Stack.

• Tạo một Stack rỗng và duyệt qua từng phần tử trong mảng:
• Nếu Stack không rỗng và phần tử hiện tại lớn hơn giá trị ở đỉnh của Stack thì lấy phần tử ở đỉnh của Stack ra và in ra cặp số đó.
• Đẩy phần tử hiện tại vào Stack.

Sau khi duyệt qua toàn bộ mảng, ta sẽ có được tất cả các cặp số thỏa điều kiện.

#include <stdio.h>

#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {

int data[MAX_SIZE];

int top;

} Stack;

void init(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");

exit(1);

}

s->data[++s->top] = value;

}

int pop(Stack *s) {

if (isEmpty(s)) {

printf("Stack is empty\n");

exit(1);

}

return s->data[s->top--];

}

void findPairs(int arr[], int n) {

Stack s;

init(&s);

for (int i = 0; i < n; i++) {

while (!isEmpty(&s) && arr[i] > s.data[s.top]) {

int top = pop(&s);

printf("(%d, %d)\n", top, arr[i]);

}

push(&s, arr[i]);

}

}

int main() {

int arr[] = {5, 6, 2, 3, 4, 1};

int n = sizeof(arr) / sizeof(arr[0]);

findPairs(arr, n);

return 0;

}