Lớp 1

Lớp 2

Lớp 2 - kết nối tri thức

Lớp 2 - Chân trời sáng tạo

Lớp 2 - Cánh diều

Tài liệu tham khảo

Lớp 3

Sách giáo khoa

Tài liệu tham khảo

Sách VNEN

Lớp 4

Sách giáo khoa

Sách/Vở bài bác tập

Đề thi

Lớp 5

Sách giáo khoa

Sách/Vở bài tập

Đề thi

Lớp 6

Lớp 6 - liên kết tri thức

Lớp 6 - Chân trời sáng tạo

Lớp 6 - Cánh diều

Sách/Vở bài xích tập

Đề thi

Chuyên đề & Trắc nghiệm

Lớp 7

Sách giáo khoa

Sách/Vở bài bác tập

Đề thi

Chuyên đề và Trắc nghiệm

Lớp 8

Sách giáo khoa

Sách/Vở bài tập

Đề thi

Chuyên đề & Trắc nghiệm

Lớp 9

Sách giáo khoa

Sách/Vở bài tập

Đề thi

Chuyên đề & Trắc nghiệm

Lớp 10

Sách giáo khoa

Sách/Vở bài tập

Đề thi

Chuyên đề & Trắc nghiệm

Lớp 11

Sách giáo khoa

Sách/Vở bài tập

Đề thi

Chuyên đề & Trắc nghiệm

Lớp 12

Sách giáo khoa

Sách/Vở bài bác tập

Đề thi

Chuyên đề và Trắc nghiệm

IT

Ngữ pháp giờ Anh

Lập trình Java

Phát triển web

Lập trình C, C++, Python

Cơ sở dữ liệu


*

Cấu trúc tài liệu và giải thuậtMột số quan niệm về Giải thuật kết cấu dữ liệu mảng (Array)Danh sách liên kết - Linked ListsNgăn xếp và Hàng đợiMột số lời giải tìm kiếmMột số giải thuật sắp xếpCấu trúc tài liệu đồ thị (Graph)Cấu trúc dữ liệu câyĐệ qui (Recursion)Tài liệu xem thêm
Cấu trúc dữ liệu hàng hóng (Queue)
Trang trước
Trang sau

Cấu trúc dữ liệu hàng ngóng (Queue) là gì ?

Hàng hóng (Queue) là một cấu tạo dữ liệu trừu tượng, là một cái nào đấy tương tự như hàng hóng trong đời sống hàng ngày (xếp hàng).

*

Khác với chống xếp, hàng ngóng là mở ở cả hai đầu. Một đầu luôn luôn luôn được áp dụng để chèn tài liệu vào (hay còn gọi là sắp vào hàng) với đầu cơ được áp dụng để xóa dữ liệu (rời hàng). Cấu trúc dữ liệu hàng đợi tuân theo phương pháp First-In-First-Out, có nghĩa là dữ liệu được nhập vào thứ nhất sẽ được truy cập đầu tiên.

Bạn đang xem: Hàng đợi queue là gì? cấu trúc dữ liệu và cài đặt queue

Trong đời sống thực chúng ta có tương đối nhiều ví dụ về mặt hàng đợi, chẳng hạn như hàng xe pháo ô tô trên đường một chiều (đặc biệt là lúc tắc xe), trong các số đó xe làm sao vào đầu tiên sẽ bay ra đầu tiên. Một vài ví dụ khác là xếp hàng học sinh, xếp hàng mua vé, …

Biểu diễn kết cấu dữ liệu hàng ngóng (Queue)

Giờ thì có lẽ rằng bạn đã tưởng tượng ra hàng đợi là gì rồi. Chúng ta cũng có thể truy cập cả nhị đầu của sản phẩm đợi. Dưới đó là biểu diễn hàng ngóng dưới dạng kết cấu dữ liệu:

*

Tương tự như cấu trúc dữ liệu phòng xếp, thì cấu trúc dữ liệu hàng hóng cũng có thể được tiến hành bởi sử dụng Mảng (Array), Danh sách links (Linked List), nhỏ trỏ (Pointer) và kết cấu (Struct). Để đơn giản, phần tiếp theo chúng ta sẽ khám phá tiếp về hàng chờ được tiến hành bởi sử dụng mảng một chiều.


Các chuyển động cơ bạn dạng trên cấu tạo dữ liệu mặt hàng đợi

Các hoạt động trên kết cấu dữ liệu hàng đợi rất có thể liên quan lại tới bài toán khởi chế tạo ra hàng đợi, sử dụng tài liệu trên hàng chờ và tiếp nối là xóa tài liệu khỏi cỗ nhớ. List dưới đây là một số hoạt động cơ phiên bản có thể tiến hành trên kết cấu dữ liệu hàng đợi:

Hoạt đụng enqueue(): thêm (hay lưu giữ trữ) một trong những phần tử vào trong mặt hàng đợi.

Hoạt rượu cồn dequeue(): xóa 1 phần tử từ mặt hàng đợi.

Để thực hiện hàng đợi một cách hiệu quả, họ cũng yêu cầu kiểm tra tâm lý của sản phẩm đợi. Để phục vụ cho mục tiêu này, dưới đấy là một số tính năng hỗ trợ khác của hàng đợi:

Phương thức peek(): lấy thành phần ở đầu mặt hàng đợi, mà lại không xóa thành phần này.

Phương thức isFull(): chất vấn xem hàng hóng là đầy hay không.

Phương thức isEmpty(): kiểm soát xem hàng đợi là trống xuất xắc hay không.

Trong cấu trúc dữ liệu sản phẩm đợi, họ luôn luôn: (1) dequeue (xóa) tài liệu được trỏ bởi con trỏ front cùng (2) enqueue (nhập) dữ liệu vào trong hàng đợi bởi vì sự giúp đỡ của nhỏ trỏ rear.

Trong phần tiếp bọn họ sẽ tò mò về những tính năng cung cấp của kết cấu dữ liệu hàng đợi:

Phương thức peek() của cấu trúc dữ liệu hàng đợi

Giống như trong kết cấu dữ liệu ngăn xếp, hàm này giúp chúng ta quan sát tài liệu tại đầu sản phẩm đợi. Giải thuật của hàm peek() là:

bắt đầu hàm peek return queue dứt hàmSự thực thi của hàm peek() trong ngôn từ C:

int peek() return queue;

Phương thức isFull() trong kết cấu dữ liệu mặt hàng đợi

Nếu khi bọn họ đang thực hiện mảng một chiều để xúc tiến hàng đợi, họ chỉ bắt buộc kiểm tra nhỏ trỏ rear tất cả tiến mang lại giá trị MAXSIZE hay là không để xác minh hàng chờ là đầy tuyệt không. Vào trường hợp thực hiện hàng hóng bởi thực hiện Danh sách link vòng (Circular Linked List), giải mã cho hàm isFull() đã khác.

Phần dưới đây là giải thuật của hàm isFull():

bắt đầu hàm isfull if rear equals to lớn MAXSIZE return true else return false endif hoàn thành hàmSự triển khai lời giải của hàm isFull() trong ngôn từ C:

bool isfull() if(rear == MAXSIZE - 1) return true; else return false;

Phương thức isEmpty() trong cấu trúc dữ liệu sản phẩm đợi

Giải thuật của hàm isEmpty():

bắt đầu hàm isempty if front là bé dại hơn MIN OR front là to hơn rear return true else return false ngừng if dứt hàmNếu giá trị của front là nhỏ hơn MIN hoặc 0 thì có nghĩa là hàng ngóng vẫn không được khởi tạo, chính vì như vậy hàng đợi là trống.

Dưới đây là sự thực thi code trong ngôn ngữ C:

bool isempty() if(front rear) return true; else return false;

Hoạt hễ enqueue trong kết cấu dữ liệu sản phẩm đợi

Bởi vì cấu tạo dữ liệu mặt hàng đợi bảo trì hai bé trỏ dữ liệu: front với rear, cho nên các hoạt động vui chơi của loại kết cấu dữ liệu này là khá phức tạp khi so sánh với cấu tạo dữ liệu phòng xếp.

Dưới phía trên là công việc để enqueue (chèn) dữ liệu vào trong hàng đợi:

Bước 1: kiểm tra xem hàng chờ là bao gồm đầy không.

Bước 2: ví như hàng chờ là đầy, quy trình bị lỗi với bị thoát.

Bước 3: ví như hàng chờ không đầy, tăng bé trỏ rear để trỏ cho tới vị trí bộ nhớ trống tiếp theo.

Bước 4: thêm bộ phận dữ liệu vào vị trí nhỏ trỏ rear sẽ trỏ tới trong hàng đợi.

Bước 5: trả về success.

*

Đôi khi họ cũng phải kiểm tra coi hàng đợi đã được khởi tạo ra hay không để giải pháp xử lý các trường hợp không mong đợi.

Giải thuật cho vận động enqueue trong cấu trúc dữ liệu sản phẩm đợi

bắt đầu enqueue(data) if queue là đầy return overflow endif rear ← rear + 1 queue ← data return true xong hàmSự triển khai lời giải của vận động enqueue() trong ngôn ngữ C:

int enqueue(int data) if(isfull()) return 0; rear = rear + 1; queue = data; return 1;kết thúc hàmĐể theo dõi sự xúc tiến code đầy đủ của các vận động trên trong ngôn từ C, mời bạn bấm vào vào chương: Hàng ngóng trong C.

Hoạt hễ dequeue trong cấu trúc dữ liệu hàng đợi

Việc truy vấn dữ liệu từ hàng đợi là một trong tiến trình gồm hai tác vụ: truy cập dữ liệu trên nơi con trỏ front đã trỏ tới cùng xóa dữ liệu sau thời điểm đã truy cập đó. Dưới đây là các bước để thực hiện hoạt động dequeue:

Bước 1: kiểm tra xem hàng chờ là trống giỏi không.

Bước 2: trường hợp hàng đợi là trống, tiến trình bị lỗi với bị thoát.

Bước 3: trường hợp hàng hóng không trống, truy vấn dữ liệu tại nơi con trỏ front sẽ trỏ.

Bước 4: tăng nhỏ trỏ front để trỏ tới vị trí chứa thành phần tiếp theo.

Bước 5: trả về success.

*

Giải thuật cho hoạt động dequeue

bắt đầu hàm dequeue if queue là trống return underflow over if data = queue front ← front + 1 return truekết thúc hàmSự triển khai vận động dequeue() trong ngôn ngữ C:

int dequeue() if(isempty()) return 0; int data = queue; front = front + 1; return data;Để quan sát và theo dõi sự xúc tiến code tương đối đầy đủ của các chuyển động trên trong ngôn ngữ C, mời bạn bấm vào vào chương: Hàng chờ trong C.

Lưu trữ hàng đợi

Lưu trữ sau đó dung mảng

*

Lưu trữ sử dụng list móc nối

*

Đã có app fkhorizont-turnovo.com trên điện thoại, giải bài xích tập SGK, SBT soạn văn, Văn mẫu, Thi online, bài bác giảng....miễn phí. Thiết lập ngay ứng dụng trên android và iOS.

Xem thêm: Bản Ghost Là Gì, Tác Dụng Và Khi Nào Cần Thực Hiện Việc Ghost Win


*

*

Follow fanpage của team https://www.facebook.com/fkhorizont-turnovo.comteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.fkhorizont-turnovo.com để thường xuyên theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... Mới nhất của bọn chúng tôi.