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

2
00:00:02,000 --> 00:00:05,000
[Chris Gerber, Università ta 'Harvard]

3
00:00:05,000 --> 00:00:07,000
Dan huwa CS50, CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Wieħed utli struttura tad-data għall-ħażna ġabra ordnata ta 'elementi huwa kju.

5
00:00:11,000 --> 00:00:14,000
Huwa jintuża meta l-elementi għandhom jitneħħew

6
00:00:14,000 --> 00:00:16,000
fl-istess ordni kif kienu miżjuda.

7
00:00:16,000 --> 00:00:20,000
Dan il-kunċett huwa msejjaħ FIFO, li huwa akronimu għal ewwel, l-ewwel barra.

8
00:00:20,000 --> 00:00:23,000
Biex tgħin Ħares dan, jista 'jkun utli li stampa

9
00:00:23,000 --> 00:00:25,000
linja checkout fil-maħżen.

10
00:00:25,000 --> 00:00:28,000
Billi n-nies jaslu, huma jistennew fuq wara tal-linja.

11
00:00:28,000 --> 00:00:31,000
Il-kaxxier mbagħad jieħu dawriet li jservu lill-klijenti fuq quddiem,

12
00:00:31,000 --> 00:00:34,000
li mbagħad ħruġ tal-linja waħda kull darba.

13
00:00:34,000 --> 00:00:37,000
Fix-xjenza tal-kompjuter, aħna nirreferu għall-quddiem tal-kju bħala l-kap

14
00:00:37,000 --> 00:00:39,000
u d-dahar bħala l-denb.

15
00:00:39,000 --> 00:00:41,000
Eżempju ta 'meta aħna jistgħu jużaw din f'applikazzjoni

16
00:00:41,000 --> 00:00:44,000
huwa waitlist għal reġistrazzjonijiet klassi.

17
00:00:44,000 --> 00:00:46,000
Kif sedili jsiru disponibbli fil-klassi,

18
00:00:46,000 --> 00:00:50,000
il-persuna fil-kap tal-lista ta 'stennija hija pprovduta l-opportunità li jinkitbu fil-klassi.

19
00:00:50,000 --> 00:00:53,000
>> A kju jistgħux jiġu mibnija bl-użu kull ġbir

20
00:00:53,000 --> 00:00:57,000
li taħżen informazzjoni sabiex, bħal firxa jew lista marbuta.

21
00:00:57,000 --> 00:01:00,000
Flimkien mal-ġbir li jaħżen l-oġġetti fil-kju,

22
00:01:00,000 --> 00:01:02,000
aħna wkoll bżonn ta 'metodu li wieħed iżid punti fl-aħħar tal-kju,

23
00:01:02,000 --> 00:01:04,000
li hija imsejħa enqueuing,

24
00:01:04,000 --> 00:01:07,000
u ieħor li tneħħi oġġett mill-kap tal-kju,

25
00:01:07,000 --> 00:01:09,000
li tissejjaħ dequeuing.

26
00:01:09,000 --> 00:01:14,000
Huwa ta 'spiss utli li tinkludi metodu ieħor li tirritorna t-tul attwali tal-kju

27
00:01:14,000 --> 00:01:17,000
kif ukoll bħala metodu biex jiċċekkjaw jekk il-kju hija vojta.

28
00:01:17,000 --> 00:01:20,000
Ejja nħarsu lejn kif nistgħu timplimenta kju tan-numri interi fis-C,

29
00:01:20,000 --> 00:01:23,000
użu ta 'firxa għall-ġbir ta' elementi.

30
00:01:23,000 --> 00:01:27,000
L-ewwel, noħolqu struttura msejħa kju biex iżommu varjabbli tagħna.

31
00:01:27,000 --> 00:01:30,000
Aħna ser tuża fiss daqs 0 indiċi firxa ta 'numri interi

32
00:01:30,000 --> 00:01:33,000
li jaħżen l-elementi.

33
00:01:33,000 --> 00:01:35,000
Aħna se jinkludi wkoll ras varjabbli imsejjaħ

34
00:01:35,000 --> 00:01:39,000
li taħżen l-indiċi ta 'l-element li huwa attwalment fir-ras ta' l-kju.

35
00:01:39,000 --> 00:01:42,000
A varjabbli tielet, imsejħa tul, se tintuża

36
00:01:42,000 --> 00:01:45,000
li jżommu rekord tan-numru ta 'elementi fil-firxa.

37
00:01:45,000 --> 00:01:48,000
Bħala alternattiva, inti tista 'tikkunsidra tuża denb varjabbli imsejjaħ

38
00:01:48,000 --> 00:01:51,000
għall-punt għall-element qasam aħħar fil-firxa.

39
00:01:51,000 --> 00:01:53,000
Qabel ma aħna jikteb il-kodiċi kwalunkwe aktar,

40
00:01:53,000 --> 00:01:55,000
ejja jippruvaw disinn tagħna.

41
00:01:55,000 --> 00:01:58,000
Nibdew ma 'firxa vojta ta' tul 0,

42
00:01:58,000 --> 00:02:02,000
bir-ras stabbiliti għal 0.

43
00:02:02,000 --> 00:02:11,000
Issa ejja enqueue 4 Valuri - 6, 2, 3, u 1.

44
00:02:11,000 --> 00:02:14,000
It-tul issa se jkun ta '4,

45
00:02:14,000 --> 00:02:17,000
u l-kap se jibqa '0.

46
00:02:17,000 --> 00:02:20,000
>> X'jiġri jekk aħna dequeue valur?

47
00:02:20,000 --> 00:02:24,000
Aħna se jnaqqas it-tul sa 3,

48
00:02:24,000 --> 00:02:28,000
jistabbilixxu l-ras għal 1,

49
00:02:28,000 --> 00:02:33,000
u jirritorna l-valur 6.

50
00:02:33,000 --> 00:02:36,000
Dik il-kodiċi tista 'tidher bħal dan.

51
00:02:36,000 --> 00:02:38,000
Hawnhekk għandna l-funzjoni dequeue,

52
00:02:38,000 --> 00:02:41,000
li tieħu pointer għall-kju - q - u pointer għall-element,

53
00:02:41,000 --> 00:02:44,000
li huwa int tip.

54
00:02:44,000 --> 00:02:47,000
L-ewwel għandna jiċċekkja t-tul tal-kju biex tagħmel ċert li huwa aktar minn 0,

55
00:02:47,000 --> 00:02:50,000
biex jiżguraw li jkun hemm element li għandu dequeued.

56
00:02:50,000 --> 00:02:54,000
Imbagħad aħna nħarsu fil-firxa elementi, il-kap pożizzjoni,

57
00:02:54,000 --> 00:02:58,000
u tistabbilixxi l-valur ta 'element li jkun il-valur f'dik il-pożizzjoni.

58
00:02:58,000 --> 00:03:01,000
Imbagħad aħna jibdlu l-ras li tkun l-indiċi li jmiss

59
00:03:01,000 --> 00:03:04,000
% Tal-kapaċità.

60
00:03:04,000 --> 00:03:07,000
Aħna mbagħad jitnaqqas it-tul tal-kju sa l-1.

61
00:03:07,000 --> 00:03:12,000
Fl-aħħarnett, nerġgħu lura minnu li jindikaw li l-dequeue kienet ta 'suċċess.

62
00:03:12,000 --> 00:03:19,000
Jekk aħna dequeue darb'oħra, it-tul se jsiru 2,

63
00:03:19,000 --> 00:03:24,000
il-kap se jsir ukoll 2,

64
00:03:24,000 --> 00:03:32,000
u l-valur tar-ritorn se jkun 2.

65
00:03:32,000 --> 00:03:35,000
>> X'jiġri jekk aħna enqueue valur ieħor bħal 7?

66
00:03:35,000 --> 00:03:37,000
Kif konna fl-aħħar tal-kju,

67
00:03:37,000 --> 00:03:47,000
ser ikollna bżonn biex nagħlaq madwar u jaħżnu l-valur fil-0 element ta 'l-array.

68
00:03:47,000 --> 00:03:50,000
Matematikament, dan jista 'jiġi rappreżentat billi żżid it-tul

69
00:03:50,000 --> 00:03:52,000
l-indiċi tar-ras

70
00:03:52,000 --> 00:03:55,000
u jwettqu modulus użu tal-kapaċità kju.

71
00:03:55,000 --> 00:04:00,000
Hawnhekk jiġifieri 2 +2, li huwa ta '4% 4,

72
00:04:00,000 --> 00:04:02,000
li hija 0.

73
00:04:02,000 --> 00:04:05,000
Traduzzjoni din l-idea għall-kodiċi li għandna din il-funzjoni.

74
00:04:05,000 --> 00:04:08,000
Hawnhekk naraw il-funzjoni enqueue,

75
00:04:08,000 --> 00:04:10,000
li tieħu pointer għall-kju - q -

76
00:04:10,000 --> 00:04:14,000
u jieħu l-element li għandu enqueued, li huwa integer.

77
00:04:14,000 --> 00:04:18,000
Aħna li jmiss jivverifika sabiex ikun żgur li l-kapaċità tal-kju

78
00:04:18,000 --> 00:04:21,000
għadu akbar mit-tul attwali tal-kju.

79
00:04:21,000 --> 00:04:24,000
Sussegwentement, aħna jaħżnu l-element fil-firxa elementi

80
00:04:24,000 --> 00:04:30,000
li l-indiċi li huwa determinat mill-kap +% tul il-kapaċità tal-kju.

81
00:04:30,000 --> 00:04:33,000
Aħna mbagħad tiżdied it-tul kju sa l-1,

82
00:04:33,000 --> 00:04:39,000
u mbagħad jirritornaw veru li jindika li l-funzjoni enqueue kienet ta 'suċċess.

83
00:04:39,000 --> 00:04:42,000
>> Minbarra l-żewġ funzjonijiet konna msemmija,

84
00:04:42,000 --> 00:04:44,000
hemm żewġ funzjonijiet addizzjonali.

85
00:04:44,000 --> 00:04:46,000
L-ewwel hija l-funzjoni isempty,

86
00:04:46,000 --> 00:04:48,000
li tieħu pointer għall-kju

87
00:04:48,000 --> 00:04:51,000
u jivverifika li t-tul huwa 0.

88
00:04:51,000 --> 00:04:53,000
It-tieni hija l-funzjoni tul,

89
00:04:53,000 --> 00:04:55,000
li wkoll jieħu pointer għall-kju

90
00:04:55,000 --> 00:04:58,000
u jirritorna l-tul attwali mill-Struct.

91
00:04:58,000 --> 00:05:03,000
Dan l-inventarju qasir wera 1 implimentazzjoni possibbli ta 'kju.

92
00:05:03,000 --> 00:05:06,000
Wieħed mill-limitazzjonijiet li din l-implimentazzjoni

93
00:05:06,000 --> 00:05:08,000
hija li l-kju għandu daqs massimu fiss.

94
00:05:08,000 --> 00:05:11,000
Jekk nippruvaw li jiżdiedu elementi aktar milli l-kju tista 'żżomm,

95
00:05:11,000 --> 00:05:14,000
għandna jistgħu jeħtieġu li jinjoraw it-talba u qatra l-element,

96
00:05:14,000 --> 00:05:17,000
jew aħna jistgħu jippreferu li jirritorna xi tip ta 'żball.

97
00:05:17,000 --> 00:05:20,000
Bl-użu ta 'lista marbut minflok firxa

98
00:05:20,000 --> 00:05:22,000
jagħmilha aktar faċli għad-daqs dinamiku-kju.

99
00:05:22,000 --> 00:05:26,000
Madankollu, peress li aħna ma jkollhomx aċċess dirett għall-elementi ta 'lista marbuta,

100
00:05:26,000 --> 00:05:28,000
jekk aħna ma jżommu rekord tad-denb,

101
00:05:28,000 --> 00:05:32,000
rridu naraw li skennjati l-lista kollha marbuta li tikseb sa l-aħħar ta kull darba.

102
00:05:32,000 --> 00:05:35,000
Aħna jista 'wkoll tikkunsidra li tuża firxa ta' tip ieħor ta 'data,

103
00:05:35,000 --> 00:05:39,000
bħal structs, li joħolqu kjuwijiet ta 'elementi aktar kumplessi.

104
00:05:39,000 --> 00:05:42,000
Thinking lura għall-eżempju tagħna ta 'waitlist klassi,

105
00:05:42,000 --> 00:05:45,000
dawn l-istrutturi jistgħu jirrappreżentaw l-istudenti individwali.

106
00:05:45,000 --> 00:05:48,000
>> Jisimni Chris Gerber, u dan huwa CS50.

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

108
00:05:51,000 --> 00:05:55,000
U l-prospetti - >> Wieħed aktar ħin.

109
00:05:55,000 --> 00:06:00,000
U r-ritorn vera li jindikaw li - l-kju kien suċċess.

110
00:06:00,000 --> 00:06:03,000
-% Tal-kapaċità tal-kju -

111
00:06:03,000 --> 00:06:06,000
Huwa ser tkun divertenti fil jeditjaw. [Daħk]