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 3Sách giáo khoa
Tài liệu tham khảo
Sách VNEN
Lớp 4Sách giáo khoa
Sách/Vở bài bác tập
Đề thi
Lớp 5Sách giáo khoa
Sách/Vở bài tập
Đề thi
Lớp 6Lớ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 7Sách giáo khoa
Sách/Vở bài bác tập
Đề thi
Chuyên đề và Trắc nghiệm
Lớp 8Sách giáo khoa
Sách/Vở bài tập
Đề thi
Chuyên đề & Trắc nghiệm
Lớp 9Sách giáo khoa
Sách/Vở bài tập
Đề thi
Chuyên đề & Trắc nghiệm
Lớp 10Sách giáo khoa
Sách/Vở bài tập
Đề thi
Chuyên đề & Trắc nghiệm
Lớp 11Sách giáo khoa
Sách/Vở bài tập
Đề thi
Chuyên đề & Trắc nghiệm
Lớp 12Sách giáo khoa
Sách/Vở bài bác tập
Đề thi
Chuyên đề và Trắc nghiệm
ITNgữ 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
int peek() return queuePhươ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
int enqueue(int data) if(isfull()) return 0; rear = rear + 1; queue
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
int dequeue() if(isempty()) return 0; int data = queue
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.