Cơ Bản Nhưng Quan Trọng: Stack Và Queue

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)

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.

Xem thêm  PHIM LAN LĂNG VƯƠNG - TẬP 11 | PHIM KIẾM HIỆP LỒNG TIẾNG HOA NGỮ

( 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 với Stack và #include với Queue). Tuy nhiên chúng ta hoàn toàn có thể xây dựng được 2 cấu trúc dữ liệu này với các cấu trúc dữ liệu đơn giản đã biết như mảng (Array) hay danh sách liên kết đơn (Singly Linked List). Trong bài viết này mình sẽ trình bày cách xây dựng Stack và Queue sử dụng danh sách liên kết đơn (để hiểu hơn về danh sách liên kết đơn, bạn có thể đọc ở một blog mà mình đã từng chia sẻ: Bạn Hiểu Gì Về Danh Sách Liên Kết Đơn Trong C++ (codelearn.io)). Ở đây để đơn giản thì mình sẽ sử dụng kiểu dữ liệu số nguyên (int) cho dữ liệu của Stack và Queue.

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:

Xem thêm  [Android] Mời chia sẻ bộ gõ tiếng Việt anh em đang sử dụng và cảm nhận về nó | Tinh tế

Xem thêm: Top 7 ứng dụng chặn tin nhắn và cuộc gọi spam trên điện thoại Android – https://bem2.vn

  • 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.
Xem thêm  Pokemon Sun and Moon - Gameplay Walkthrough Part 1 - Alola Intro and Litten Starter! (Nintendo 3DS) | Tin tức game mới cập nhật tại Bem2

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 !

Rate this post

Bài viết liên quan

Để lại ý kiến của bạn:

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *