1
00:00:00,000 --> 00:00:05,204

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Vì vậy, nếu bạn đã
xem video trên stack,

3
00:00:07,370 --> 00:00:09,870
này có lẽ sẽ cảm thấy
như một chút của deja vu.

4
00:00:09,870 --> 00:00:13,850
Đó sẽ là một khái niệm rất tương tự,
chỉ với một thay đổi nhỏ trên đó.

5
00:00:13,850 --> 00:00:15,530
Chúng ta sẽ nói bây giờ về hàng đợi.

6
00:00:15,530 --> 00:00:19,350
Vì vậy, một hàng đợi, tương tự như một chồng,
là một loại cấu trúc dữ liệu

7
00:00:19,350 --> 00:00:22,412
rằng chúng ta có thể sử dụng để duy trì
dữ liệu một cách có tổ chức.

8
00:00:22,412 --> 00:00:24,120
Tương tự như một chồng,
nó có thể được thực hiện

9
00:00:24,120 --> 00:00:27,000
như là một mảng hoặc một danh sách liên kết.

10
00:00:27,000 --> 00:00:30,320
Không giống như một chồng, các quy tắc
mà chúng tôi sử dụng để xác định

11
00:00:30,320 --> 00:00:34,210
khi mọi thứ được thêm vào và lấy ra từ
một hàng đợi là một chút khác nhau.

12
00:00:34,210 --> 00:00:36,590
>> Không giống như một chồng, mà
là một cấu trúc LIFO,

13
00:00:36,590 --> 00:00:45,610
kéo vào, ra đầu tiên, một hàng đợi là một FIFO
cấu trúc, FIFO, đầu vào, đầu ra.

14
00:00:45,610 --> 00:00:49,320
Bây giờ hàng đợi, bạn có thể
có một tương tự để xếp hàng.

15
00:00:49,320 --> 00:00:52,820
Nếu bạn đã từng đứng xếp hàng tại
công viên giải trí hoặc tại một ngân hàng,

16
00:00:52,820 --> 00:00:56,430
có sắp xếp của một sự công bằng
thực hiện cơ cấu.

17
00:00:56,430 --> 00:00:59,160
Người đầu tiên trong đường dây
Ngân hàng là người đầu tiên

18
00:00:59,160 --> 00:01:00,760
những người được để nói chuyện với các nhân viên giao dịch.

19
00:01:00,760 --> 00:01:03,522
>> Nó sẽ là sắp xếp của một chủng tộc
đến phía dưới nếu cách duy nhất

20
00:01:03,522 --> 00:01:06,730
Bạn có để nói chuyện với các nhân viên giao dịch tại
ngân hàng đã phải là người cuối cùng trong hàng.

21
00:01:06,730 --> 00:01:09,146
Mọi người sẽ luôn luôn muốn
phải là người cuối cùng trong đường dây,

22
00:01:09,146 --> 00:01:12,580
và người đó đã có những người đầu tiên
người đã chờ đợi một thời gian,

23
00:01:12,580 --> 00:01:14,715
có thể ở đó trong nhiều giờ,
và giờ, và giờ

24
00:01:14,715 --> 00:01:17,590
trước khi chúng có cơ hội để thực sự
rút tiền tại ngân hàng.

25
00:01:17,590 --> 00:01:22,510
Và như vậy hàng đợi được sắp xếp của các
công bằng việc thực hiện cơ cấu.

26
00:01:22,510 --> 00:01:25,780
Nhưng điều đó không nhất thiết có nghĩa
rằng ngăn xếp là một điều xấu, chỉ

27
00:01:25,780 --> 00:01:28,160
rằng hàng đợi là một cách khác để làm điều đó.

28
00:01:28,160 --> 00:01:32,420
Vì vậy, một lần nữa một hàng đợi đầu vào, đầu tiên
ra, so với một chồng mà cuối cùng trong,

29
00:01:32,420 --> 00:01:34,440
đầu ra.

30
00:01:34,440 --> 00:01:36,190
Tương tự như một chồng,
chúng tôi có hai hoạt động

31
00:01:36,190 --> 00:01:38,470
rằng chúng ta có thể thực hiện trên hàng đợi.

32
00:01:38,470 --> 00:01:43,910
Các tên là enqueue, đó là thêm
một yếu tố mới vào cuối hàng đợi,

33
00:01:43,910 --> 00:01:47,330
và dequeue, đó là
để loại bỏ các cổ nhất

34
00:01:47,330 --> 00:01:49,670
yếu tố từ phía trước của hàng đợi.

35
00:01:49,670 --> 00:01:53,600
Vì vậy, chúng ta sẽ thêm các yếu tố
vào cuối hàng đợi,

36
00:01:53,600 --> 00:01:57,220
và chúng tôi sẽ loại bỏ các yếu tố
từ phía trước của hàng đợi.

37
00:01:57,220 --> 00:02:00,790
Một lần nữa, với chồng, chúng tôi đã bổ sung thêm
phần từ đỉnh của ngăn xếp

38
00:02:00,790 --> 00:02:03,380
và loại bỏ yếu tố
từ đỉnh của ngăn xếp.

39
00:02:03,380 --> 00:02:07,570
Vì vậy, với enqueue, nó thêm vào
cuối, loại bỏ từ phía trước.

40
00:02:07,570 --> 00:02:10,639
Vì vậy, điều lâu đời nhất ở trong đó
luôn luôn là điều tiếp theo

41
00:02:10,639 --> 00:02:13,620
để đi ra nếu chúng tôi cố gắng
và dequeue một cái gì đó.

42
00:02:13,620 --> 00:02:18,330
>> Vì vậy, một lần nữa, với hàng đợi, chúng ta có thể
triển khai mảng dựa trên

43
00:02:18,330 --> 00:02:20,110
và danh sách liên kết triển khai dựa.

44
00:02:20,110 --> 00:02:24,620
Chúng tôi sẽ bắt đầu lại với
triển khai mảng dựa trên.

45
00:02:24,620 --> 00:02:27,070
Định nghĩa cấu trúc
trông khá tương tự.

46
00:02:27,070 --> 00:02:30,720
Chúng tôi có một mảng khác
có giá trị kiểu dữ liệu,

47
00:02:30,720 --> 00:02:32,690
do đó, nó có thể chứa các loại dữ liệu tùy ý.

48
00:02:32,690 --> 00:02:35,570
Chúng tôi một lần nữa đi vào sử dụng
số nguyên trong ví dụ này.

49
00:02:35,570 --> 00:02:39,830
>> Và cũng như với chúng tôi
mảng dựa trên ngăn xếp thực hiện,

50
00:02:39,830 --> 00:02:42,340
bởi vì chúng ta đang sử dụng một
mảng, chúng ta nhất thiết

51
00:02:42,340 --> 00:02:46,850
có giới hạn đó mà loại C
của thực thi trên chúng ta, đó là chúng ta

52
00:02:46,850 --> 00:02:51,670
không có bất kỳ năng động trong chúng tôi
khả năng phát triển và co mảng.

53
00:02:51,670 --> 00:02:55,710
Chúng tôi phải quyết định ngay từ đầu
số lượng tối đa của vật là gì

54
00:02:55,710 --> 00:02:59,300
rằng chúng ta có thể đưa vào đây
hàng đợi, và trong trường hợp này,

55
00:02:59,300 --> 00:03:02,070
khả năng sẽ có một số bảng
định nghĩa hằng số trong mã của chúng tôi.

56
00:03:02,070 --> 00:03:05,430
Và cho các mục đích này
video, công suất sẽ là 10.

57
00:03:05,430 --> 00:03:07,690
>> Chúng ta cần theo dõi
phía trước của hàng đợi

58
00:03:07,690 --> 00:03:11,160
vì vậy chúng tôi biết rằng những yếu tố
chúng tôi muốn dequeue,

59
00:03:11,160 --> 00:03:15,070
và chúng ta cũng cần phải theo dõi
một cái gì đó else-- số phần tử

60
00:03:15,070 --> 00:03:16,690
mà chúng tôi có trong hàng đợi của chúng tôi.

61
00:03:16,690 --> 00:03:19,360
Chú ý chúng tôi không theo dõi
Tính đến cuối của hàng đợi, chỉ

62
00:03:19,360 --> 00:03:21,150
kích thước của hàng đợi.

63
00:03:21,150 --> 00:03:24,310
Và lý do cho rằng sẽ hy vọng
trở thành một chút rõ ràng hơn trong một thời điểm.

64
00:03:24,310 --> 00:03:26,143
Một khi chúng ta đã hoàn thành
định nghĩa kiểu này,

65
00:03:26,143 --> 00:03:29,080
chúng ta có một kiểu dữ liệu mới
gọi là hàng đợi, mà chúng tôi có thể bây giờ

66
00:03:29,080 --> 00:03:30,630
khai báo các biến của kiểu dữ liệu.

67
00:03:30,630 --> 00:03:35,350
Và phần nào gây nhầm lẫn, tôi đã quyết định
để gọi hàng đợi q này, các thư

68
00:03:35,350 --> 00:03:38,090
q thay vì các kiểu dữ liệu q.

69
00:03:38,090 --> 00:03:39,600
>> Vì vậy, đây là hàng đợi của chúng tôi.

70
00:03:39,600 --> 00:03:40,700
Nó là một cấu trúc.

71
00:03:40,700 --> 00:03:45,730
Nó chứa ba thành viên hoặc ba
lĩnh vực, một mảng có kích thước NĂNG LỰC.

72
00:03:45,730 --> 00:03:47,340
Trong trường hợp này, NĂNG LỰC là 10.

73
00:03:47,340 --> 00:03:49,580
Và mảng này là
sẽ giữ nguyên.

74
00:03:49,580 --> 00:03:55,240
Màu xanh là mặt trước của hàng đợi của chúng tôi,
Yếu tố tiếp theo sẽ được gỡ bỏ, và màu đỏ

75
00:03:55,240 --> 00:03:58,610
sẽ được kích thước của hàng đợi,
bao nhiêu yếu tố hiện đang là

76
00:03:58,610 --> 00:04:01,190
hiện có trong hàng đợi.

77
00:04:01,190 --> 00:04:05,300
Vì vậy, nếu chúng ta nói equals q.front
0, và kích thước q.size bằng 0--

78
00:04:05,300 --> 00:04:07,120
chúng ta đặt số 0 vào các lĩnh vực này.

79
00:04:07,120 --> 00:04:11,070
Và tại thời điểm này, chúng tôi khá nhiều
sẵn sàng để bắt đầu làm việc với hàng đợi của chúng tôi.

80
00:04:11,070 --> 00:04:14,140
>> Vì vậy, các hoạt động đầu tiên chúng ta có thể
thực hiện là enqueue một cái gì đó,

81
00:04:14,140 --> 00:04:16,860
để thêm một yếu tố mới để
cuối của hàng đợi.

82
00:04:16,860 --> 00:04:19,089
Vâng những gì chúng ta cần phải
làm gì trong trường hợp tổng quát?

83
00:04:19,089 --> 00:04:23,690
Vâng chức năng này enqueue nhu cầu
để chấp nhận một con trỏ vào hàng đợi của chúng tôi.

84
00:04:23,690 --> 00:04:26,370
Một lần nữa, nếu chúng ta đã tuyên bố
hàng đợi của chúng tôi trên toàn cầu,

85
00:04:26,370 --> 00:04:29,490
chúng ta sẽ không cần phải làm điều này
nhất thiết, nhưng nói chung, chúng tôi

86
00:04:29,490 --> 00:04:32,330
cần phải chấp nhận con trỏ
để cấu trúc dữ liệu

87
00:04:32,330 --> 00:04:35,040
như thế này, bởi vì nếu không,
chúng ta đang đi ngang qua value-- chúng tôi

88
00:04:35,040 --> 00:04:38,140
đi qua trong các bản sao của hàng đợi,
và vì vậy chúng ta không thực sự thay đổi

89
00:04:38,140 --> 00:04:41,050
hàng đợi rằng chúng tôi có ý định thay đổi.

90
00:04:41,050 --> 00:04:44,860
>> Một điều khác cần làm là chấp nhận
một phần tử dữ liệu của các loại thích hợp.

91
00:04:44,860 --> 00:04:46,818
Một lần nữa, trong trường hợp này, đó là
sẽ là các số nguyên,

92
00:04:46,818 --> 00:04:49,330
nhưng bạn có thể tùy tiện
khai báo kiểu dữ liệu như giá trị

93
00:04:49,330 --> 00:04:51,160
và sử dụng nói chung.

94
00:04:51,160 --> 00:04:56,030
Đó là những yếu tố chúng ta muốn enqueue,
chúng ta muốn thêm vào cuối hàng đợi.

95
00:04:56,030 --> 00:04:58,573
Sau đó, chúng tôi thực sự muốn
đặt dữ liệu trong hàng đợi.

96
00:04:58,573 --> 00:05:01,490
Trong trường hợp này, đặt nó trong
đúng vị trí của mảng của chúng tôi,

97
00:05:01,490 --> 00:05:05,040
và sau đó chúng tôi muốn thay đổi kích thước
của hàng đợi, bao nhiêu yếu tố chúng tôi

98
00:05:05,040 --> 00:05:07,050
hiện có.

99
00:05:07,050 --> 00:05:07,990
>> Vì vậy, chúng ta hãy bắt đầu.

100
00:05:07,990 --> 00:05:10,890
Ở đây, một lần nữa, mà nói chung
khai báo hàm dạng

101
00:05:10,890 --> 00:05:13,980
cho những gì enqueue thể trông như thế.

102
00:05:13,980 --> 00:05:14,910
Và ở đây chúng tôi đi.

103
00:05:14,910 --> 00:05:18,335
Hãy enqueue số
28 vào hàng đợi.

104
00:05:18,335 --> 00:05:19,460
Vì vậy, những gì chúng ta sẽ làm gì?

105
00:05:19,460 --> 00:05:23,390
Vâng, mặt trước của hàng đợi của chúng tôi là
0, và kích thước của hàng đợi của chúng tôi

106
00:05:23,390 --> 00:05:29,680
là 0, và vì vậy chúng tôi có thể muốn đặt
số 28 trong số phần tử mảng

107
00:05:29,680 --> 00:05:31,124
0, phải không?

108
00:05:31,124 --> 00:05:32,540
Vì vậy, bây giờ chúng tôi đã đặt trong đó.

109
00:05:32,540 --> 00:05:34,820
Vì vậy, bây giờ những gì chúng ta cần phải thay đổi?

110
00:05:34,820 --> 00:05:37,090
Chúng tôi không muốn thay đổi
phía trước của hàng đợi,

111
00:05:37,090 --> 00:05:40,850
bởi vì chúng tôi muốn biết những gì yếu tố
chúng ta có thể cần phải dequeue sau.

112
00:05:40,850 --> 00:05:44,020
Vì vậy, lý do chúng tôi có mặt ở đó
là loại một chỉ báo về những gì

113
00:05:44,020 --> 00:05:46,439
điều lâu đời nhất trong mảng.

114
00:05:46,439 --> 00:05:49,730
Vâng điều lâu đời nhất trong array-- trong
Thực tế, điều duy nhất trong mảng quyền

115
00:05:49,730 --> 00:05:53,540
now-- là 28, đó là
ở mảng vị trí 0.

116
00:05:53,540 --> 00:05:56,160
Vì vậy, chúng tôi không muốn
thay đổi con số màu xanh lá cây,

117
00:05:56,160 --> 00:05:57,910
bởi vì đó là những yếu tố lâu đời nhất.

118
00:05:57,910 --> 00:06:00,510
Thay vào đó, chúng tôi muốn thay đổi kích thước.

119
00:06:00,510 --> 00:06:04,110
Vì vậy, trong trường hợp này, chúng tôi sẽ
tăng kích thước đến 1.

120
00:06:04,110 --> 00:06:08,430
>> Bây giờ một loại chung của ý tưởng về nơi
Yếu tố tiếp theo là sẽ đi trong một hàng đợi

121
00:06:08,430 --> 00:06:12,310
là thêm hai con số
với nhau, mặt trước và kích thước,

122
00:06:12,310 --> 00:06:16,390
và đó sẽ cho bạn biết nơi tiếp theo
phần tử trong hàng đợi là sẽ đi.

123
00:06:16,390 --> 00:06:18,130
Vì vậy, bây giờ hãy enqueue một số khác.

124
00:06:18,130 --> 00:06:20,250
Hãy enqueue 33.

125
00:06:20,250 --> 00:06:24,480
Vì vậy, 33 là sẽ đi vào
mảng địa điểm 0 cộng với 1.

126
00:06:24,480 --> 00:06:26,840
Vì vậy, trong trường hợp này, nó sẽ
để đi vào mảng vị trí 1,

127
00:06:26,840 --> 00:06:29,500
và bây giờ là kích thước của hàng đợi của chúng tôi là 2.

128
00:06:29,500 --> 00:06:31,840
>> Một lần nữa, chúng tôi sẽ không thay đổi
mặt trước của hàng đợi của chúng tôi,

129
00:06:31,840 --> 00:06:34,730
vì 28 vẫn là
yếu tố lâu đời nhất, và chúng tôi

130
00:06:34,730 --> 00:06:38,220
muốn với: khi ta sẽ nhận được
để dequeuing, loại bỏ yếu tố

131
00:06:38,220 --> 00:06:43,300
từ hàng đợi này, chúng tôi muốn biết
ở đó yếu tố lâu đời nhất là.

132
00:06:43,300 --> 00:06:48,620
Và vì vậy chúng tôi luôn luôn cần phải duy trì
một số chỉ số về nơi đó là.

133
00:06:48,620 --> 00:06:50,410
Vì vậy, đó là những gì 0 là có cho.

134
00:06:50,410 --> 00:06:52,910
Đó là những gì phía trước là có cho.

135
00:06:52,910 --> 00:06:55,022
>> Hãy ở enqueue một trong nhiều yếu tố, 19.

136
00:06:55,022 --> 00:06:56,980
Tôi chắc rằng bạn có thể đoán
nơi 19 là sẽ đi.

137
00:06:56,980 --> 00:06:59,860
Nó sẽ đi vào
mảng vị trí số 2.

138
00:06:59,860 --> 00:07:01,570
Đó là 0 cộng 2.

139
00:07:01,570 --> 00:07:03,199
Và bây giờ là kích thước của hàng đợi của chúng tôi là 3.

140
00:07:03,199 --> 00:07:04,240
Chúng tôi có 3 yếu tố trong đó.

141
00:07:04,240 --> 00:07:08,490
Vì vậy, nếu chúng ta, và chúng ta sẽ không
đến ngay bây giờ, enqueue một yếu tố khác,

142
00:07:08,490 --> 00:07:11,370
nó sẽ đi vào mảng vị trí
số 3, và kích thước của hàng đợi của chúng tôi

143
00:07:11,370 --> 00:07:13,160
sẽ là 4.

144
00:07:13,160 --> 00:07:15,279
Vì vậy, chúng tôi đã enqueued một số yếu tố bây giờ.

145
00:07:15,279 --> 00:07:16,570
Bây giờ chúng ta hãy bắt đầu loại bỏ chúng.

146
00:07:16,570 --> 00:07:19,450
Hãy dequeue họ từ hàng đợi.

147
00:07:19,450 --> 00:07:23,340
>> Vì vậy, tương tự như pop, đó là loại
của analog này cho ngăn xếp,

148
00:07:23,340 --> 00:07:26,180
dequeue cần phải chấp nhận một
con trỏ đến queue-- một lần nữa,

149
00:07:26,180 --> 00:07:28,140
trừ khi nó được công bố trên toàn cầu.

150
00:07:28,140 --> 00:07:31,610
Bây giờ chúng tôi muốn thay đổi vị trí
của mặt trước của hàng đợi.

151
00:07:31,610 --> 00:07:35,050
Đây là nơi mà nó loại đi kèm
vào chơi, mà biến phía trước,

152
00:07:35,050 --> 00:07:37,310
bởi vì một khi chúng ta loại bỏ
một phần tử, chúng ta muốn

153
00:07:37,310 --> 00:07:40,720
để di chuyển nó đến các yếu tố cũ nhất tiếp theo.

154
00:07:40,720 --> 00:07:44,180
>> Sau đó, chúng tôi muốn giảm
kích thước của hàng đợi,

155
00:07:44,180 --> 00:07:47,130
và sau đó chúng ta muốn trả về giá trị
đã được gỡ bỏ khỏi hàng đợi.

156
00:07:47,130 --> 00:07:48,921
Một lần nữa, chúng tôi không muốn chỉ cần loại bỏ nó.

157
00:07:48,921 --> 00:07:51,170
Chúng tôi có lẽ được chiết xuất
nó từ queue-- chúng tôi

158
00:07:51,170 --> 00:07:54,170
dequeuing nó bởi vì chúng tôi quan tâm đến nó.

159
00:07:54,170 --> 00:08:01,080
Vì vậy, chúng tôi muốn chức năng này để trở về
một phần tử dữ liệu của loại giá trị.

160
00:08:01,080 --> 00:08:04,360
Một lần nữa, trong trường hợp này, giá trị là số nguyên.

161
00:08:04,360 --> 00:08:05,670
>> Vì vậy, bây giờ hãy dequeue một cái gì đó.

162
00:08:05,670 --> 00:08:09,310
Hãy loại bỏ một phần tử từ hàng đợi.

163
00:08:09,310 --> 00:08:15,970
Nếu chúng ta nói int x = & q, ký hiệu q--
một lần nữa đó là một con trỏ đến dữ liệu q này

164
00:08:15,970 --> 00:08:20,177
structure-- cho yếu tố
sẽ được dequeued?

165
00:08:20,177 --> 00:08:23,840

166
00:08:23,840 --> 00:08:29,480
Trong trường hợp này, bởi vì nó là một đầu tiên
trong, đầu ra cấu trúc dữ liệu, FIFO,

167
00:08:29,480 --> 00:08:33,690
điều đầu tiên chúng ta đưa vào đây
hàng đợi là 28, và vì vậy trong trường hợp này,

168
00:08:33,690 --> 00:08:37,245
chúng ta sẽ mất 28 trong số
hàng đợi, không phải 19, mà là những gì

169
00:08:37,245 --> 00:08:38,870
chúng tôi đã có thể làm nếu điều này là một chồng.

170
00:08:38,870 --> 00:08:42,220
Chúng ta sẽ mất 28 ra khỏi hàng đợi.

171
00:08:42,220 --> 00:08:44,960
>> Tương tự như những gì chúng ta đã làm với
một chồng, chúng tôi không thực sự

172
00:08:44,960 --> 00:08:47,345
đi để xóa 28
từ hàng đợi riêng của mình,

173
00:08:47,345 --> 00:08:49,470
chúng tôi chỉ cần đi để loại
của giả vờ đó là không có.

174
00:08:49,470 --> 00:08:51,678
Vì vậy, nó sẽ ở lại đó
trong bộ nhớ, nhưng chúng tôi chỉ

175
00:08:51,678 --> 00:08:57,820
sẽ loại bỏ nó bằng cách di chuyển
hai lĩnh vực khác của dữ liệu của chúng tôi q

176
00:08:57,820 --> 00:08:58,830
cấu trúc.

177
00:08:58,830 --> 00:09:00,230
Chúng ta sẽ thay đổi phía trước.

178
00:09:00,230 --> 00:09:04,290
Q.front bây giờ sẽ
là 1, vì rằng bây giờ là

179
00:09:04,290 --> 00:09:07,740
các yếu tố lâu đời nhất chúng tôi có trong chúng tôi
hàng đợi, bởi vì chúng tôi đã loại bỏ 28,

180
00:09:07,740 --> 00:09:10,460
đó là yếu tố lâu đời cũ.

181
00:09:10,460 --> 00:09:13,540
>> Và bây giờ, chúng tôi muốn thay đổi
kích thước của hàng đợi

182
00:09:13,540 --> 00:09:15,780
hai yếu tố thay vì ba.

183
00:09:15,780 --> 00:09:20,450
Bây giờ nhớ trước đó tôi đã nói khi chúng tôi
muốn thêm phần tử vào hàng đợi,

184
00:09:20,450 --> 00:09:26,000
chúng tôi đặt nó ở một vị trí mảng
đó là tổng của mặt trước và kích thước.

185
00:09:26,000 --> 00:09:29,050
Vì vậy, trong trường hợp này, chúng tôi vẫn đặt
nó, phần tử tiếp theo trong hàng đợi,

186
00:09:29,050 --> 00:09:33,360
vào mảng vị trí 3, và
chúng ta sẽ thấy rằng trong một giây.

187
00:09:33,360 --> 00:09:35,730
>> Vì vậy, bây giờ chúng tôi đã dequeued của chúng tôi
Yếu tố đầu tiên từ hàng đợi.

188
00:09:35,730 --> 00:09:36,480
Hãy làm điều đó một lần nữa.

189
00:09:36,480 --> 00:09:38,696
Hãy loại bỏ khác
phần tử từ hàng đợi.

190
00:09:38,696 --> 00:09:42,400
Trong trường hợp, lâu đời nhất hiện nay
phần tử là mảng 1 vị trí.

191
00:09:42,400 --> 00:09:44,220
Đó là những gì q.front nói với chúng ta.

192
00:09:44,220 --> 00:09:46,980
Đó là hộp màu xanh lá cây cho chúng ta biết
đó là yếu tố lâu đời nhất.

193
00:09:46,980 --> 00:09:49,310
Và như vậy, x sẽ trở thành 33.

194
00:09:49,310 --> 00:09:52,130
Chúng tôi sẽ chỉ cần loại quên
33 tồn tại trong mảng,

195
00:09:52,130 --> 00:09:55,100
và chúng tôi sẽ nói rằng bây giờ, các
yếu tố cổ nhất mới trong hàng đợi

196
00:09:55,100 --> 00:09:58,900
là ở mảng vị trí 2, và kích thước
của hàng đợi, số lượng các yếu tố

197
00:09:58,900 --> 00:10:02,152
chúng tôi có trong hàng đợi, là 1.

198
00:10:02,152 --> 00:10:05,110
Bây giờ chúng ta hãy enqueue một cái gì đó, và tôi
loại này đã cho đi một giây trước đó,

199
00:10:05,110 --> 00:10:10,340
nhưng nếu chúng ta muốn đặt 40 vào
hàng đợi, nơi của 40 sẽ đi đâu?

200
00:10:10,340 --> 00:10:12,880

201
00:10:12,880 --> 00:10:17,730
Vâng, chúng tôi đã đưa nó
trong q.front cộng với hàng đợi kích thước,

202
00:10:17,730 --> 00:10:20,850
và do đó, nó làm cho cảm giác
thực sự để đưa 40 ở đây.

203
00:10:20,850 --> 00:10:22,840
Bây giờ nhận thấy rằng tại
một số điểm, chúng ta sẽ

204
00:10:22,840 --> 00:10:27,980
để có được đến cuối của
mảng của chúng tôi bên trong của q,

205
00:10:27,980 --> 00:10:32,010
nhưng mà nhạt nhòa dần 28 và 33--
chúng thật sự, về mặt kỹ thuật

206
00:10:32,010 --> 00:10:33,300
không gian mở, phải không?

207
00:10:33,300 --> 00:10:36,040
Và như vậy, chúng ta có thể eventually--
rằng quy tắc của việc thêm

208
00:10:36,040 --> 00:10:40,390
hai together-- chúng tôi có thể cuối cùng
cần mod bởi kích thước của công suất

209
00:10:40,390 --> 00:10:41,410
vì vậy chúng tôi có thể quấn quanh.

210
00:10:41,410 --> 00:10:43,620
>> Vì vậy, nếu chúng ta có được yếu tố
số 10, nếu chúng tôi

211
00:10:43,620 --> 00:10:48,790
thay thế nó trong phần tử số 10, chúng tôi muốn
thực sự đặt nó trong mảng vị trí 0.

212
00:10:48,790 --> 00:10:50,997
Và nếu chúng tôi đã đi
mảng location-- tha cho tôi,

213
00:10:50,997 --> 00:10:53,080
nếu chúng tôi được họ lên cùng nhau,
và chúng tôi đã số

214
00:10:53,080 --> 00:10:56,330
11 sẽ là nơi mà chúng tôi sẽ phải đặt
nó, mà không tồn tại trong array-- này

215
00:10:56,330 --> 00:10:58,200
nó sẽ đi ra ngoài giới hạn.

216
00:10:58,200 --> 00:11:03,367
Chúng ta có thể mod bởi 10 và đặt
nó trong mảng 1 vị trí.

217
00:11:03,367 --> 00:11:04,450
Vì vậy, đó là cách làm việc hàng đợi.

218
00:11:04,450 --> 00:11:08,540
Họ luôn luôn đi từ trái
sang phải và có thể quấn quanh.

219
00:11:08,540 --> 00:11:11,280
Và bạn biết rằng họ đang
đầy đủ nếu kích thước, mà hộp màu đỏ,

220
00:11:11,280 --> 00:11:13,710
trở nên bằng năng lực.

221
00:11:13,710 --> 00:11:16,720
Và như vậy sau khi chúng tôi đã thêm 40 đến
hàng đợi, cũng làm những gì chúng ta cần phải làm gì?

222
00:11:16,720 --> 00:11:19,890
Vâng, yếu tố cổ xưa nhất
trong hàng đợi vẫn là 19,

223
00:11:19,890 --> 00:11:21,990
vì vậy chúng tôi không muốn thay đổi
phía trước của hàng đợi,

224
00:11:21,990 --> 00:11:23,820
nhưng bây giờ chúng tôi có hai
các phần tử trong hàng đợi,

225
00:11:23,820 --> 00:11:28,710
và vì vậy chúng tôi muốn tăng
Kích thước của chúng tôi 1-2.

226
00:11:28,710 --> 00:11:31,820
>> Đó là khá nhiều nó với
làm việc với hàng đợi dựa trên mảng,

227
00:11:31,820 --> 00:11:33,630
và tương tự để ngăn xếp,
đó cũng là một cách

228
00:11:33,630 --> 00:11:36,450
để thực hiện một hàng đợi như là một danh sách liên kết.

229
00:11:36,450 --> 00:11:40,150
Bây giờ nếu có kiểu cấu trúc dữ liệu này
trông quen thuộc với bạn, nó được.

230
00:11:40,150 --> 00:11:43,780
Nó không phải là một danh sách đơn lẻ liên kết,
đó là một danh sách gấp đôi được liên kết.

231
00:11:43,780 --> 00:11:46,790
Và bây giờ, khi một sang một bên, nó là
thực sự có thể thực hiện

232
00:11:46,790 --> 00:11:50,160
một hàng đợi như một danh sách liên kết đơn lẻ, nhưng
Tôi nghĩ về mặt trực quan,

233
00:11:50,160 --> 00:11:53,350
nó thực sự có thể giúp để xem
này như là một danh sách gấp đôi được liên kết.

234
00:11:53,350 --> 00:11:56,850
Nhưng nó chắc chắn có thể
làm điều này như là một danh sách đơn lẻ liên kết.

235
00:11:56,850 --> 00:12:00,110
>> Vì vậy, chúng ta hãy có một cái nhìn tại
điều này có thể trông như thế nào.

236
00:12:00,110 --> 00:12:02,750
Nếu chúng ta muốn enquue--
vì vậy bây giờ, một lần nữa chúng tôi

237
00:12:02,750 --> 00:12:05,360
chuyển sang một danh sách liên kết
dựa trên mô hình ở đây.

238
00:12:05,360 --> 00:12:08,420
Nếu chúng ta muốn enqueue, chúng tôi muốn
để thêm một yếu tố mới, cũng

239
00:12:08,420 --> 00:12:09,730
những gì chúng ta cần phải làm gì?

240
00:12:09,730 --> 00:12:12,770
Vâng, trước hết, bởi vì
chúng ta đang thêm đến cùng

241
00:12:12,770 --> 00:12:15,520
và loại bỏ từ
bắt đầu, chúng ta có thể

242
00:12:15,520 --> 00:12:20,050
muốn duy trì con trỏ đến cả
đầu và đuôi của danh sách liên kết?

243
00:12:20,050 --> 00:12:22,660
Tail là một hạn cho
sự kết thúc của danh sách liên kết,

244
00:12:22,660 --> 00:12:24,496
phần tử cuối cùng trong danh sách liên kết.

245
00:12:24,496 --> 00:12:26,620
Và những thể sẽ,
một lần nữa, có lợi cho chúng tôi

246
00:12:26,620 --> 00:12:28,477
nếu họ là các biến toàn cầu.

247
00:12:28,477 --> 00:12:31,060
Nhưng bây giờ nếu chúng ta muốn thêm một mới
yếu tố gì làm chúng ta phải làm gì?

248
00:12:31,060 --> 00:12:35,262
Những gì chúng ta chỉ [? Malak?] hoặc tự động
phân bổ nút mới của chúng tôi cho chính mình.

249
00:12:35,262 --> 00:12:38,220
Và sau đó, giống như khi chúng ta thêm bất kỳ
yếu tố để một danh sách chúng ta gấp đôi liên kết,

250
00:12:38,220 --> 00:12:40,410
chỉ có để sắp xếp of--
ba bước cuối cùng ở đây

251
00:12:40,410 --> 00:12:43,330
chỉ là tất cả về việc di chuyển
con trỏ một cách chính xác

252
00:12:43,330 --> 00:12:46,710
do đó các phần tử được thêm vào
các chuỗi mà không phá vỡ dây chuyền

253
00:12:46,710 --> 00:12:49,580
hoặc làm cho một số loại sai lầm
hoặc có một số loại tai nạn

254
00:12:49,580 --> 00:12:54,505
xảy ra nhờ đó mà chúng ta vô tình
Orphan một số yếu tố của hàng đợi của chúng tôi.

255
00:12:54,505 --> 00:12:55,880
Đây là những gì này có thể trông như thế nào.

256
00:12:55,880 --> 00:13:00,980
Chúng tôi muốn thêm vào các yếu tố
10 đến cuối hàng đợi này.

257
00:13:00,980 --> 00:13:03,380
Vì vậy, các yếu tố lâu đời nhất ở đây
được đại diện bởi đầu.

258
00:13:03,380 --> 00:13:06,800
Đó là điều đầu tiên chúng tôi đặt
vào hàng đợi giả thuyết này ở đây.

259
00:13:06,800 --> 00:13:10,430
Và đuôi, 13 tuổi, là nhất
gần đây đã thêm yếu tố.

260
00:13:10,430 --> 00:13:17,030
Và như vậy, nếu chúng ta muốn enqueue 10 vào
hàng đợi này, chúng tôi muốn đặt nó sau 13.

261
00:13:17,030 --> 00:13:19,860
Và như vậy chúng ta sẽ phải tự động
phân bổ không gian cho một nút mới

262
00:13:19,860 --> 00:13:23,280
và kiểm tra null để đảm bảo
chúng ta không có một thất bại bộ nhớ.

263
00:13:23,280 --> 00:13:27,040
Sau đó chúng ta sẽ
đặt 10 vào nút đó,

264
00:13:27,040 --> 00:13:30,030
và bây giờ chúng ta cần phải cẩn thận
về cách chúng tôi tổ chức các con trỏ

265
00:13:30,030 --> 00:13:32,180
vì vậy chúng tôi không phá vỡ dây chuyền.

266
00:13:32,180 --> 00:13:38,910
>> Chúng tôi có thể thiết lập trường trước đây của 10
đến điểm trở lại đuôi cũ,

267
00:13:38,910 --> 00:13:41,620
và kể từ '10 sẽ là
đuôi mới tại một số điểm

268
00:13:41,620 --> 00:13:44,459
do thời gian tất cả các
chuỗi được kết nối,

269
00:13:44,459 --> 00:13:46,250
không có gì đang xảy đến
sau 10 ngay bây giờ.

270
00:13:46,250 --> 00:13:49,880
Và như vậy con trỏ tới 10 của
sẽ trỏ đến null,

271
00:13:49,880 --> 00:13:53,580
và sau đó sau khi chúng tôi làm điều này, sau khi chúng tôi đã
kết nối 10 ngược trở lại để các chuỗi,

272
00:13:53,580 --> 00:13:57,780
chúng ta có thể lấy đầu cũ, hay, cái cớ
tôi, đuôi cũ của hàng đợi.

273
00:13:57,780 --> 00:14:02,980
Sự kết thúc cũ của hàng đợi,
13, và làm cho nó trỏ đến 10.

274
00:14:02,980 --> 00:14:08,220
Và bây giờ, vào thời điểm này, chúng tôi có
enqueued số 10 vào hàng đợi này.

275
00:14:08,220 --> 00:14:14,740
Tất cả chúng ta cần làm bây giờ chỉ được di chuyển
đuôi để trỏ đến 10 thay vì 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing là thực sự
rất giống với popping

277
00:14:17,630 --> 00:14:21,710
từ một chồng mà là
thực hiện như một danh sách liên kết

278
00:14:21,710 --> 00:14:24,040
nếu bạn đã nhìn thấy những đống video.

279
00:14:24,040 --> 00:14:27,280
Tất cả chúng ta cần phải làm là bắt đầu ở
bắt đầu, tìm các phần tử thứ hai,

280
00:14:27,280 --> 00:14:30,480
giải phóng các yếu tố đầu tiên,
và sau đó di chuyển đầu

281
00:14:30,480 --> 00:14:32,930
để trỏ đến phần tử thứ hai.

282
00:14:32,930 --> 00:14:37,920
Có lẽ tốt hơn để hình dung nó
chỉ được thêm rõ ràng về nó.

283
00:14:37,920 --> 00:14:39,230
Vì vậy, đây là hàng đợi của chúng tôi một lần nữa.

284
00:14:39,230 --> 00:14:42,600
12 là yếu tố lâu đời nhất
trong hàng đợi của chúng tôi, những người đứng đầu.

285
00:14:42,600 --> 00:14:46,210
10 là nguyên tố mới nhất
trong hàng đợi của chúng tôi, đuôi của chúng tôi.

286
00:14:46,210 --> 00:14:49,310
>> Và như vậy khi chúng ta muốn
để dequeue một phần tử,

287
00:14:49,310 --> 00:14:52,202
chúng ta muốn loại bỏ các yếu tố lâu đời nhất.

288
00:14:52,202 --> 00:14:52,910
vậy chúng ta làm gì?

289
00:14:52,910 --> 00:14:55,243
Vâng, chúng tôi thiết lập một con trỏ traversal
mà bắt đầu từ đầu,

290
00:14:55,243 --> 00:14:57,840
và chúng tôi di chuyển nó để nó
trỏ tới phần tử thứ hai

291
00:14:57,840 --> 00:15:02,290
điều này queue-- một cái gì đó bằng cách nói trav
bằng trav mũi tên bên cạnh, ví dụ,

292
00:15:02,290 --> 00:15:07,170
sẽ di chuyển trav đó để trỏ đến
15, trong đó, sau khi chúng tôi dequeue 12,

293
00:15:07,170 --> 00:15:13,030
hoặc sau khi chúng tôi loại bỏ 12, sẽ
trở thành các yếu tố sau đó lâu đời.

294
00:15:13,030 --> 00:15:16,360
>> Bây giờ chúng ta đã có một tổ chức vào ngày đầu tiên
yếu tố thông qua đầu con trỏ

295
00:15:16,360 --> 00:15:19,440
và yếu tố thứ hai
qua trav con trỏ.

296
00:15:19,440 --> 00:15:25,170
Chúng tôi có thể đứng đầu bây giờ miễn phí, và sau đó chúng ta có thể
nói gì đến trước 15 nữa.

297
00:15:25,170 --> 00:15:29,990
Vì vậy, chúng ta có thể thay đổi 15 của trước
con trỏ trỏ tới null,

298
00:15:29,990 --> 00:15:31,874
và chúng ta chỉ cần di chuyển đầu hơn.

299
00:15:31,874 --> 00:15:32,540
Và ở đó chúng tôi đi.

300
00:15:32,540 --> 00:15:35,840
Bây giờ chúng tôi đã thành công
dequeued 12, và bây giờ chúng tôi

301
00:15:35,840 --> 00:15:39,180
có một hàng đợi của 4 yếu tố.

302
00:15:39,180 --> 00:15:41,700
Đó là khá nhiều tất cả
có đến hàng đợi,

303
00:15:41,700 --> 00:15:45,810
cả hai mảng dựa trên và danh sách liên kết dựa.

304
00:15:45,810 --> 00:15:46,860
Tôi Doug Lloyd.

305
00:15:46,860 --> 00:15:49,100
Đây là CS 50.

306
00:15:49,100 --> 00:15:50,763