Cấu trúc dữ liệu và thuật toán | Ngăn xếp (Stack) ~ TÀI LIỆU BÁCH KHOA

Cấu trúc dữ liệu và thuật toán | Ngăn xếp (Stack)

8/27/2023 trannguyenhan

1. Cấu trúc dữ liệu ngăn xếp và ứng dụng

Ngăp xếp là một dạng cấu trúc dữ liệu mà ở đó các thao tác với CTDL này chỉ diễn ra ở một đầu, được gọi là đỉnh của ngăn xếp (top). Hai thao tác phổ biến đối với ngăn xếp là đẩy vào (push) và lấy ra (pop), cả hai thao tác này đều tác động vào đỉnh của ngăn xếp.

Nguyên tắc của ngăn xếp: Vào trước ra sao, First-In Last-Out (FILO)

Có 2 cách cài đặt ngăn xếp là sử dụng mảng hoặc sử dụng con trỏ.

Mặc dù nhìn bề ngoài ngăn xếp có vẻ trông đơn giản nhưng nó lại có ứng dụng rất lớn trong thực tế. Ứng dụng trong sử dụng điều hướng các màn hình của điện thoại, ví dụ chúng ta đang ở một màn hình Settings của Facebook, Khi bấm vào General sẽ bị chuyển hướng sang một màn khác, vậy thì làm sao để khi bấm quay lại có thể quay lại đúng màn Settings một cách nhanh nhất? Đó chính là vứt nó vào ngăn xếp, mỗi khi bấm quay lại chỉ cần lấy nó ra từ đỉnh của ngăn xếp là được. Một số các ứng dụng khác của ngăn xếp như là lịch sử trình duyệt, hay là các cơ chế Undo (Redo) trong các trình soạn thảo văn bản.

Ngăn xếp còn rất quan trọng trong việc giải một số bài toán như:

- Tính giá trị biểu thức trung tố, hậu tố

- Bài toán cộng hai số lớn

- Bài toán kiểm tra ngoặc đúng

- Bài toán đảo ngược xâu

2. Cài đặt ngăn xếp sử dụng mảng

Khai báo một struct Stack và viết các hàm tương ứng với các phép toán trên ngăn xếp:

- isFull(stack): kiểm tra xem ngăn xếp đã đầy chưa

- isEmpty(stack): kiểm tra ngăn xếp có rỗng không

- push(stack, item): thêm phần tử vào ngăn xếp

- pop(stack): lấy phần tử ra khỏi ngăn xếp

- getTop(stack): xem phần tử ở đầu ngăn xếp và không xóa phần tử đó khỏi ngăn xếp

Tùy thuộc vào từng bài toán, khi cần thêm những chức năng cụ thể nào cho ngăn xếp thì chúng ta có thể viết thêm các hàm tương ứng để công việc được thực hiện một cách dễ dàng hơn.

#define INT_MIN -2147483648

struct Stack {
    int top;
    unsigned capacity;
    int* array;
};


// Khoi tao ngan xep
struct Stack* createStack(unsigned capacity){
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*) malloc(stack->capacity * sizeof(int));
}

// Kiem tra xem ngan xep day chua
int isFull(struct Stack* stack){
    return stack->top == stack->capacity - 1;
}

// Kiem tra ngan xep rong khong
int isEmpty(struct Stack* stack){
    return stack->top == -1;
}

// Them phan tu vao stack
void push(struct Stack* stack, int item){
    if(isFull(stack)){
        return;
    }

    stack->array[++stack->top] = item;
    printf("%d push to stack\n", item);
}

int pop(struct Stack* stack){
    if(isEmpty(stack)){
        return INT_MIN;
    }

    return stack->array[stack->top--];
}

int getTop(struct Stack* stack){
    if(isEmpty(stack)){
        return INT_MIN;
    }

    return stack->array[stack->top];
}

int main(){
    struct Stack* stack = createStack(10);
    push(stack, 2);
    push(stack, 3);
    printf("Top of value in stack: %d", getTop(stack));

}

3. Cài đặt ngăn xếp sử dụng con trỏ

Với con trỏ thì chúng ta cũng cài đặt tương tự các hàm so với cài đặt ngăn xếp sử dụng mảng.

#include <stdio.h>

struct Node {
    int data;
    struct Node* next;
};

struct Node* newNode(int val){
    struct Node* newN = (struct Node*) malloc(sizeof(struct Node));
    newN->data = val;
    newN->next = NULL;

    return newN;
}

void push(struct Node* head, int val){
    struct Node* newN = newNode(val);
    if(head == NULL){
        newN->next = NULL;
    } else {
        newN->next = head;
    }

    head = newN;

    printf("Top of stack is %d\n", head->data);
    printf("----------------\n");
}

int pop(struct Node* head){
    if(head == NULL){
        printf("Stack is empty\n");
        return;
    }

    int item = head->data;
    struct Node* tmp = head;
    head = head->next;
    free(tmp);

    printf("Top of stack is %d\n", head->data);
    return item;
}

int isEmpty(struct Node* head){
    return head == NULL;
}

int getTop(struct Node* head){
    if(head == NULL){
        return NULL;
    }

    return head->data;
}

int main(){
    struct Node* head = NULL;
    push(head, 10);
    pop(head);

    //printf("Top stack: %d", getTop(head));
}

Xem đầy đủ code tại repo github: https://github.com/piandhust/data-structures/blob/main/stack.c, https://github.com/piandhust/data-structures/blob/main/stack_pointer.c

8/27/2023