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

2
00:00:02,000 --> 00:00:05,000
[Chris Gerber, Harvard University]

3
00:00:05,000 --> 00:00:07,000
Detta är CS50, CS50.TV]

4
00:00:07,000 --> 00:00:11,000
En användbar datastruktur för lagring av en ordnad samling av element är en kö.

5
00:00:11,000 --> 00:00:14,000
Det används när elementen måste tas bort

6
00:00:14,000 --> 00:00:16,000
i samma ordning som de tillsattes.

7
00:00:16,000 --> 00:00:20,000
Detta koncept kallas FIFO, vilket är en förkortning för först in, först ut.

8
00:00:20,000 --> 00:00:23,000
För att hjälpa visualisera detta, kan det vara lämpligt att bilden

9
00:00:23,000 --> 00:00:25,000
en kassan linje i en butik.

10
00:00:25,000 --> 00:00:28,000
När människor kommer, väntar de på baksidan av linjen.

11
00:00:28,000 --> 00:00:31,000
Kassören tar sedan vänder betjänar kunder på framsidan,

12
00:00:31,000 --> 00:00:34,000
som sedan avsluta linjen en åt gången.

13
00:00:34,000 --> 00:00:37,000
I datavetenskap hänvisar vi till framsidan av kön som chef

14
00:00:37,000 --> 00:00:39,000
och tillbaka som svansen.

15
00:00:39,000 --> 00:00:41,000
Ett exempel på när vi kan använda detta i ett program

16
00:00:41,000 --> 00:00:44,000
är en väntelista för klass registreringar.

17
00:00:44,000 --> 00:00:46,000
Som platser blir tillgängliga i klassen,

18
00:00:46,000 --> 00:00:50,000
personen i spetsen för väntelistan finns möjlighet att anmäla dig till klassen.

19
00:00:50,000 --> 00:00:53,000
>> En kö kan konstrueras med användning av någon samling

20
00:00:53,000 --> 00:00:57,000
som lagrar data i ordning, såsom en matris eller en länkad lista.

21
00:00:57,000 --> 00:01:00,000
Tillsammans med samlingen för att lagra poster i kön,

22
00:01:00,000 --> 00:01:02,000
Vi behöver också en metod för att lägga till objekt i slutet av kön,

23
00:01:02,000 --> 00:01:04,000
som kallas enqueuing,

24
00:01:04,000 --> 00:01:07,000
och en annan för att ta bort ett objekt från chefen för kön,

25
00:01:07,000 --> 00:01:09,000
som kallas dequeuing.

26
00:01:09,000 --> 00:01:14,000
Det är ofta användbart att inkludera en annan metod för att returnera den aktuella längden på kön

27
00:01:14,000 --> 00:01:17,000
såväl som en metod för att kontrollera om kön är tom.

28
00:01:17,000 --> 00:01:20,000
Låt oss titta på hur vi kan genomföra en kö av heltal i C,

29
00:01:20,000 --> 00:01:23,000
använda en array för insamling av elementen.

30
00:01:23,000 --> 00:01:27,000
Först skapar vi en struktur som kallas kö för att hålla våra variabler.

31
00:01:27,000 --> 00:01:30,000
Vi kommer att använda en fast storlek array 0 index heltal

32
00:01:30,000 --> 00:01:33,000
att lagra elementen.

33
00:01:33,000 --> 00:01:35,000
Vi kommer också att innehålla en variabel som heter huvud

34
00:01:35,000 --> 00:01:39,000
som lagrar index för elementet som för närvarande i spetsen för kön.

35
00:01:39,000 --> 00:01:42,000
En tredje variabel, kallad längd, kommer att användas

36
00:01:42,000 --> 00:01:45,000
att hålla reda på antalet element i arrayen.

37
00:01:45,000 --> 00:01:48,000
Som ett alternativ kan du överväga att använda en variabel som heter svans

38
00:01:48,000 --> 00:01:51,000
att peka på det sista fältet elementet i arrayen.

39
00:01:51,000 --> 00:01:53,000
Innan vi skriver något mer kod,

40
00:01:53,000 --> 00:01:55,000
Låt oss prova vår design.

41
00:01:55,000 --> 00:01:58,000
Låt oss börja med en tom array med längden 0,

42
00:01:58,000 --> 00:02:02,000
med huvudet satt till 0.

43
00:02:02,000 --> 00:02:11,000
Nu ska vi köa 4 värden - 6, 2, 3, och 1.

44
00:02:11,000 --> 00:02:14,000
Längden kommer nu att 4,

45
00:02:14,000 --> 00:02:17,000
och huvudet kommer att bo på 0.

46
00:02:17,000 --> 00:02:20,000
>> Vad händer om vi avköa ett värde?

47
00:02:20,000 --> 00:02:24,000
Vi kommer att minska längden till 3,

48
00:02:24,000 --> 00:02:28,000
ställa huvudet till 1,

49
00:02:28,000 --> 00:02:33,000
och returnera värdet 6.

50
00:02:33,000 --> 00:02:36,000
Den koden kan se ut så här.

51
00:02:36,000 --> 00:02:38,000
Här har vi dequeue funktion,

52
00:02:38,000 --> 00:02:41,000
som tar en pekare till kön - q - och en pekare till elementet,

53
00:02:41,000 --> 00:02:44,000
som är en typ int.

54
00:02:44,000 --> 00:02:47,000
Först kollar vi längden på kön för att se att det är mer än 0,

55
00:02:47,000 --> 00:02:50,000
att säkerställa att det finns ett element som skall ur kön.

56
00:02:50,000 --> 00:02:54,000
Då vi tittar i elementen arrayen, i det läge huvudet,

57
00:02:54,000 --> 00:02:58,000
och ange värdet på elementet vara det värde vid denna position.

58
00:02:58,000 --> 00:03:01,000
Sedan byter vi huvudet att bli nästa index

59
00:03:01,000 --> 00:03:04,000
% Kapaciteten.

60
00:03:04,000 --> 00:03:07,000
Vi minskar då längden av kön med 1.

61
00:03:07,000 --> 00:03:12,000
Slutligen återvänder vi riktigt för att indikera att dequeue lyckades.

62
00:03:12,000 --> 00:03:19,000
Om vi ​​avköa igen, längden blir 2,

63
00:03:19,000 --> 00:03:24,000
huvudet blir också 2,

64
00:03:24,000 --> 00:03:32,000
och returvärdet blir 2.

65
00:03:32,000 --> 00:03:35,000
>> Vad händer om vi köa annat värde som en 7?

66
00:03:35,000 --> 00:03:37,000
Eftersom vi var i slutet av kön,

67
00:03:37,000 --> 00:03:47,000
kommer vi att behöva svepa runt och lagra värdet i elementet 0 av matrisen.

68
00:03:47,000 --> 00:03:50,000
Matematiskt kan detta representeras genom tillsats längden

69
00:03:50,000 --> 00:03:52,000
till index av huvudet

70
00:03:52,000 --> 00:03:55,000
och utföra en modul med kö kapacitet.

71
00:03:55,000 --> 00:04:00,000
Här som är 2 +2, vilket är 4% 4,

72
00:04:00,000 --> 00:04:02,000
vilket är 0.

73
00:04:02,000 --> 00:04:05,000
Översätta denna idé att koda vi har denna funktion.

74
00:04:05,000 --> 00:04:08,000
Här ser vi den enqueue funktion,

75
00:04:08,000 --> 00:04:10,000
som tar en pekare till kön - q -

76
00:04:10,000 --> 00:04:14,000
och tar elementet som skall kö, som är ett heltal.

77
00:04:14,000 --> 00:04:18,000
Vi kontrollerar bredvid se till att kapaciteten i kön

78
00:04:18,000 --> 00:04:21,000
är ännu större än den aktuella längden på kön.

79
00:04:21,000 --> 00:04:24,000
Sedan lagrar vi elementet i elementen arrayen

80
00:04:24,000 --> 00:04:30,000
vid indexet som bestäms av huvudet + längd% kapacitet kön.

81
00:04:30,000 --> 00:04:33,000
Vi ökar sedan kölängden med 1,

82
00:04:33,000 --> 00:04:39,000
och sedan återvända riktigt för att indikera att enqueue funktionen lyckades.

83
00:04:39,000 --> 00:04:42,000
>> Förutom de två funktioner som vi har nämnt,

84
00:04:42,000 --> 00:04:44,000
Det finns två ytterligare funktioner.

85
00:04:44,000 --> 00:04:46,000
Först är IsEmpty funktionen,

86
00:04:46,000 --> 00:04:48,000
som tar en pekare till kön

87
00:04:48,000 --> 00:04:51,000
och verifierar att längden är 0.

88
00:04:51,000 --> 00:04:53,000
Den andra är längden funktionen,

89
00:04:53,000 --> 00:04:55,000
som tar också en pekare till kön

90
00:04:55,000 --> 00:04:58,000
och returnerar den aktuella längden från struct.

91
00:04:58,000 --> 00:05:03,000
Denna korta översikt har visat en möjlig tillämpning av en kö.

92
00:05:03,000 --> 00:05:06,000
En av begränsningarna för denna implementering

93
00:05:06,000 --> 00:05:08,000
är att kön har en fast maximal storlek.

94
00:05:08,000 --> 00:05:11,000
Om vi ​​försöker att lägga till fler element än kön kan hålla,

95
00:05:11,000 --> 00:05:14,000
vi kan behöva ignorera begäran och släpp elementet,

96
00:05:14,000 --> 00:05:17,000
eller vi kanske föredrar att returnera någon typ av fel.

97
00:05:17,000 --> 00:05:20,000
Med användning av en länkad lista snarare än en matris

98
00:05:20,000 --> 00:05:22,000
skulle göra det lättare att dynamiskt storlek kön.

99
00:05:22,000 --> 00:05:26,000
Men eftersom vi inte har direkt tillgång till de delar av en länkad lista,

100
00:05:26,000 --> 00:05:28,000
om vi inte hålla reda på svansen,

101
00:05:28,000 --> 00:05:32,000
vi skulle behöva skanna hela länkad lista för att få till slutet varje gång.

102
00:05:32,000 --> 00:05:35,000
Vi kan också överväga att använda en rad av en annan datatyp,

103
00:05:35,000 --> 00:05:39,000
såsom structs att skapa köer av mer komplexa element.

104
00:05:39,000 --> 00:05:42,000
Tänker tillbaka till vårt exempel på en klass väntelista,

105
00:05:42,000 --> 00:05:45,000
dessa strukturer kunde representera de enskilda studenterna.

106
00:05:45,000 --> 00:05:48,000
>> Mitt namn är Chris Gerber, och detta är CS50.

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

108
00:05:51,000 --> 00:05:55,000
Och avkastning - >> en gång till.

109
00:05:55,000 --> 00:06:00,000
Och return true för att indikera att - kön var framgångsrik.

110
00:06:00,000 --> 00:06:03,000
-% Kapacitet kön -

111
00:06:03,000 --> 00:06:06,000
Det ska bli kul i redigera. [Skratt]