Hàng đợi (Queue)
[/B]Cũng tương tự như stack, Quêu là một cấu trúc có nhiều nút trải dài từ đầu hàng đợi đến cuối hàng đợi - với hàng đợi chúng ta chỉ được phép thêm nút vào cuối hàng đợi và xóa nút ở đầu hàng đợi nghĩa là việc truy xuất các nút trên hàng đợi xảy ra ở cả hai đầu. Vì nút thêm vào trước sẽ được lấy ra trước nên cấu trúc hàng đợi còn được gọi là cấu trúc FIFO (Firt In First Out). Ví dụ như bạn đi mua vé xem phim với người iu chẳng hạn thì người mua xếp hàng trước sẽ được mua vé trước còn người mua xếp hàng sau thì sẽ mua vé sau.
Và hàng đợi để làm gì ???: Hàng đợi để giải quyết những vấn đề có cơ chế FIFO như dịch vụ quản lý kho, dịch vụ ngân hàng ....
Và sau đây là mô hình Queue-ADT
1. Mô tả dữ liệu:
Có nhiều nút cùng kiểu dữ liệu.
Có đầu hàng đợi (front) và cuối hàng đợi (tail)
2. Mô tả các tác vụ trên hàng đợi:
initialize:
Chức năng: Khởi động hàng đợi.
Dữ liệu nhập: không.
Dữ liệu xuất: front và tail được gán giá trị phù hợp.
empty:
Chức năng: Kiểm tra hàng đợi có bị rỗng không.
Dữ liệu nhập: không.
Dữ liệu xuất True or False. (true khi hàng đợi rỗng, false khi hàng đợi không rỗng)
insert:
Chức năng: thêm nút mới vào cuối hàng đợi.
Dữ liệu nhập: nút mới.
Điều kiện: hàng đợi không bị đầy.
Dữ liệu xuất: không.
remove:
Chức năng: xóa nút ở đầu hàng đợi.
Dữ liệu nhập: không.
Điều kiện: hàng đợi không bị rỗng.
Dữ liệu xuất: nút bị xóa.
queuefront:
Chức năng truy xuất nút ở đầu hàng đợi.
Dữ liệu nhập: không.
Điều kiện: hàng đợi không bị rỗng.
Dữ liệu xuất: nút tại đầu hàng đợi.
queuetail:
Chức năng truy xuất nút tại cuối hàng đợi.
Dữ liệu nhập: không.
Điều kiện: hàng đợi không bị rỗng.
Dữ liệu xuất: nút tại cuối hàng đợi.
queue size:
Chức năng: xác định số nút hiện có trong hàng đợi.
Dữ liệu nhập: không.
Dữ liệu xuất:số nút có trong hàng đợi.
clearqueue:
Chức năng: xóa tất cả các nút có trong hàng đợi.
Dữ liệu nhập: không.
Dữ liệu xuất: front và tail với giá trị phù hợp.
Các phương pháp cài đặt Queue-ADT
Cũng như stack chúng ta cài đặt hàng đợi theo hai cách là cài đặt kiểu kế tiếp (dùng mảng 1 chiều hoặc dùng mảng vòng) và cài đặt kiểu liên kết (dùng DSLK đơn, vòng, kép, kép+vòng và giống như stack thì cài đặt bằng DSLK kép+vòng là hay nhất).
Để đơn giản và dễ hiểu nhất thì tớ sẽ cài đặt bằng mảng 1 chiều. Minh họa bằng ngôn ngữ C++
const Max = 100;
class queue
{
private:
int front,tail; //dau va cuoi hang doi
int nodes[Max];
public:
queue() // cau tu khoi dong hang doi
{
front = 0;
tail = -1;
}
int empty(); // kiem tra hang doi bi rong khong
int full(); // kiem tra hang doi co bi day chua
void insert(int x); // them mot nut vao cuoi hang doi
int remove(); // xoa nut o dau hang doi
int queuesize(); // xac dinh so nut co trong hang doi
};
int queue::empty()
{
return ((tail < front) ? true : false);
}
int queue::full()
{
return ((tail == Max-1) ? true : false);
}
void queue::insert(int x)
{
if(full())
else
nodes[++tail] = x;
}
int queue::remove()
{
if(empty())
cout<<"hang doi bi rong"; else
return(nodes[front++]);
}
int queue::queuesize()
{
return(tail - front + 1);
}
Ngăn xếp và hàng đợi (Stack and Queue) - Nguyên tắc và cài đặt trên C++
Trả lời cùng với trích dẫn
Hàng đợi (Queue)
Nguyên bản được gửi bởi chuonggio_mailaniemdau
.Cám ơn mấy anh
