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, Universitas Harvard]

3
00:00:05,000 --> 00:00:07,000
Ini adalah CS50, CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Satu berguna struktur data untuk menyimpan koleksi memerintahkan unsur adalah antrian.

5
00:00:11,000 --> 00:00:14,000
Hal ini digunakan ketika elemen perlu dihapus

6
00:00:14,000 --> 00:00:16,000
dalam urutan yang sama seperti mereka menambahkan.

7
00:00:16,000 --> 00:00:20,000
Konsep ini disebut sebagai FIFO, yang merupakan singkatan pertama, keluar pertama.

8
00:00:20,000 --> 00:00:23,000
Untuk membantu memvisualisasikan ini, mungkin berguna untuk gambar

9
00:00:23,000 --> 00:00:25,000
checkout line di toko.

10
00:00:25,000 --> 00:00:28,000
Sebagai orang tiba, mereka menunggu di belakang garis.

11
00:00:28,000 --> 00:00:31,000
Kasir kemudian bergiliran melayani pelanggan di depan,

12
00:00:31,000 --> 00:00:34,000
yang kemudian keluar dari satu baris pada satu waktu.

13
00:00:34,000 --> 00:00:37,000
Dalam ilmu komputer, kita lihat ke depan antrian sebagai kepala

14
00:00:37,000 --> 00:00:39,000
dan kembali sebagai ekor.

15
00:00:39,000 --> 00:00:41,000
Sebuah contoh ketika kita dapat menggunakan ini dalam aplikasi

16
00:00:41,000 --> 00:00:44,000
adalah daftar tunggu untuk pendaftaran kelas.

17
00:00:44,000 --> 00:00:46,000
Seperti kursi menjadi tersedia di kelas,

18
00:00:46,000 --> 00:00:50,000
orang di kepala daftar tunggu disediakan kesempatan untuk mendaftar di kelas.

19
00:00:50,000 --> 00:00:53,000
>> Sebuah antrian dapat dibangun menggunakan setiap koleksi

20
00:00:53,000 --> 00:00:57,000
yang menyimpan data dalam rangka, seperti array atau linked list.

21
00:00:57,000 --> 00:01:00,000
Seiring dengan koleksi untuk menyimpan item dalam antrian,

22
00:01:00,000 --> 00:01:02,000
kita juga perlu sebuah metode untuk menambahkan item pada akhir antrian,

23
00:01:02,000 --> 00:01:04,000
yang disebut enqueuing,

24
00:01:04,000 --> 00:01:07,000
dan lain untuk menghapus item dari kepala antrian,

25
00:01:07,000 --> 00:01:09,000
yang disebut dequeuing.

26
00:01:09,000 --> 00:01:14,000
Hal ini sering berguna untuk menyertakan metode lain untuk mengembalikan panjang saat antrian

27
00:01:14,000 --> 00:01:17,000
serta metode untuk memeriksa apakah antrian kosong.

28
00:01:17,000 --> 00:01:20,000
Mari kita lihat bagaimana kita bisa menerapkan antrian bilangan bulat di C,

29
00:01:20,000 --> 00:01:23,000
menggunakan array untuk koleksi elemen.

30
00:01:23,000 --> 00:01:27,000
Pertama, kita membuat struktur yang disebut antrian untuk memegang variabel kita.

31
00:01:27,000 --> 00:01:30,000
Kami akan menggunakan fixed-size 0 indeks array bilangan bulat

32
00:01:30,000 --> 00:01:33,000
untuk menyimpan elemen.

33
00:01:33,000 --> 00:01:35,000
Kami juga akan menyertakan kepala disebut variabel

34
00:01:35,000 --> 00:01:39,000
yang menyimpan indeks dari elemen yang saat ini di kepala antrian.

35
00:01:39,000 --> 00:01:42,000
Sebuah variabel ketiga, yang disebut panjang, akan digunakan

36
00:01:42,000 --> 00:01:45,000
untuk melacak jumlah elemen dalam array.

37
00:01:45,000 --> 00:01:48,000
Sebagai alternatif, Anda bisa mempertimbangkan untuk menggunakan ekor disebut variabel

38
00:01:48,000 --> 00:01:51,000
untuk menunjuk ke elemen field terakhir dalam array.

39
00:01:51,000 --> 00:01:53,000
Sebelum kita menulis kode lagi,

40
00:01:53,000 --> 00:01:55,000
mari kita mencoba desain kami.

41
00:01:55,000 --> 00:01:58,000
Mari kita mulai dengan array kosong dengan panjang 0,

42
00:01:58,000 --> 00:02:02,000
dengan kepala set ke 0.

43
00:02:02,000 --> 00:02:11,000
Sekarang mari kita enqueue 4 nilai - 6, 2, 3, dan 1.

44
00:02:11,000 --> 00:02:14,000
Panjang sekarang akan 4,

45
00:02:14,000 --> 00:02:17,000
dan kepala akan tinggal di 0.

46
00:02:17,000 --> 00:02:20,000
>> Apa yang terjadi jika kita dequeue nilai?

47
00:02:20,000 --> 00:02:24,000
Kami akan mengurangi panjang ke 3,

48
00:02:24,000 --> 00:02:28,000
mengatur kepala ke 1,

49
00:02:28,000 --> 00:02:33,000
dan mengembalikan nilai 6.

50
00:02:33,000 --> 00:02:36,000
Kode yang mungkin terlihat seperti ini.

51
00:02:36,000 --> 00:02:38,000
Di sini kita memiliki fungsi dequeue,

52
00:02:38,000 --> 00:02:41,000
yang membutuhkan pointer ke antrian - q - dan pointer ke elemen,

53
00:02:41,000 --> 00:02:44,000
yang merupakan tipe int.

54
00:02:44,000 --> 00:02:47,000
Pertama kita memeriksa panjang antrian untuk memastikan itu lebih dari 0,

55
00:02:47,000 --> 00:02:50,000
untuk memastikan bahwa ada elemen yang akan dequeued.

56
00:02:50,000 --> 00:02:54,000
Kemudian kita lihat dalam elemen array, di posisi kepala,

57
00:02:54,000 --> 00:02:58,000
dan menetapkan nilai elemen menjadi nilai di posisi itu.

58
00:02:58,000 --> 00:03:01,000
Kemudian kita mengubah kepala menjadi indeks berikutnya

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

60
00:03:04,000 --> 00:03:07,000
Kami kemudian mengurangi panjang antrian dengan 1.

61
00:03:07,000 --> 00:03:12,000
Akhirnya, kita kembali benar untuk menunjukkan bahwa dequeue itu berhasil.

62
00:03:12,000 --> 00:03:19,000
Jika kita dequeue lagi, panjangnya akan menjadi 2,

63
00:03:19,000 --> 00:03:24,000
kepala juga akan menjadi 2,

64
00:03:24,000 --> 00:03:32,000
dan nilai kembali akan 2.

65
00:03:32,000 --> 00:03:35,000
>> Apa yang terjadi jika kita enqueue nilai lain seperti 7?

66
00:03:35,000 --> 00:03:37,000
Ketika kami berada di ujung antrian,

67
00:03:37,000 --> 00:03:47,000
kita perlu membungkus dan menyimpan nilai dalam 0 elemen dari array.

68
00:03:47,000 --> 00:03:50,000
Secara matematis, hal ini dapat direpresentasikan dengan menambahkan panjang

69
00:03:50,000 --> 00:03:52,000
ke indeks kepala

70
00:03:52,000 --> 00:03:55,000
dan melakukan modulus menggunakan kapasitas antrian.

71
00:03:55,000 --> 00:04:00,000
Berikut yaitu 2 +2, yaitu 4% 4,

72
00:04:00,000 --> 00:04:02,000
yaitu 0.

73
00:04:02,000 --> 00:04:05,000
Menerjemahkan ide ini untuk kode kita memiliki fungsi ini.

74
00:04:05,000 --> 00:04:08,000
Di sini kita lihat fungsi enqueue,

75
00:04:08,000 --> 00:04:10,000
yang membutuhkan pointer ke antrian - q -

76
00:04:10,000 --> 00:04:14,000
dan mengambil elemen yang akan enqueued, yang merupakan integer.

77
00:04:14,000 --> 00:04:18,000
Kami selanjutnya periksa untuk memastikan bahwa kapasitas antrian

78
00:04:18,000 --> 00:04:21,000
masih lebih besar dari panjang saat antrian.

79
00:04:21,000 --> 00:04:24,000
Selanjutnya, kita menyimpan elemen dalam array elemen

80
00:04:24,000 --> 00:04:30,000
pada indeks yang ditentukan oleh kepala + panjang% kapasitas antrian.

81
00:04:30,000 --> 00:04:33,000
Kami kemudian meningkatkan panjang antrian oleh 1,

82
00:04:33,000 --> 00:04:39,000
dan kemudian kembali benar untuk menunjukkan bahwa fungsi enqueue berhasil.

83
00:04:39,000 --> 00:04:42,000
>> Selain dua fungsi yang telah kami sebutkan,

84
00:04:42,000 --> 00:04:44,000
ada dua fungsi tambahan.

85
00:04:44,000 --> 00:04:46,000
Pertama adalah fungsi isEmpty,

86
00:04:46,000 --> 00:04:48,000
yang membutuhkan pointer ke antrian

87
00:04:48,000 --> 00:04:51,000
dan memverifikasi bahwa panjangnya adalah 0.

88
00:04:51,000 --> 00:04:53,000
Yang kedua adalah fungsi panjang,

89
00:04:53,000 --> 00:04:55,000
yang juga membutuhkan pointer ke antrian

90
00:04:55,000 --> 00:04:58,000
dan mengembalikan panjang arus dari struct.

91
00:04:58,000 --> 00:05:03,000
Ini gambaran singkat telah menunjukkan salah satu kemungkinan pelaksanaan antrian.

92
00:05:03,000 --> 00:05:06,000
Salah satu keterbatasan implementasi ini

93
00:05:06,000 --> 00:05:08,000
adalah bahwa antrian memiliki ukuran maksimum tetap.

94
00:05:08,000 --> 00:05:11,000
Jika kita mencoba untuk menambahkan elemen lebih dari antrian dapat memegang,

95
00:05:11,000 --> 00:05:14,000
kita mungkin perlu untuk mengabaikan permintaan dan drop elemen,

96
00:05:14,000 --> 00:05:17,000
atau kita dapat memilih untuk kembali beberapa jenis kesalahan.

97
00:05:17,000 --> 00:05:20,000
Menggunakan linked list bukan array

98
00:05:20,000 --> 00:05:22,000
akan membuat lebih mudah untuk ukuran dinamis antrian.

99
00:05:22,000 --> 00:05:26,000
Namun, karena kita tidak memiliki akses langsung ke elemen linked list,

100
00:05:26,000 --> 00:05:28,000
jika kita tidak melacak ekor,

101
00:05:28,000 --> 00:05:32,000
kita harus memindai seluruh linked list untuk sampai ke akhir setiap kali.

102
00:05:32,000 --> 00:05:35,000
Kita juga bisa mempertimbangkan untuk menggunakan sebuah array dari jenis lain data,

103
00:05:35,000 --> 00:05:39,000
seperti structs, untuk menciptakan antrian elemen yang lebih kompleks.

104
00:05:39,000 --> 00:05:42,000
Berpikir kembali ke contoh kita dari daftar tunggu kelas,

105
00:05:42,000 --> 00:05:45,000
struktur ini dapat mewakili masing-masing siswa.

106
00:05:45,000 --> 00:05:48,000
>> Nama saya Chris Gerber, dan ini adalah CS50.

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

108
00:05:51,000 --> 00:05:55,000
Dan kembali - >> Sekali lagi.

109
00:05:55,000 --> 00:06:00,000
Dan kembali benar untuk menunjukkan bahwa - antrian berhasil.

110
00:06:00,000 --> 00:06:03,000
-% Kapasitas antrian -

111
00:06:03,000 --> 00:06:06,000
Ini akan menyenangkan di edit. [Tertawa]