1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Queue]

2
00:00:02,000 --> 00:00:05,000
[Chris Gerber, Đại học Harvard]

3
00:00:05,000 --> 00:00:07,000
Đây là CS50, CS50.TV]

4
00:00:07,000 --> 00:00:11,000
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.

5
00:00:11,000 --> 00:00:14,000
Nó được sử dụng khi những yếu tố cần phải được loại bỏ

6
00:00:14,000 --> 00:00:16,000
theo thứ tự như chúng đã được thêm vào.

7
00:00:16,000 --> 00:00:20,000
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.

8
00:00:20,000 --> 00:00:23,000
Để giúp hình dung này, nó có thể hữu ích cho hình ảnh

9
00:00:23,000 --> 00:00:25,000
một dòng tiền tại một cửa hàng.

10
00:00:25,000 --> 00:00:28,000
Khi mọi người đến nơi, họ chờ đợi ở phía cuối hàng.

11
00:00:28,000 --> 00:00:31,000
Thu ngân sau đó chờ đến lượt phục vụ khách hàng ở phía trước,

12
00:00:31,000 --> 00:00:34,000
những người sau đó thoát khỏi một dòng tại một thời điểm.

13
00:00:34,000 --> 00:00:37,000
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

14
00:00:37,000 --> 00:00:39,000
và trở lại như đuôi.

15
00:00:39,000 --> 00:00:41,000
Một ví dụ khi chúng ta có thể sử dụng điều này trong một ứng dụng

16
00:00:41,000 --> 00:00:44,000
là một danh sách chờ đợi cho tuyển sinh lớp học.

17
00:00:44,000 --> 00:00:46,000
Như chỗ ngồi trở nên có sẵn trong lớp,

18
00:00:46,000 --> 00:00:50,000
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.

19
00:00:50,000 --> 00:00:53,000
>> 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

20
00:00:53,000 --> 00:00:57,000
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.

21
00:00:57,000 --> 00:01:00,000
Cùng với bộ sưu tập để lưu trữ các mục trong hàng đợi,

22
00:01:00,000 --> 00:01:02,000
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,

23
00:01:02,000 --> 00:01:04,000
được gọi là enqueuing,

24
00:01:04,000 --> 00:01:07,000
và một để loại bỏ một mục từ người đứng đầu của hàng đợi,

25
00:01:07,000 --> 00:01:09,000
được gọi là dequeuing.

26
00:01:09,000 --> 00:01:14,000
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

27
00:01:14,000 --> 00:01:17,000
cũng như một phương pháp để kiểm tra xem hàng đợi rỗng.

28
00:01:17,000 --> 00:01:20,000
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,

29
00:01:20,000 --> 00:01:23,000
bằng cách sử dụng một mảng cho bộ sưu tập của các yếu tố.

30
00:01:23,000 --> 00:01:27,000
Đầ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.

31
00:01:27,000 --> 00:01:30,000
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

32
00:01:30,000 --> 00:01:33,000
để lưu trữ các yếu tố.

33
00:01:33,000 --> 00:01:35,000
Chúng tôi cũng sẽ bao gồm một đầu được gọi là biến

34
00:01:35,000 --> 00:01:39,000
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.

35
00:01:39,000 --> 00:01:42,000
Một biến thứ ba, được gọi là chiều dài, sẽ được sử dụng

36
00:01:42,000 --> 00:01:45,000
để theo dõi số lượng các phần tử trong mảng.

37
00:01:45,000 --> 00:01:48,000
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

38
00:01:48,000 --> 00:01:51,000
để trỏ đến các yếu tố lĩnh vực cuối cùng trong mảng.

39
00:01:51,000 --> 00:01:53,000
Trước khi chúng tôi viết code nữa,

40
00:01:53,000 --> 00:01:55,000
chúng ta hãy thử thiết kế của chúng tôi.

41
00:01:55,000 --> 00:01:58,000
Hãy bắt đầu với một mảng rỗng có chiều dài 0,

42
00:01:58,000 --> 00:02:02,000
với người đứng đầu thiết lập là 0.

43
00:02:02,000 --> 00:02:11,000
Bây giờ chúng ta hãy enqueue 4 giá trị - 6, 2, 3, và 1

44
00:02:11,000 --> 00:02:14,000
Chiều dài bây giờ sẽ là 4,

45
00:02:14,000 --> 00:02:17,000
và người đứng đầu sẽ ở mức 0.

46
00:02:17,000 --> 00:02:20,000
>> Điều gì sẽ xảy ra nếu chúng ta dequeue một giá trị?

47
00:02:20,000 --> 00:02:24,000
Chúng tôi sẽ giảm bớt chiều dài đến 3,

48
00:02:24,000 --> 00:02:28,000
thiết lập đầu đến 1,

49
00:02:28,000 --> 00:02:33,000
và trả lại giá trị 6.

50
00:02:33,000 --> 00:02:36,000
Đó là mã có thể trông như thế này.

51
00:02:36,000 --> 00:02:38,000
Ở đây chúng tôi có chức năng dequeue,

52
00:02:38,000 --> 00:02:41,000
trong đó có một con trỏ vào hàng đợi - q - và một con trỏ vào phần tử,

53
00:02:41,000 --> 00:02:44,000
mà là một kiểu int.

54
00:02:44,000 --> 00:02:47,000
Đầ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,

55
00:02:47,000 --> 00:02:50,000
để đảm bảo rằng có một yếu tố để được dequeued.

56
00:02:50,000 --> 00:02:54,000
Sau đó, chúng ta nhìn trong mảng yếu tố, ở đầu vị trí,

57
00:02:54,000 --> 00:02:58,000
và thiết lập giá trị của các phần tử là giá trị ở vị trí đó.

58
00:02:58,000 --> 00:03:01,000
Sau đó, chúng tôi thay đổi người đứng đầu là chỉ số tiếp theo

59
00:03:01,000 --> 00:03:04,000
% Công suất.

60
00:03:04,000 --> 00:03:07,000
Chúng tôi sau đó làm giảm chiều dài của hàng đợi bằng cách 1.

61
00:03:07,000 --> 00:03:12,000
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.

62
00:03:12,000 --> 00:03:19,000
Nếu chúng ta dequeue một lần nữa, chiều dài sẽ trở thành 2,

63
00:03:19,000 --> 00:03:24,000
người đứng đầu cũng sẽ trở thành 2,

64
00:03:24,000 --> 00:03:32,000
và giá trị trả lại sẽ được 2.

65
00:03:32,000 --> 00:03:35,000
>> Điều gì sẽ xảy ra nếu chúng ta enqueue một giá trị như một 7?

66
00:03:35,000 --> 00:03:37,000
Khi chúng tôi vào cuối của hàng đợi,

67
00:03:37,000 --> 00:03:47,000
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.

68
00:03:47,000 --> 00:03:50,000
Toán học, điều này có thể được đại diện bằng cách thêm chiều dài

69
00:03:50,000 --> 00:03:52,000
các chỉ số của đầu

70
00:03:52,000 --> 00:03:55,000
và thực hiện một modulus bằng cách sử dụng các năng lực hàng đợi.

71
00:03:55,000 --> 00:04:00,000
Dưới đây là 2 +2, đó là 4% 4,

72
00:04:00,000 --> 00:04:02,000
mà là 0.

73
00:04:02,000 --> 00:04:05,000
Dịch ý tưởng này để mã chúng tôi có chức năng này.

74
00:04:05,000 --> 00:04:08,000
Ở đây chúng ta thấy chức năng enqueue,

75
00:04:08,000 --> 00:04:10,000
trong đó có một con trỏ vào hàng đợi - q -

76
00:04:10,000 --> 00:04:14,000
và phần tử được enqueued, đó là một số nguyên.

77
00:04:14,000 --> 00:04:18,000
Tiếp theo chúng ta kiểm tra để đảm bảo rằng dung lượng của hàng đợi

78
00:04:18,000 --> 00:04:21,000
vẫn còn lớn hơn chiều dài hiện tại của hàng đợi.

79
00:04:21,000 --> 00:04:24,000
Tiếp theo, chúng tôi lưu trữ các phần tử trong mảng các yếu tố

80
00:04:24,000 --> 00:04:30,000
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.

81
00:04:30,000 --> 00:04:33,000
Chúng tôi sau đó tăng chiều dài hàng đợi 1,

82
00:04:33,000 --> 00:04:39,000
và sau đó trở lại đúng sự thật để cho biết rằng chức năng enqueue là thành công.

83
00:04:39,000 --> 00:04:42,000
>> Ngoài hai chức năng mà chúng tôi đã đề cập,

84
00:04:42,000 --> 00:04:44,000
có hai chức năng bổ sung.

85
00:04:44,000 --> 00:04:46,000
Đầu tiên là chức năng isEmpty,

86
00:04:46,000 --> 00:04:48,000
trong đó có một con trỏ vào hàng đợi

87
00:04:48,000 --> 00:04:51,000
và xác minh rằng chiều dài là 0.

88
00:04:51,000 --> 00:04:53,000
Thứ hai là chức năng chiều dài,

89
00:04:53,000 --> 00:04:55,000
mà cũng có một con trỏ vào hàng đợi

90
00:04:55,000 --> 00:04:58,000
và trả về độ dài hiện tại từ các cấu trúc.

91
00:04:58,000 --> 00:05:03,000
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.

92
00:05:03,000 --> 00:05:06,000
Một trong những hạn chế để thực hiện điều này

93
00:05:06,000 --> 00:05:08,000
là hàng đợi có kích thước tối đa cố định.

94
00:05:08,000 --> 00:05:11,000
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,

95
00:05:11,000 --> 00:05:14,000
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ố,

96
00:05:14,000 --> 00:05:17,000
hoặc chúng tôi có thể thích để trở lại một số loại lỗi.

97
00:05:17,000 --> 00:05:20,000
Sử dụng một danh sách liên kết chứ không phải là một mảng

98
00:05:20,000 --> 00:05:22,000
sẽ làm cho nó dễ dàng hơn với kích thước tự động hàng đợi.

99
00:05:22,000 --> 00:05:26,000
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,

100
00:05:26,000 --> 00:05:28,000
nếu chúng ta không theo dõi của đuôi,

101
00:05:28,000 --> 00:05:32,000
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.

102
00:05:32,000 --> 00:05:35,000
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,

103
00:05:35,000 --> 00:05:39,000
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.

104
00:05:39,000 --> 00:05:42,000
Nghĩ lại ví dụ của chúng tôi một danh sách chờ lớp,

105
00:05:42,000 --> 00:05:45,000
các cấu trúc này có thể đại diện cho các cá nhân học sinh.

106
00:05:45,000 --> 00:05:48,000
>> Tên tôi là Chris Gerber, và điều này là CS50.

107
00:05:48,000 --> 00:05:51,000
[CS50.TV]

108
00:05:51,000 --> 00:05:55,000
Và trả về - >> Một lần nữa.

109
00:05:55,000 --> 00:06:00,000
Và trở lại đúng sự thật để cho biết rằng hàng đợi đã thành công.

110
00:06:00,000 --> 00:06:03,000
-% Năng lực của hàng đợi -

111
00:06:03,000 --> 00:06:06,000
Nó sẽ được vui vẻ trong chỉnh sửa. [Cười]