Bài viết sẽ trình bày về 2 cấu trúc dữ liệu khá cơ bản nhưng cực kì quan trong lập trình là Stack và Queue, về cách cài đặt cũng như ứng dụng của 2 cấu trúc dữ liệu này trên thực tế.
Mục lục bài viết
Stack và Queue là gì?
Stack (ngăn xếp) là một cấu trúc dữ liệu hoạt động theo nguyên tắc LIFO (Last In First Out), vào sau ra trước. Để dễ hình dung thì nó giống với hình ảnh 1 chông sách, tuy nhiên chồng sách này phải tuân theo một quy tắc đó là khi thêm một cuốn sách mới vào chồng thì phải thêm vào phía trên chồng sách và khi lấy sách ra cũng phải lấy từ phía trên.
(link ảnh: VisuAlgo – Linked List (Single, Doubly), Stack, Queue, Deque)
Bạn đang đọc: Cơ Bản Nhưng Quan Trọng: Stack Và Queue
Tương tự như Stack, Queue (hàng đợi) cũng là một cấu trúc dữ liệu. Về hình ảnh của Queue thì chính tên gọi đã giúp ta tưởng tượng ra nó. Chúng ta có thể hình dung đó là hình ảnh một hàng người đang xếp hàng để mua pizza, và dĩ nhiên tính chất của hàng người này đó là ai đến trước thì được mua trước(dĩ nhiên sẽ có trường hợp có người được ưu tiên mua trước, tuy nhiên chúng ta sẽ nói đến trường hợp này ở một bài viết khác về hàng đợi ưu tiên).
( link ảnh : Hundreds of students queue up to get không lấy phí Domino’s pizza | Daily Mail Online )
Chính vì vậy Queue hoạt động theo nguyên tắc FIFO (First In First Out), vào trước ra trước.
( link ảnh : https://en.wikipedia.org/wiki/Network_scheduler )
Cài đặt:
Để sử dụng Stack và Queue, chúng ta có thể sử dụng các thư viện hỗ trợ có sẵn của C++(#include
struct Node{
int data;
Node* next;
}; Stack:
- Push(): Thêm 1 phần tử vào Stack. Hàm này tương tự với hàm thêm 1 phần tử vào đầu danh sách liên kết đơn, dĩ nhiên các bạn cũng có thể xây dựng giống với hàm thêm phần tử vào cuối danh sách liên kết đơn. Tuy nhiên, khi xây dựng như vậy thì hàm Pop(), tương ứng với hàm Push() ấy cũng phải là hàm xóa phần tử ở cuối danh sách, và việc này yêu cầu chi phí là O(n), trong khi hàm xóa 1 phần tử ở đầu danh sách(ứng với hàm xây dựng bên dưới) chỉ là O(1).
node *top = NULL; // dùng biến top để kiểm soát Stack
void Push(int data)
{
Node* temp;
temp = new Node;
//Trường hợp không cấp phát được bộ nhớ cho temp
if (!temp)
{
cout << "\nHeap Overflow";
exit(1);
}
//Thêm temp vào đỉnh Stack, cập nhập lại biến top
temp->data = data;
temp->link = top;
top = temp;
} - Pop(): Xóa 1 phần tử trong Stack. Tương tự với hàm xóa 1 phần tử ở đầu danh sách liên kết đơn.
void Pop()
{
Node* temp;
//Kiểm tra trường hợp Stack rỗng
if (top == NULL)
{
cout << "\nStack Underflow" << endl;
exit(1);
}
else
{
//xóa phần tử ở top, cập nhập lại top
temp = top;
top = top->link;
temp->link = NULL;
delete temp;
}
} - isEmpty(): Kiểm tra Stack có rỗng hay không.
int isEmpty()
{
return top == NULL;
}- Peek(): Trả ra giá trị của phần tử ở đỉnh Stack.
int Peek()
{
if (!isEmpty())
return top->data;
else
exit(1);
}Queue:
- enQueue(): Thêm 1 phần tử vào Queue, tương tự với hàm thêm 1 phần tử vào cuối danh sách liên kết đơn. Còn lí do mình chọn thêm vào cuối chứ không phải vào đầu thì lí do tương tự với lí do mình đã nói ở hàm Push() của phần Stack ở trên.
Node* front = NULL, rear = NULL;// dùng 2 biến front và rear để kiểm soát queue.
void enQueue(int x)
{
Node* temp;
temp = new Node;
//Trường hợp không cấp phát được bộ nhớ cho temp
if (!temp)
{
cout << "\nHeap Overflow";
exit(1);
}
temp->data = x;
temp->next = NULL;
//Trường hợp Queue đang rỗng.
if (rear == NULL)
{
front = rear = temp;
return;
}
//Thêm phần tử vào Queue, cập nhập lại rear
rear->next = temp;
rear = temp;
} - deQueue(): Xóa 1 phần tử trong Queue, tương tự với hàm xóa 1 phần tử ở đầu danh sách liên kết đơn.
void deQueue()
{
//Trường hợp Queue rỗng.
if (front == NULL)
return;
Node* temp = front;
front = front->next;
//Trường hợp ban đầu Queue chỉ có 1 phần tử
if (front == NULL)
rear = NULL;
delete temp;
} Ứng dụng:
Stack:
- Khử đệ quy.
- Chuyển infix sang postfix (tham khảo ở đây: Stack | Set 2 (Infix to Postfix) – GeeksforGeeks )
- Chuyển infix sang prefix (tham khảo ở đây: Convert Infix To Prefix Notation – GeeksforGeeks)
- Kiểm tra dãy ngoặc đúng(tham khảo ở đây: Check for Balanced Brackets in an expression (well-formedness) using Stack – GeeksforGeeks)
- …
- Bên cạnh đó, 1 ứng dụng rất dễ thấy của Stack là lệnh Undo(Ctrl + Z) bạn sử dụng trong Word hay 1 số chương trình khác, các lệnh bạn thực thi sẽ được lưu trong một cấu trúc tương tự Stack, và khi bạn thực thi lệnh Undo, các lệnh trong Stack sẽ lần lượt được lấy ra.
Queue:
- Thuật toán Breadth First Search
- Bộ đệm, chứa các yêu cầu cần xử lí theo thứ tự vào trước thì xử lí trước.
- …
Kết luận:
Trên đây là những san sẻ của mình về 2 kiểu tài liệu Stack và Queue. Hi vọng sau bài viết này những bạn sẽ có 1 cái nhìn tổng quan về 2 kiểu tài liệu trên. Hẹn gặp lại những bạn trong những bài viết tiếp theo !
Source: https://bem2.vn
Category: Ứng dụng hay
