[Powered by Google Translate] [Queue]
[Chris Gerber, Đại học Harvard]
Đây là CS50, CS50.TV]
Một cấu trúc dữ liệu hữu ích cho việc lưu trữ một bộ sưu tập lệnh của các yếu tố là một hàng đợi.
Nó được sử dụng khi những yếu tố cần phải được loại bỏ
theo thứ tự như chúng đã được thêm vào.
Khái niệm này được gọi là FIFO, mà là một từ viết tắt cho đầu tiên, ra trước.
Để giúp hình dung này, nó có thể hữu ích cho hình ảnh
một dòng tiền tại một cửa hàng.
Khi mọi người đến nơi, họ chờ đợi ở phía cuối hàng.
Thu ngân sau đó chờ đến lượt phục vụ khách hàng ở phía trước,
những người sau đó thoát khỏi một dòng tại một thời điểm.
Trong khoa học máy tính, chúng tôi đề cập phía trước của hàng đợi là người đứng đầu
và trở lại như đuôi.
Một ví dụ khi chúng ta có thể sử dụng điều này trong một ứng dụng
là một danh sách chờ đợi cho tuyển sinh lớp học.
Như chỗ ngồi trở nên có sẵn trong lớp,
người đứng đầu trong danh sách chờ đợi được cung cấp cơ hội để ghi danh vào lớp học.
>> Hàng đợi có thể được xây dựng bằng cách sử dụng bất kỳ bộ sưu tập
lưu trữ dữ liệu theo thứ tự, chẳng hạn như là một mảng hoặc một danh sách liên kết.
Cùng với bộ sưu tập để lưu trữ các mục trong hàng đợi,
chúng tôi cũng cần một phương pháp để thêm các mục vào cuối của hàng đợi,
được gọi là enqueuing,
và một để loại bỏ một mục từ người đứng đầu của hàng đợi,
được gọi là dequeuing.
Nó thường là hữu ích để bao gồm một phương pháp khác để trả lại chiều dài hiện tại của hàng đợi
cũng như một phương pháp để kiểm tra xem hàng đợi rỗng.
Chúng ta hãy xem làm thế nào chúng ta có thể thực hiện một danh sách các số nguyên trong C,
bằng cách sử dụng một mảng cho bộ sưu tập của các yếu tố.
Đầu tiên, chúng ta tạo ra một cấu trúc gọi là xếp hàng để giữ biến của chúng tôi.
Chúng tôi sẽ sử dụng một mảng kích thước cố định chỉ số 0 các số nguyên
để lưu trữ các yếu tố.
Chúng tôi cũng sẽ bao gồm một đầu được gọi là biến
mà các cửa hàng chỉ số của các yếu tố đó hiện ở phần đầu của hàng đợi.
Một biến thứ ba, được gọi là chiều dài, sẽ được sử dụng
để theo dõi số lượng các phần tử trong mảng.
Là một thay thế, bạn có thể xem xét việc sử dụng một biến gọi là đuôi
để trỏ đến các yếu tố lĩnh vực cuối cùng trong mảng.
Trước khi chúng tôi viết code nữa,
chúng ta hãy thử thiết kế của chúng tôi.
Hãy bắt đầu với một mảng rỗng có chiều dài 0,
với người đứng đầu thiết lập là 0.
Bây giờ chúng ta hãy enqueue 4 giá trị - 6, 2, 3, và 1
Chiều dài bây giờ sẽ là 4,
và người đứng đầu sẽ ở mức 0.
>> Điều gì sẽ xảy ra nếu chúng ta dequeue một giá trị?
Chúng tôi sẽ giảm bớt chiều dài đến 3,
thiết lập đầu đến 1,
và trả lại giá trị 6.
Đó là mã có thể trông như thế này.
Ở đây chúng tôi có chức năng dequeue,
trong đó có một con trỏ vào hàng đợi - q - và một con trỏ vào phần tử,
mà là một kiểu int.
Đầu tiên chúng ta kiểm tra độ dài của hàng đợi để chắc chắn rằng nó là nhiều hơn 0,
để đảm bảo rằng có một yếu tố để được dequeued.
Sau đó, chúng ta nhìn trong mảng yếu tố, ở đầu vị trí,
và thiết lập giá trị của các phần tử là giá trị ở vị trí đó.
Sau đó, chúng tôi thay đổi người đứng đầu là chỉ số tiếp theo
% Công suất.
Chúng tôi sau đó làm giảm chiều dài của hàng đợi bằng cách 1.
Cuối cùng, chúng ta trở lại đúng sự thật để cho biết rằng dequeue là thành công.
Nếu chúng ta dequeue một lần nữa, chiều dài sẽ trở thành 2,
người đứng đầu cũng sẽ trở thành 2,
và giá trị trả lại sẽ được 2.
>> Điều gì sẽ xảy ra nếu chúng ta enqueue một giá trị như một 7?
Khi chúng tôi vào cuối của hàng đợi,
chúng tôi sẽ cần để bọc xung quanh và lưu trữ các giá trị trong 0 phần tử của mảng.
Toán học, điều này có thể được đại diện bằng cách thêm chiều dài
các chỉ số của đầu
và thực hiện một modulus bằng cách sử dụng các năng lực hàng đợi.
Dưới đây là 2 +2, đó là 4% 4,
mà là 0.
Dịch ý tưởng này để mã chúng tôi có chức năng này.
Ở đây chúng ta thấy chức năng enqueue,
trong đó có một con trỏ vào hàng đợi - q -
và phần tử được enqueued, đó là một số nguyên.
Tiếp theo chúng ta kiểm tra để đảm bảo rằng dung lượng của hàng đợi
vẫn còn lớn hơn chiều dài hiện tại của hàng đợi.
Tiếp theo, chúng tôi lưu trữ các phần tử trong mảng các yếu tố
chỉ số được xác định bởi người đứng đầu + chiều dài% năng lực của hàng đợi.
Chúng tôi sau đó tăng chiều dài hàng đợi 1,
và sau đó trở lại đúng sự thật để cho biết rằng chức năng enqueue là thành công.
>> Ngoài hai chức năng mà chúng tôi đã đề cập,
có hai chức năng bổ sung.
Đầu tiên là chức năng isEmpty,
trong đó có một con trỏ vào hàng đợi
và xác minh rằng chiều dài là 0.
Thứ hai là chức năng chiều dài,
mà cũng có một con trỏ vào hàng đợi
và trả về độ dài hiện tại từ các cấu trúc.
Tóm tắt ngắn gọn này đã chứng minh một thực hiện có thể có của một hàng đợi.
Một trong những hạn chế để thực hiện điều này
là hàng đợi có kích thước tối đa cố định.
Nếu chúng ta cố gắng thêm nhiều yếu tố hơn so với các hàng đợi có thể tổ chức,
chúng tôi có thể cần phải bỏ qua các yêu cầu và thả các yếu tố,
hoặc chúng tôi có thể thích để trở lại một số loại lỗi.
Sử dụng một danh sách liên kết chứ không phải là một mảng
sẽ làm cho nó dễ dàng hơn với kích thước tự động hàng đợi.
Tuy nhiên, kể từ khi chúng tôi không có quyền truy cập trực tiếp đến các yếu tố của một danh sách liên kết,
nếu chúng ta không theo dõi của đuôi,
chúng tôi sẽ phải quét các danh sách liên kết toàn bộ để có được để kết thúc mỗi lần.
Chúng tôi cũng có thể xem xét việc sử dụng một mảng của các kiểu dữ liệu khác,
chẳng hạn như cấu trúc, để tạo ra các hàng đợi của các yếu tố phức tạp hơn.
Nghĩ lại ví dụ của chúng tôi một danh sách chờ lớp,
các cấu trúc này có thể đại diện cho các cá nhân học sinh.
>> Tên tôi là Chris Gerber, và điều này là CS50.
[CS50.TV]
Và trả về - >> Một lần nữa.
Và trở lại đúng sự thật để cho biết rằng hàng đợi đã thành công.
-% Năng lực của hàng đợi -
Nó sẽ được vui vẻ trong chỉnh sửa. [Cười]