Boong rỗng c ++

Hàm Deque empty() trong C++ kiểm tra container có rỗng hay không. Nếu vùng chứa trống, nó trả về 1 nếu không thì 0

cú pháp

tham số

Nó không chứa bất kỳ tham số nào

giá trị trả về

Nó không trả về bất kỳ giá trị nào

ví dụ 1

Hãy xem một ví dụ đơn giản khi deque không trống

đầu ra

Trong ví dụ này, hàm empty() xác định rằng deque không trống. Do đó, nó trả về false

Bên cạnh ngăn xếp, hàng đợi cũng là một cấu trúc dữ liệu hết sức thông tin. Ngoài ra, một biến có thể được coi là sự kết hợp của ngăn xếp và hàng đợi được ứng dụng phổ biến trong Các bài toán. Trong bài học ngày hôm nay, hãy cùng nhau đi tìm hiểu về queue và deque để xem no là gì nhé

Nội dung

Để có thể hiểu được bài học này một Cách tốt nhất, Các bạn nên có kiến ​​thức cơ bản về Các phần

Trong bài học ngày hôm nay, chúng ta sẽ tìm hiểu về

• Khái niệm hàng đợi và cách sử dụng
• Khái niệm deque và cách sử dụng

Khái niệm

Nếu như ngăn xếp là một cấu trúc dữ liệu dạng “vào sau, ra trước” (Last In First Out) thì queue là một cấu trúc dữ liệu dạng “vào trước, ra trước” (First In First Out), có nghĩa là tử nào được vào trong hàng đợi trước sẽ được ra trước

Một ví dụ minh họa thực tế nằm chính ở mười tiếng Việt của hàng đợi là hàng đợi. Hàng đợi giống như người xếp hàng mua vé vậy, người đến sau sẽ vào cuối hàng, người đến trước được mua vé trước và sau khi vé xong sẽ ra khỏi hàng để đến người tiếp theo

Một hàng đợi sẽ hỗ trợ các thao tác sau

• Thêm phần tử vào cuối hàng đợi
• Loại bỏ phần tử ở đầu hàng đợi
• Get the first element in queue
• Get size of queue

Use queue trong C++

Trong khóa học này, mình sẽ không giới thiệu Cách cài đặt hàng thủ công làm việc này sẽ khó khăn hơn so với ngăn xếp và gần như không có ứng dụng sử dụng trong biệt thự

hàng khai báo

Thông thường để thêm hàng đợi vào chương trình, chúng tôi sẽ thêm thư viện như sau

#bao gồm

Tuy nhiên, trong suốt khóa học này, mình sẽ sử dụng tiêu đề sau

#bao gồm

Tiêu đề này sẽ giúp chúng tôi bổ sung tất cả các thư viện về Cấu trúc dữ liệu cấu trúc mà chúng tôi sẽ học trong khóa học này

Ta will khai báo queue as after

queue <{kiểu dữ liệu}> {tên queue};

Thấy bạn. queuemyQueue;

Các phương thức cơ bản của hàng đợi

Hàng đợi trong C++ sẽ hỗ trợ các phương thức sau

• đẩy. Thêm phần tử vào cuối hàng đợi
• nhạc pop. Loại bỏ phần tử ở đầu hàng đợi
• đổi diện. Trả về giá trị là phần tử đầu tiên trong hàng đợi
• kích thước. Return to the integer is size of queue
• trống rỗng. Trả về giá trị bool, true nếu hàng đợi rỗng, sai nếu hàng đợi không rỗng

Các phương thức trên đều biến dạng phức tạp O(1)

Lưu ý. Cũng giống như ngăn xếp, Phương thức pop và front khi được gọi phải đảm bảo hàng đợi không trống nếu không sẽ gây ra Lỗi thời gian chạy. Do đó, nếu không chắc chắn, Các bạn cần kiểm tra bằng phương thức trống trước khi gọi hai phương thức này

Ở đây mình có đoạn mã demo Các phương thức cơ bản của hàng đợi

#include
using namespace std;

queue q;

int main(){
    // Thêm các phần tử vào queue
    q.push(1);
    q.push(3);
    q.push(5);
    // Lúc này, queue là [1, 3, 5]

    // In ra phần tử đầu tiên trong queue
    cout << "Phan tu dau tien trong queue la: " << q.front() << endl;
    // In ra kích thước của queue
    cout << "Kich thuoc cua queue la: " << q.size() << endl;

    // Loại bỏ phần tử đầu tiên ra khỏi queue
    cout << "Loai bo phan tu dau trong queue" << endl;
    q.pop();
    // Khi này queue là [3, 5]

    // Kiểm tra queue có rỗng hay không
    if(q.empty()) cout << "Queue rong" << endl;
    else cout << "Queue khong rong" << endl;

    // In ra phần tử đầu tiên trong queue
    cout << "Phan tu dau tien trong queue la: " << q.front() << endl;
    // In ra kích thước của queue
    cout << "Kich thuoc cua queue la: " << q.size() << endl;
}

Khi chạy đoạn mã trên, ta thu được kết quả

Khái niệm

Trong bài học trước, mình đã giới thiệu về ngăn xếp, cấu trúc dữ liệu cho phép thêm dữ liệu ở cuối và lấy dữ liệu ở cuối. Vừa rồi, mình đã giới thiệu thêm cho Các bạn về hàng đợi, một cấu trúc dữ liệu cho phép thêm dữ liệu ở cuối và lấy dữ liệu ở đầu. Do đó, cấu trúc dữ liệu không thể kết hợp Các tính chất của ngăn xếp và hàng đợi hay không?

Deque là viết tắt của hàng đợi hai đầu, có nghĩa là hàng đợi hai đầu. Một deque sẽ hỗ trợ các phương thức sau

• Add an element on the end deque
• Add an element to start deque
• Remove the death section at end deque
• Bỏ đi phần tử ở đầu deque
• Get the first deque value
• Get the end of the end of value

Use deque in C++

Giống như hàng đợi, việc cài đặt deque thủ công tương đối phức tạp và không cần thiết nên mình sẽ không hướng dẫn bạn cài đặt thégạn cài đặt đ

cỗ khai bảo

Thông thường để thêm deque vào chương trình, chúng tôi sẽ thêm thư viện như sau

#bao gồm

Tuy nhiên, trong suốt khóa học này, mình sẽ sử dụng tiêu đề sau

#bao gồm

Tiêu đề này sẽ giúp chúng tôi bổ sung tất cả các thư viện về Cấu trúc dữ liệu cấu trúc mà chúng tôi sẽ học trong khóa học này

Ta will tuyên bố deque as after

deque <{kiểu dữ liệu}> {tên deque};

Thấy bạn. dequemyDeque;

Các phương thức cơ bản của deque

Deque trong C++ sẽ hỗ trợ các phương thức cơ bản sau

• đẩy_front. Thêm phần tử vào deque đầu
• đẩy lùi. Add phần tử vào cuối deque
• pop_front. Loại bỏ phần tử ở đầu deque
• pop_back. Loại bỏ phần tử ở cuối deque
• đổi diện. Return to value is the head in deque
• mặt sau. Return to value is the end of the end of the deque
• kích thước. Return to the integer value is size of deque
• trống rỗng. Trả về giá trị bool, true nếu deque rỗng, false nếu deque không rỗng

Các phương thức trên đều biến dạng phức tạp O(1)

Lưu ý. Cũng như Các cấu trúc dữ liệu khác, Các phương thức pop_front, pop_back, front, back when. Do đó, nếu không chắc chắn, Các bạn cần kiểm tra bằng phương thức trống trước khi gọi Các phương thức trên

Ở đây mình có đoạn code demo về The method of deque as sau

#include
using namespace std;

deque dq;

int main(){
    // Thêm 3, 6 vào cuối deque
    dq.push_back(3);
    dq.push_back(6);
    // Lúc này deque là [3, 6]
    // Thêm 4 vào đầu deque
    dq.push_front(4);
    // Lúc này deque là [4, 3, 6]
    // Thêm 1 vào đầu deque
    dq.push_front(1);
    // Lúc này deque là [1, 4, 3, 6]

    cout << "Kich thuoc cua deque la: " << dq.size() << endl;
    cout << "Phan tu dau tien trong deque la: " << dq.front() << endl;
    cout << "Phan tu cuoi cung trong deque la: " << dq.back() << endl;

    cout << "Xoa bo phan tu cuoi deque" << endl;
    dq.pop_back();
    // Lúc này deque là [1, 4, 3]

    cout << "Kich thuoc cua deque la: " << dq.size() << endl;
    cout << "Phan tu dau tien trong deque la: " << dq.front() << endl;
    cout << "Phan tu cuoi cung trong deque la: " << dq.back() << endl;

    cout << "Xoa bo phan tu dau deque" << endl;
    dq.pop_front();
    // Lúc này deque là [4, 3]

    cout << "Kich thuoc cua deque la: " << dq.size() << endl;
    cout << "Phan tu dau tien trong deque la: " << dq.front() << endl;
    cout << "Phan tu cuoi cung trong deque la: " << dq.back() << endl;
}

Khi chạy đoạn mã trên ta thu được kết quả sau

Ứng dụng trong thực tế của queue và deque

Khi học bài này, bạn sẽ thấy lạ. Tại sao mình không nêu ra một bài toán ban đầu rồi suy luận để cấu trúc dữ liệu như trong bài trước?

Hàng đợi được áp dụng trong Thuật toán thiên về yếu tố cần duyệt và lưu trữ Các trạng thái, điển hình cho dạng thuật toán như vậy là loang và BFS. Đối với deque, thuật toán ứng dụng quan trọng nhất là tìm kiếm min-max trên đoạn tiến trình. Các thuật toán trên đều sẽ có trong khóa học này của mình. Khi đi đến thuật toán đó, mình sẽ hướng dẫn các bạn Cách sử dụng cụ thể

Tất nhiên, queue và deque sẽ có thể áp dụng trong Các bài toán khác. Đánh vào tính chất của bài toán và tính chất của queue và deque, Các bạn có thể sử dụng chúng linh hoạt sao cho phù hợp

Kết luận

Thứ tư bài này chúng ta đã nắm được về queue và deque

Bài sau chúng ta sẽ bắt đầu tìm hiểu về cấu trúc danh sách liên kết dữ liệu

Cảm ơn Các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc đóng góp ý kiến ​​của mình để phát triển bài viết tốt hơn. Đừng dập tắt “Luyện tập – Thử thách – Không sợ khó”

Thảo luận

Nếu bạn thấy khó khăn hay thắc mắc điều gì về khóa học, sợ đặt cam hỏi trong phần lui dưới đáy hoặc trong mục hỏi & đap trên thư bảo vệ của howkteam. com to get the support from the community