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

2
00:00:02,000 --> 00:00:05,000
[克里斯·格柏，哈佛大学]

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
这个概念被称为FIFO，这是一个缩写为先，先出。

8
00:00:20,000 --> 00:00:23,000
为了帮助可视化，它可能是有用的图片

9
00:00:23,000 --> 00:00:25,000
一个在商店的收银台。

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
类入学候补名单。

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
被称为入队

24
00:01:04,000 --> 00:01:07,000
，另一个是删除一个项目从队列头部，

25
00:01:07,000 --> 00:01:09,000
被称为出列。

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
让我们来看看我们怎么可能在C实现一个队列的整数，

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
我们将使用一个固定大小的索引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
现在，让我们排队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
到队列 -  q时 - 和一个指针的元素，需要一个指针

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
，以确保有一个元素被出列。

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
最后，我们返回true，以指示出列是成功的。

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，会发生什么事？

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
在这里，我们看到了排队功能，

75
00:04:08,000 --> 00:04:10,000
这需要一个指针到队列 -  q时 - 

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
然后返回true以指示排队功能是成功的。

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
第二个是长度函​​数，

89
00:04:53,000 --> 00:04:55,000
这也需要一个指针到队列

90
00:04:55,000 --> 00:04:58,000
从结构并返回当前的长度。

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
如结构，以创建更复杂的元素的队列中。

104
00:05:39,000 --> 00:05:42,000
回想我们的例子中的一类候补名单，

105
00:05:42,000 --> 00:05:45,000
这些结构可能代表个别学生。

106
00:05:45,000 --> 00:05:48,000
>> 我的名字是克里斯·格柏，这是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
返回true，表示 - 的队列是成功的。

110
00:06:00,000 --> 00:06:03,000
 - ％的容​​量的队列 - 

111
00:06:03,000 --> 00:06:06,000
这将是在编辑的乐趣。 [笑]