Bài 3. Ngăn xếp

Mô hình

GỒM 2 LOẠI

• Stack-ArrayList - Ngăn xếp cài đặt theo danh sách đặc

• Stack-LinkedList - Ngăn xếp cài đạt theo danh sách liên kết

Lý thuyết

Source Code

stach.h

CẤU TRÚC

#define Max_length 50
typedef struct{
    int Data[Max_length];
    int Top;
}Stack;

KHỞI TẠO NGĂN XẾP RỖNG

void makeNullStack(Stack *S){
    S->Top = Max_length;
}

HIỂN THỊ NGĂN XẾP

void displayStack(Stack S){
    for(int i = S.Top ; i < Max_length ; i++){
        printf("%d ",S.Data[i]);
    }
}

THÊM N PHẦN TỬ VÀO NGĂN XẾP

void inputStack(int n,Stack *S){
    for(int i = 0; i < n; i++){
        scanf("%d",&S->Data[S->Top-1]);
        S->Top--;
    }
}

THÊM X TẠI VỊ TRÍ P VÀO NGĂN XẾP

void insertStack(int x,int p,Stack *L){
    L->Data[p] = x;
    L->Top--;
}

XOÁ X TẠI VỊ TRÍ P TRONG NGĂN XẾP

void deleleStack_byPos(int p,Stack *S){
    for(int i = p; i > S->Top; i--){
        S->Data[i] = S->Data[i-1];
    }
    S->Top++;
}

XOÁ PHẦN TỬ X TRONG NGĂN XẾP

void deleteStack_byValue(int x,Stack *S){
    for(int i = S->Top ; i < Max_length ; i++){
        if(S->Data[i] == x){
            deleleStack_byPos(i,S);
        }
    }
}

TRẢ VỀ VỊ TRÍ ĐẦU TIÊN CỦA X TRONG NGĂN XẾP

int locateStack(int x,Stack S){
    for(int i = S.Top ; i < Max_length ; i++){
        if(S.Data[i] == x){
            return i;
        }
    }
    return -1;
}

KIỂM TRA X CÓ TRONG NGĂN XẾP

int memberStack(int x,Stack S){
    if(locateStack(x,S) != -1){
        return 1;
    }
    return 0;
}

TỐI ƯU NGĂN XẾP (`1 2 1` -> `1 2`)

void optimizeStack(Stack *S){
    int i = Max_length - 1;
    int j;
    while(i >= S->Top){
        j = i - 1;
        while (j >= S->Top){
            if(S->Data[i] == S->Data[j]){
                deleleStack_byPos(j,S);
            }
            else{
                j--;
            }
        }
        i--;
    }
}

CHUYỂN NGĂN XẾP QUA NGĂN XẾP MỚI

void changeStack(Stack S1,Stack *S){
    int size = Max_length;
    int i = Max_length - S1.Top;
    while (i > 0){
        insertStack(S1.Data[size - 1],S->Top - 1,S);
        size--;
        i--;
    }
}

GỘP 2 NGĂN XẾP THÀNH MỘT

void mergeList(Stack S1,Stack S2,Stack *S){
    changeStack(S1,S);
    changeStack(S2,S);
}

LỌC PHẨN TỬ CHẲN HOẶC LẺ QUA NGĂN XẾP MỚI

void filter_evenNumber(Stack S1,Stack *S){
    int j = S->Top - 1;
    int size = Max_length - S1.Top;
    for(int i = 0 ; i < size ; i++){
        if(S1.Data[j] % 2 == 0){
            insertStack(S1.Data[j],S->Top - 1,S);
        }
        j--;
    }
}

void filter_oddNumber(Stack S1,Stack *S){
    int j = S->Top - 1;
    int size = Max_length - S1.Top;
    for (int i = 0; i < size; i++){
        if(S1.Data[j] % 2 != 0){
            insertStack(S1.Data[j],S->Top - 1,S);
        }
        j--;
    }
}

TÍNH TRUNG BÌNH CỘNG PHẦN TỬ TRONG NGĂN XẾP

double averageStack(Stack S){
    int size = Max_length - S.Top;
    double sum = 0;
    double result;
    int j = S.Top;
    for (int i = 0; i < size; i++){
        sum += S.Data[j];
        j++;
    }
    result = sum / size;
    return result;
}