Ngăn xếp – Stack

Định nghĩa

Ngăn xếp là dạng đặc biệt của danh sách tuyến tính trong đó các đối tượng được nạp vào(push) và lấy ra (pop) chỉ từ 1 đầu được gọi là đỉnh (top) của ngăn xếp.

Nguyên tắc hoạt động : Vào sau – Ra trước (Last In – First out)
• Các phép toán cơ bản trên stack
– Push(object) : đẩy(nạp) 1 phần tử vào trong stack
– Pop() : loại bỏ và trả lại phần tử tại top của stack. Và đồng thời kích thước của stack giảm đi 1.
• Cách tổ chức ngăn xếp
– Sử dụng mảng
– Sử dụng danh sách liên kết.

Cài đặt ngăn xếp dùng mảng

Ta dùng 1 mảng S, lưu trữ các phần tử của stack bằng cách push các phần tử vào mảng lần lượt theo thứ tự từ trái sang phải theo hình vẽ.

Như trên hình vẽ mô tả ngăn xếp đã được nạp (push) N phần tử. Thao tác lấy (pop) rất đơn giản là trả về phần tử S[N-1], và đồng thời kích thước ngăn xếp sẽ giảm đi 1.
Với cách cài đặt ngăn xếp bằng mảng, khi pop phần tử, thì ta ko cần phải dồn mảng vì push và pop đều được thực hiện ở phần tử cuối.

• Khai báo stack

static int size;
int stack[100];

• Khởi tạo ngăn xếp

void initStack()
{
    size = -1;
}

• Nạp giá trị vào ngăn xếp

void push(int x)
{
    stack[++size] = x;
}

• Lấy giá trị khỏi ngăn xếp

int pop()
{
    return stack[size--];
}

• In ngăn xếp ra màn hình

void viewStack()
{
    int len = size; 
    if (len == -1)
    {
        printf("Stack is empty");
    }
    else
    {
        while(len > -1)
        {
            printf("%d\n", stack[len--]);
        } 
    }
}

Cài đặt ngăn xếp dùng danh sách liên kết

Trong cách cài đặt ngăn xếp dùng dslk, ngăn xếp được cài đặt như dslk với thao tác bổ sung (push) hay loại bỏ (pop) luôn làm việc với ô đầu tiên.

•  Khai báo stack

struct Node 
{
    int n;
    Node *pNext;
};
struct Stack
{
    Node *pTop;
};
Node *newNode(int k)
{
    Node *pNode;
    pNode = (Node*)malloc(1 * sizeof(Node));
    if (!pNode)
    {
        return NULL;
    }
    pNode->n = k;
    pNode->pNext = NULL;
    return pNode;
}

• Khởi tạo ngăn xếp

void initStack(Stack *s)
{
    s->pTop = NULL;
}

• Kiểm tra ngăn xếp rỗng

bool IsStackEmpty(Stack s)
{
    if(s == NULL)
        return false;
    else
        return true;
}

• Nạp giá trị vào ngăn xếp

bool push(Stack *s, Node *node)
{
    if (!node)
    {
        return false;
    }
    if (!s->pTop)
    {
        s->pTop = node;
    }
    else
    {
        node->pNext = s->pTop;
        s->pTop = node;
    }
    return true;
}

• Lấy giá trị khỏi ngăn xếp

bool pop(Stack *s, int *n)
{
    Node *pNode;
    if (isStackEmpty(*s))
    {
        *n = -1;
        return false;
    }
    *n = s->pTop->n;
    pNode = s->pTop;
    s->pTop = pNode->pNext;
    free(pNode);
    return true;
}

• In ngăn xếp ra màn hình

bool pop(Stack *s, int *n)
{
    Node *pNode;
    if (isStackEmpty(*s))
    {
        *n = -1;
        return false;
    }
    *n = s->pTop->n;
    pNode = s->pTop;
    s->pTop = pNode->pNext;
    free(pNode);
    return true;
}

 

Một số ứng dụng của ngăn xếp

Ứng dụng trực tiếp
• Lịch sử duyệt web
• Dãy Undo trong bộ soạn thảo văn bản
• Chains of method calls
• Kiểm tra tính hợp lệ của dấu ngoặc đơn trong biểu thức toán học
• Đổi cơ số
• Ứng dụng trong cài đặt chương trình Compiler. (Compiler implementation)
• Tính giá trị biểu thức toán học
• Quay lui (Backtracking)
• Khử đệ quy
…..
Ứng dụng gián tiếp
• Cấu trúc dữ liệu hỗ trợ cho các thuật toán
• Thành phần của các cấu trúc dữ liệu khác

Bài tập