1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [कतार]

2
00:00:02,000 --> 00:00:05,000
[क्रिस Gerber, हार्वर्ड विश्वविद्यालय]

3
00:00:05,000 --> 00:00:07,000
इस CS50 है, CS50.TV]

4
00:00:07,000 --> 00:00:11,000
तत्वों के एक आदेश संग्रह के भंडारण के लिए उपयोगी डेटा संरचना एक कतार है.

5
00:00:11,000 --> 00:00:14,000
यह प्रयोग किया जाता है जब तत्वों को हटा दिया जाना चाहिए

6
00:00:14,000 --> 00:00:16,000
के रूप में वे एक ही क्रम में जोड़ा गया था.

7
00:00:16,000 --> 00:00:20,000
इस अवधारणा फीफो, जो में, 1 बाहर पहली बार के लिए एक परिचित करा रहा है के रूप में जाना जाता है.

8
00:00:20,000 --> 00:00:23,000
यह कल्पना करने में मदद करने के लिए, यह तस्वीर के लिए उपयोगी हो सकता है

9
00:00:23,000 --> 00:00:25,000
एक दुकान पर एक Checkout लाइन.

10
00:00:25,000 --> 00:00:28,000
के रूप में लोगों को आने, वे लाइन के पीछे प्रतीक्षा.

11
00:00:28,000 --> 00:00:31,000
खजांची बदल जाता है तो मोर्चे पर ग्राहकों की सेवा लेता है,

12
00:00:31,000 --> 00:00:34,000
जो तब एक समय में एक लाइन से बाहर निकलें.

13
00:00:34,000 --> 00:00:37,000
कंप्यूटर विज्ञान में, हम लाइन के सामने करने के लिए सिर के रूप में देखें

14
00:00:37,000 --> 00:00:39,000
और पूंछ के रूप में वापस.

15
00:00:39,000 --> 00:00:41,000
जब हम एक आवेदन में इस का उपयोग कर सकते हैं का एक उदाहरण

16
00:00:41,000 --> 00:00:44,000
कक्षा में नामांकन के लिए एक waitlist है.

17
00:00:44,000 --> 00:00:46,000
सीटें कक्षा में उपलब्ध हो जाते हैं,

18
00:00:46,000 --> 00:00:50,000
प्रतीक्षा सूची के सिर पर व्यक्ति कक्षा में भर्ती करने का अवसर प्रदान किया जाता है.

19
00:00:50,000 --> 00:00:53,000
>> एक कतार किसी भी संग्रह का उपयोग कर निर्माण किया जा सकता है

20
00:00:53,000 --> 00:00:57,000
कि एक सरणी या एक लिंक सूची के रूप में इस तरह के आदेश में डेटा संग्रहीत करता है.

21
00:00:57,000 --> 00:01:00,000
संग्रह के साथ कतार में वस्तुओं की दुकान,

22
00:01:00,000 --> 00:01:02,000
हम भी कतार के अंत में आइटम जोड़ने के लिए एक विधि की जरूरत है,

23
00:01:02,000 --> 00:01:04,000
जो enqueuing कहा जाता है,

24
00:01:04,000 --> 00:01:07,000
और एक अन्य कतार के सिर से एक आइटम हटाने के लिए,

25
00:01:07,000 --> 00:01:09,000
जो dequeuing कहा जाता है.

26
00:01:09,000 --> 00:01:14,000
यह उपयोगी होता है के लिए एक और विधि शामिल करने के लिए कतार की वर्तमान लंबाई वापस

27
00:01:14,000 --> 00:01:17,000
के रूप में अच्छी तरह से जाँच करने के लिए अगर कतार खाली है के लिए एक विधि के रूप में.

28
00:01:17,000 --> 00:01:20,000
चलो हम सी में integers की एक कतार कैसे लागू हो सकता है पर देखो,

29
00:01:20,000 --> 00:01:23,000
तत्वों के संग्रह के लिए एक सरणी का उपयोग.

30
00:01:23,000 --> 00:01:27,000
सबसे पहले, हम एक संरचना बुलाया कतार हमारे चर पकड़ बनाने के लिए.

31
00:01:27,000 --> 00:01:30,000
हम integers के एक निश्चित आकार 0 सूचकांक सरणी का उपयोग होगा

32
00:01:30,000 --> 00:01:33,000
तत्वों की दुकान.

33
00:01:33,000 --> 00:01:35,000
हम भी एक चर बुलाया सिर शामिल होंगे

34
00:01:35,000 --> 00:01:39,000
कि तत्व है कि कतार के सिर पर वर्तमान में है के सूचकांक में संग्रहीत करता है.

35
00:01:39,000 --> 00:01:42,000
एक तीसरा चर, लंबाई बुलाया इस्तेमाल किया जा

36
00:01:42,000 --> 00:01:45,000
सरणी में तत्वों की संख्या का ट्रैक रखने के लिए.

37
00:01:45,000 --> 00:01:48,000
एक विकल्प के रूप में, आप एक चर बुलाया पूंछ का उपयोग करने पर विचार कर सकता है

38
00:01:48,000 --> 00:01:51,000
सरणी में पिछले क्षेत्र तत्व को इंगित करने के लिए.

39
00:01:51,000 --> 00:01:53,000
इससे पहले कि हम किसी भी अधिक कोड लिखने के लिए,

40
00:01:53,000 --> 00:01:55,000
चलो बाहर हमारे डिजाइन की कोशिश.

41
00:01:55,000 --> 00:01:58,000
चलो 0 लंबाई के एक खाली सरणी के साथ शुरू करते हैं,

42
00:01:58,000 --> 00:02:02,000
साथ सिर 0 पर सेट.

43
00:02:02,000 --> 00:02:11,000
अब चलो enqueue 4 मूल्यों - 6, 2, 3, और 1.

44
00:02:11,000 --> 00:02:14,000
लंबाई अब 4 हो जाएगा,

45
00:02:14,000 --> 00:02:17,000
और सिर 0 में रहना होगा.

46
00:02:17,000 --> 00:02:20,000
>> क्या होता है अगर हम एक मूल्य विपंक्ति?

47
00:02:20,000 --> 00:02:24,000
हम 3 लंबाई कम हो जाएगा,

48
00:02:24,000 --> 00:02:28,000
1 के लिए सिर सेट,

49
00:02:28,000 --> 00:02:33,000
और 6 मूल्य वापसी.

50
00:02:33,000 --> 00:02:36,000
यही कोड इस तरह लग सकता है.

51
00:02:36,000 --> 00:02:38,000
यहाँ हम विपंक्ति समारोह,

52
00:02:38,000 --> 00:02:41,000
क्ष - जो कतार में एक सूचक लेता है और तत्व के लिए एक सूचक है,

53
00:02:41,000 --> 00:02:44,000
जो एक प्रकार int है.

54
00:02:44,000 --> 00:02:47,000
पहले हम कतार की लंबाई यकीन है कि यह 0 से अधिक है करने के लिए जाँच

55
00:02:47,000 --> 00:02:50,000
सुनिश्चित करें कि वहाँ एक तत्व के लिए dequeued है.

56
00:02:50,000 --> 00:02:54,000
तो फिर हम तत्वों सरणी में स्थिति सिर पर, देखो,

57
00:02:54,000 --> 00:02:58,000
और तत्व का मूल्य निर्धारित करने के लिए उस स्थिति में मूल्य.

58
00:02:58,000 --> 00:03:01,000
तो फिर हम सिर बदलने के लिए अगले सूचकांक

59
00:03:01,000 --> 00:03:04,000
क्षमता%.

60
00:03:04,000 --> 00:03:07,000
हम तो 1 से कतार की लंबाई कम है.

61
00:03:07,000 --> 00:03:12,000
अंत में, हम यह इंगित करने के लिए कि विपंक्ति सफल रहा था सच वापसी.

62
00:03:12,000 --> 00:03:19,000
अगर हम फिर विपंक्ति, लंबाई 2 बन जाएगा,

63
00:03:19,000 --> 00:03:24,000
सिर भी 2 बन जाएगा,

64
00:03:24,000 --> 00:03:32,000
और वापसी मान 2 हो जाएगा.

65
00:03:32,000 --> 00:03:35,000
>> क्या होता है अगर हम एक 7 के रूप में एक और मूल्य enqueue?

66
00:03:35,000 --> 00:03:37,000
जैसा कि हम कतार के अंत में थे,

67
00:03:37,000 --> 00:03:47,000
हम चारों ओर लपेट और सरणी के तत्व 0 में मूल्य की दुकान की आवश्यकता होगी.

68
00:03:47,000 --> 00:03:50,000
गणितीय, इस लंबाई जोड़कर प्रतिनिधित्व किया जा सकता है

69
00:03:50,000 --> 00:03:52,000
सिर के सूचकांक

70
00:03:52,000 --> 00:03:55,000
और एक कतार क्षमता का उपयोग कर मापांक प्रदर्शन.

71
00:03:55,000 --> 00:04:00,000
यहाँ है कि 2 2, जो 4 4% है,

72
00:04:00,000 --> 00:04:02,000
जो 0 है.

73
00:04:02,000 --> 00:04:05,000
इस विचार अनुवाद हम इस समारोह कोड.

74
00:04:05,000 --> 00:04:08,000
यहाँ हम enqueue समारोह देखने के लिए,

75
00:04:08,000 --> 00:04:10,000
क्ष - जो कतार में एक सूचक लेता है -

76
00:04:10,000 --> 00:04:14,000
और तत्व कतारबद्ध करने के लिए लेता है, जो एक पूर्णांक है.

77
00:04:14,000 --> 00:04:18,000
हम अगले जांच सुनिश्चित करने के लिए कि कतार की क्षमता

78
00:04:18,000 --> 00:04:21,000
अभी भी कतार की वर्तमान लंबाई से अधिक है.

79
00:04:21,000 --> 00:04:24,000
अगला, हम तत्वों सरणी में तत्व की दुकान

80
00:04:24,000 --> 00:04:30,000
सूचकांक में जो सिर + लंबाई% कतार की क्षमता से निर्धारित होता है.

81
00:04:30,000 --> 00:04:33,000
हम फिर 1 से कतार लंबाई बढ़ाने के लिए,

82
00:04:33,000 --> 00:04:39,000
और फिर सच लौटने के लिए संकेत मिलता है कि enqueue समारोह सफल रहा था.

83
00:04:39,000 --> 00:04:42,000
>> दो कार्यों हम उल्लेख किया है के अलावा,

84
00:04:42,000 --> 00:04:44,000
वहाँ दो अतिरिक्त कार्य कर रहे हैं.

85
00:04:44,000 --> 00:04:46,000
पहले isempty समारोह है,

86
00:04:46,000 --> 00:04:48,000
जो कतार में एक सूचक लेता है

87
00:04:48,000 --> 00:04:51,000
पुष्टि और कि लंबाई 0 है.

88
00:04:51,000 --> 00:04:53,000
2 लंबाई समारोह है,

89
00:04:53,000 --> 00:04:55,000
जो भी कतार में एक सूचक लेता है

90
00:04:55,000 --> 00:04:58,000
और struct से मौजूदा लंबाई देता है.

91
00:04:58,000 --> 00:05:03,000
इस संक्षिप्त सिंहावलोकन एक कतार के एक संभव कार्यान्वयन का प्रदर्शन किया है.

92
00:05:03,000 --> 00:05:06,000
सीमाओं के इस कार्यान्वयन के लिए एक

93
00:05:06,000 --> 00:05:08,000
यह है कि कतार एक निश्चित अधिकतम आकार है.

94
00:05:08,000 --> 00:05:11,000
यदि हम अधिक तत्वों से कतार पकड़ कर सकते हैं जोड़ने की कोशिश

95
00:05:11,000 --> 00:05:14,000
हम अनुरोध उपेक्षा और तत्व ड्रॉप की आवश्यकता हो सकती है,

96
00:05:14,000 --> 00:05:17,000
या हम त्रुटि के कुछ प्रकार लौटना पसंद कर सकते हैं.

97
00:05:17,000 --> 00:05:20,000
एक सरणी के बजाय एक लिंक सूची का उपयोग

98
00:05:20,000 --> 00:05:22,000
यह गतिशील आकार कतार को आसान बनाना होगा.

99
00:05:22,000 --> 00:05:26,000
हालांकि, के बाद से हम एक लिंक सूची के तत्वों के लिए सीधी पहुँच नहीं है,

100
00:05:26,000 --> 00:05:28,000
अगर हम पूंछ का ट्रैक नहीं रहते हो,

101
00:05:28,000 --> 00:05:32,000
हम पूरे लिंक की गई सूची को स्कैन करने के लिए समाप्त करने के लिए हर बार प्राप्त करना होगा.

102
00:05:32,000 --> 00:05:35,000
हम भी अन्य डेटा प्रकार की एक सरणी का उपयोग करने पर विचार कर सकते हैं,

103
00:05:35,000 --> 00:05:39,000
structs के रूप में इस तरह के और अधिक जटिल तत्व की कतार बनाने.

104
00:05:39,000 --> 00:05:42,000
एक वर्ग waitlist के हमारे उदाहरण के लिए वापस सोच,

105
00:05:42,000 --> 00:05:45,000
इन संरचनाओं व्यक्तिगत छात्रों का प्रतिनिधित्व कर सकता है.

106
00:05:45,000 --> 00:05:48,000
>> मेरा नाम क्रिस Gerber है, और इस CS50 है.

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

108
00:05:51,000 --> 00:05:55,000
और रिटर्न - >> एक बार.

109
00:05:55,000 --> 00:06:00,000
और संकेत मिलता है कि वापसी सच - कतार सफल रहा था.

110
00:06:00,000 --> 00:06:03,000
% कतार की क्षमता -

111
00:06:03,000 --> 00:06:06,000
यह संपादित करने में मज़ा आने वाला है. [हँसी]