[DSA] Loại bỏ phần tử trùng lặp dùng Stack

Nguồn: Click here

Sử dụng cấu trúc dữ liệu Stack bằng mảng để tìm kiếm và xóa tất cả các phần tử trùng lặp trong một danh sách số nguyên

#include <stdio.h>

#define MAX_SIZE 100 // Kích thước tối đa của Stack

typedef struct {

int data[MAX_SIZE];

int top;

} Stack;

void push(Stack *s, int value) {

if (s->top == MAX_SIZE - 1) {

printf("Stack overflow!\n");

return;

}

s->top++;

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

}

int pop(Stack *s) {

if (s->top == -1) {

printf("Stack underflow!\n");

return -1;

}

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

s->top--;

return value;

}

void removeDuplicates(Stack *s) {

int temp[MAX_SIZE] = {0}; // Mảng tạm để lưu các giá trị xuất hiện

int count = 0; // Số lượng phần tử không trùng lặp

while (s->top != -1) {

int value = pop(s);

int exists = 0; // Biến đánh dấu giá trị đã tồn tại

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

if (temp[i] == value) {

exists = 1;

break;

}

}

if (!exists) {

temp[count++] = value;

}

}

// Đẩy lại các giá trị không trùng lặp vào Stack

for (int i = count - 1; i >= 0; i--) {

push(s, temp[i]);

}

}

void printStack(Stack s) {

printf("Stack: ");

for (int i = s.top; i >= 0; i--) {

printf("%d ", s.data[i]);

}

printf("\n");

}

int main() {

Stack s = { .top = -1 };

push(&s, 1);

push(&s, 2);

push(&s, 3);

push(&s, 2);

push(&s, 4);

push(&s, 3);

printStack(s);

removeDuplicates(&s);

printStack(s);

return 0;

}