🌱 Cấu trúc dữ liệu - Monotonic Stack
Ở bài viết trước chúng ta đã cùng tìm hiểu về cấu trúc dữ liệu Stack, cách hoạt động và triển khai một Stack cơ bản bằng ngôn ngữ lập trình C. Đối với một số trường hợp, stack cần lưu trữ & xử lý data theo một thứ tự nhất định (tăng dần hoặc giảm dần), kiểm soát data lớn nhất hoặc nhỏ nhất, chúng ta có Monotonic Stack. Cùng mình đi vào bài toán dưới đây để làm rõ hơn vấn đề trên.
👉 Bài toán - View ngắm hoàng hôn
(Bài này khá nổi tiếng và mình cũng chỉ tham khảo trên trang Medium.com): Có một tập hợp các tòa nhà với chiều cao được cho ở mảng bên dưới, các tòa đứng sát nhau nên nếu tòa cao hơn sẽ hạn chế tầm nhìn của tòa thấp hơn khi ngắm hoàng hôn. Mặt trời sẽ lặn bên phía tay phải (index cao nhất của mảng). Nhiệm vụ là tìm những ngôi nhà có thể ngắm được hoàng hôn.
uint8_t buildings[] = {18, 14, 13, 16, 12}; Nhìn qua về mặt logic thì thấy ngay, tòa 18 là cao nhất nên không bị tòa nào che chắn và có thể ngắm hoàng hôn, tòa 12 là tòa đầu tiên nên cũng không bị chắn, tòa 16 cũng như vậy, chỉ có tòa 14 và 13 là bị tòa 16 chắn tầm nhìn. Đáp án expect sẽ là [18, 16, 12] hoặc theo index [0, 3, 4].
Ý tưởng, dễ thấy với bài toán này chúng ta cần xét từng phần tử trong mảng, và lưu trữ lại các phần tử hợp lệ theo một thứ tự nhất định (theo chiều cao giảm dần).
- Lưu trữ giá trị 18.
- 14 < 18 nên cả 2 đều được giữ lại, lưu trữ giá trị 14.
- 13 < 14 nên cả 2 đều được giữ lại, lưu trữ giá trị 13.
- 16 > 14 > 13 nên 2 giá trị 14 và 13 sẽ bị loại bỏ, lưu trữ giá trị 16.
- 12 < 16 nên cả 2 đều được giữ lại.
- Cuối cùng chúng ta còn lại [18, 16, 12].
➤ Và trên đây chính là ý tưởng chính của Monotonic Stack.
- Hoạt động cơ bản sẽ là Push/Pop giống như Stack.
- Đảm bảo các phần tử trong Stack sẽ luôn sắp xếp tăng hoặc giảm.
- Khi Push, nếu phần tử ở vị trí phù hợp rồi thì push như Stack thông thường, nếu chưa phù hợp (Ví dụ số 16 ở Step 4 ở trên), thì các phần tử cản trở phần tử này sẽ bị Pop ra khỏi Stack (số 14 và 13).
👉 Triển khai Monotonic Stack bằng ngôn ngữ lập trình 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 Monotonic Stack
Monotonic Stack có cách tổ chức Data tương tự như Stack, ở đây mình sẽ dùng cách cấp phát động và thêm một phần tử là tăng hay giảm để quy định về cách sắp xếp dữ liệu trong Stack.
typedef enum
{
STACK_MONO_ASC,
STACK_MONO_DESC,
} eMonoStackType;
typedef struct
{
uint32_t *pData; // Pointer point to Data Array in Heap
uint32_t Top;
uint32_t MAX;
eMonoStackType eType;
} MonoStackType;
💬 Các Operation với Monotonic Stack
> Khởi tạo Monotonic 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).
MonoStackType sMonoStack = { 0U }; void MonoStack_Init(uint32_t maxItem, eMonoStackType eStackType) { /* Allocate Memory for Stack Data */ sMonoStack.pData = (uint32_t*)malloc(maxItem * sizeof(uint32_t)); sMonoStack.Top = 0U; sMonoStack.MAX = maxItem; sMonoStack.eType = eStackType; }
> Push phần tử vào Stack
Khác với Stack thông thường, Monotonic Stack vẫn có thể Pop thêm data vào Stack kể cả khi nó đã đầy. Nó chỉ Overflow khi mà đã đầy và phần từ push vào không phù hợp.
Với trường hợp có thể push được, chúng ta cần tiếp tục kiểm tra xem phần tử push vào đã đứng đúng vị trí hay chưa.
Ví dụ với bài toán trên, cần Init Stack với kiểu là STACK_MONO_DESC. Nên khi push một phần tử, chúng ta cần kiểm tra lần lượt xem phần tử nào nhỏ hơn hoặc bằng phần tử cần Push, sẽ bị pop khỏi Stack. Sau đó mới Push phần tử mới này vào.
StackStatus_t MonoStack_Push(uint32_t inputData)
{
StackStatus_t eStatus = STACK_OVERFLOW;
uint32_t Idx = 0U;
/* Search the position for new element */
for( Idx = 0U; Idx < sMonoStack.Top; Idx++ )
{
if( (sMonoStack.pData[Idx] <= inputData && STACK_MONO_DESC == sMonoStack.eType) \
|| (sMonoStack.pData[Idx] >= inputData && STACK_MONO_ASC == sMonoStack.eType) \
)
{
/* Searching is PAUSE and push new element to stack */
sMonoStack.pData[Idx] = inputData;
sMonoStack.Top = Idx+1;
break;
}
}
/* Case Stack is Full and New Element is not mapping */
if( Idx == sMonoStack.MAX )
{
eStatus = STACK_OVERFLOW;
}
/* First Element is added
or Case No Element is poped from stack, push new to last */
else if( Idx == sMonoStack.Top )
{
sMonoStack.pData[sMonoStack.Top++] = inputData;
eStatus = STACK_OK;
}
else /* Normal Case */
{
eStatus = STACK_OK;
}
return eStatus;
}
> Pop phần tử khỏi Stack
Với action Pop thì tương tự như Stack thông thường, 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
uint8_t buildings[] = {18, 14, 13, 16, 12};
void main()
{
uint32_t Idx;
uint32_t numofBuilding = sizeof(buildings)/sizeof(buildings[0]);
MonoStack_Init(numofBuilding, STACK_MONO_DESC);
for( Idx = 0U; Idx < numofBuilding; Idx++ )
{
MonoStack_Push(buildings[Idx]);
}
printStack(); // expect = [18, 16, 12]
}
Run This Code
🔻 Nhớ run debug nhé, kết quả sẽ như bên dưới!
Stack Data: 18 16 12 Khi có ý tưởng và triển khai được Monotonic Stack, bạn cũng có thể làm tương tự với Monotonic Queue ở một số dạng bài toán khác.
>>>= Follow ngay =<<<
Để nhận được những bài học miễn phí mới nhất nhé 😊
Chúc các bạn học tập tốt 😊