🌱 Cấu trúc dữ liệu - Stack
Ở những bài trước, chúng ta có nói về Queue, một kiểu dữ liệu FIFO (First In First Out), dùng để lưu trữ và xử lý data theo kiểu xếp hàng, data nào đến trước sẽ được xử lý trước.
Một số bài toán sẽ cần chúng ta làm theo kiểu ngược lại, tức là phần tử nào đến trước thì sẽ được xử lý sau, giống như việc đặt sách vào thùng, cuốn sách nào đặt vào trước sẽ được lấy ra cuối cùng).
Stack (Data Structure) là một cấu trúc dữ liệu tuyến tính (linear data structure) hoạt động theo cơ chế LIFO (Last In First Out).
 |
| Stack Operations |
Stack này hoạt động giống như Stack Hardware, nhưng ở đây đối với DSA, chúng ta đang triển khai nó bằng Software.
👉 Các thành phần của Stack
> Stack Pointer / Top of Stack
Khái niệm này liên quan đến phần cứng, khi vị trí phần tử mới nhất (top of stack) sẽ cần phải được đánh dấu, Stack Pointer sẽ chứa thông tin về mặt địa chỉ của phần tử cuối cùng được đưa vào stack.
> Các loại Hardware Stack
Hardware Stack dựa vào 2 đặc điểm để phân loại Stack:
- Stack Pointer chứa địa chỉ của phần tử mới nhất trong Stack (Full) hay chứa địa chỉ ngay sau phần tử mới nhất đó (Empty).
- Khi Push phần tử vào Stack thì địa chỉ phần tử mới tăng hay giảm so với phần tử trước đó (Ascending / Descending).
 |
| Hardware Stack Type |
> Hoạt động của Stack
Stack xoay quanh 2 action chính là Push và Pop, khi triển khai chúng ta có thể thêm action Peek dùng khi lấy ra nhiều data (giống ý tưởng đã triển khai ở bài Queue).
👉 Triển khai Stack Data Structure trong C
Vẫn với cách tiếp cận quen thuộc khi triển khai các Data Structure, với Stack, chúng ta cũng chia ra làm 2 phase:
- Organize Data - Tổ chức Data
- Operations - Triển khai các thao tác với Stack (Push / Pop)
💬 Tổ chức Data cho Stack
Với Stack thì các phần tử không có quá nhiều sự ràng buộc, chỉ cần có cách để quản lý các phần tử có cùng kiểu dữ liệu và quản lý chúng liên tiếp nhau.
Ở đây dễ thấy chúng ta có thể quản lý bằng một Array hoặc một Linked List (Dynamic Stack). Để đơn giản hóa bài toán và tối ưu dung lượng bộ nhớ, bài viết này mình sẽ sử dụng Array để quản lý các phần tử của Stack.
Đối với Array thì chúng ta có thể quản lý Top of Stack bằng giá trị index của phần tử top.
> Triển khai theo kiểu tĩnh - cố định size Stack max.
#define MAX (10U)
typedef struct
{
uint32_t Data[MAX]; // Array contain Data
uint32_t Top;
} StackType;> Triển khai theo kiểu động - có thể tạo thêm Hàm Stack_Init() để khởi tạo Size.
typedef struct
{
uint32_t * pData; // Pointer point to Data Array in Heap
uint32_t Top;
uint32_t MAX;
} StackType;
💬 Các Operation với Stack
> Khởi tạo Stack
Dễ thấy khi khởi tạo, Stack sẽ không có phần tử nào, ở ví dụ này mình triển khai theo kiểu Empty - tức là vị trí của Top sẽ không chứa phần tử nào cả. Ban đầu khi chưa có data thì Top = 0 (index của mảng).
> Triển khai theo kiểu tĩnh
StackType Stack = { 0 };> Triển khai theo kiểu động
StackType Stack = { 0 }; void Stack_Init(uint32_t maxItem) { /* Allocate Memory for Stack Data */ Stack.pData = (uint32_t*)malloc(maxItem * sizeof(uint32_t)); Stack.Top = 0U; Stack.MAX = maxItem; }
> Push phần tử vào Stack
Với action Push, cần kiểm tra trước là Stack đã đầy hay chưa. Nếu Stack chưa đầy, chúng ta chỉ đơn giản là đưa Data cần Push vào vị trí index tiếp theo, rồi tăng phần tử Top lên 1 đơn vị.
StackStatus_t Stack_Push(uint32_t inputData)
{
StackStatus_t eStatus = STACK_OVERFLOW;
if( Stack.Top < Stack.MAX )
{
Stack.pData[Stack.Top++] = inputData;
eStatus = STACK_OK;
}
return eStatus;
}
> Pop phần tử khỏi Stack
Với action Pop thì cần kiểm tra xem Stack có phần tử nào để Pop hay không. Nếu có, lấy phần tử đó ra và giảm Top đi 1 đơn vị.
StackStatus_t Stack_Pop(uint32_t * pOutData)
{
StackStatus_t eStatus = STACK_EMPTY;
if( Stack.Top > 0U )
{
*pOutData = Stack.pData[--Stack.Top];
eStatus = STACK_OK;
}
return eStatus;
}
> Sample Code
void main() { uint32_t PopData; Stack_Init(3); printStack(); // Empty printf("push status = %d => ", Stack_Push(1)); // status = 0 = STACK_OK printStack(); // 1 printf("push status = %d => ", Stack_Push(2)); // status = 0 = STACK_OK printStack(); // 1 2 printf("push status = %d => ", Stack_Push(3)); // status = 0 = STACK_OK printStack(); // 1 2 3 printf("push status = %d => ", Stack_Push(4)); // status = 2 = STACK_OVERFLOW printStack(); // 1 2 3 printf("pop status = %d => ", Stack_Pop(&PopData)); // status = 0 = STACK_OK printf(" pop data = %d \n", PopData); // 3 printf("pop status = %d => ", Stack_Pop(&PopData)); // status = 0 = STACK_OK printf(" pop data = %d \n", PopData); // 2 printf("pop status = %d => ", Stack_Pop(&PopData)); // status = 0 = STACK_OK printf(" pop data = %d \n", PopData); // 1 printf("pop status = %d => ", Stack_Pop(&PopData)); // status = 1 = STACK_EMPTY printf(" pop data = %d \n", PopData); // 1 }Run This Code
🔻 Nhớ run debug nhé, kết quả sẽ như bên dưới!
Stack Data:
push status = 0 => Stack Data: 1
push status = 0 => Stack Data: 1 2
push status = 0 => Stack Data: 1 2 3
push status = 2 => Stack Data: 1 2 3
pop status = 0 => pop data = 3
pop status = 0 => pop data = 2
pop status = 0 => pop data = 1
pop status = 1 => pop data = 1 Phần tới mình sẽ triển khai một số bài toán sử dụng DSA Stack!
>>>= Follow ngay =<<<