首页 > 程序开发 > 软件开发 > 其他 >

算法系列15天速成——第九天 队列

2011-12-20

可能大家都知道,线性表的变种非常非常多,比如今天讲的队列,灰常有意思啊。一:概念 队列是一个先进先出的线性表,牛X的名字就是First in First Out(FIFO), 生活中有很多这样的场景,比如读...

可能大家都知道,线性表的变种非常非常多,比如今天讲的“队列”,灰常有意思啊。

一:概念

队列是一个”先进先出“的线性表,牛X的名字就是“First in First Out(FIFO)”,

生活中有很多这样的场景,比如读书的时候去食堂打饭时的”排队“。当然我们拒绝插队。

二:存储结构

前几天也说过,线性表有两种”存储结构“,① 顺序存储,②链式存储。当然“队列”也脱离

不了这两种服务,这里我就分享一下“顺序存储”。

顺序存储时,我们会维护一个叫做”head头指针“和”tail尾指针“,分别指向队列的开头和结尾。

\

代码段如下:

1 #region 队列的数据结构

2 /// <summary>

3 /// 队列的数据结构

4 /// </summary>

5 /// <typeparam name="T"></typeparam>

6 public class SeqQueue<T>

7 {

8 private const int maxSize = 100;

9

10 public int MaxSize

11 {

12 get { return maxSize; }

13 }

14

15 /// <summary>

16 /// 顺序队列的存储长度

17 /// </summary>

18 public T[] data = new T[maxSize];

19

20 //头指针

21 public int head;

22

23 //尾指针

24 public int tail;

25

26 }

27 #endregion

三:常用操作

队列的操作一般分为:

①: 初始化队列。

②: 出队。

③: 入队。

④: 获取队头。

⑤: 获取队长。

1:初始化队列

这个很简单,刚才也说过了,队列是用一个head和tail的指针来维护。分别设置为0即可。

2:出队

看着“队列”的结构图,大家都知道,出队肯定跟head指针有关,需要做两件事情,

第一: 判断队列是否为空,这个我想大家都知道。

第二: 将head头指针向后移动一位,返回head移动前的元素,时间复杂度为O(1)。

\

代码段如下:

1 #region 队列元素出队

2 /// <summary>

3 /// 队列元素出队

4 /// </summary>

5 /// <typeparam name="T"></typeparam>

6 /// <param name="seqQueue"></param>

7 /// <returns></returns>

8 public T SeqQueueOut<T>(SeqQueue<T> seqQueue)

9 {

10 if (SeqQueueIsEmpty(seqQueue))

11 throw new Exception("队列已空,不能进行出队操作");

12

13 var single = seqQueue.data[seqQueue.head];

14

15 //head指针自增

16 seqQueue.data[seqQueue.head++] = default(T);

17

18 return single;

19

20 }

21 #endregion

www.2cto.com

3:入队

这个跟”出队“的思想相反,同样也是需要做两件事情。

第一:判断队列是否已满。

第二:将tail指针向后移动一位,时间复杂度为O(1)。

代码段如下:

1 #region 队列元素入队

2 /// <summary>

3 /// 队列元素入队

4 /// </summary>

5 /// <typeparam name="T"></typeparam>

6 /// <param name="seqQueue"></param>

7 /// <param name="data"></param>

8 /// <returns></returns>

9 public SeqQueue<T> SeqQueueIn<T>(SeqQueue<T> seqQueue, T data)

10 {

11 //如果队列已满,则不能进行入队操作

12 if (SeqQueueIsFull(seqQueue))

13 throw new Exception("队列已满,不能入队操作");

14

15 //入队操作

16 seqQueue.data[seqQueue.tail++] = data;

17

18 return seqQueue;

19 }

20 #endregion

www.2cto.com

4: 获取队头

知道”出队“和”入队“的原理,相信大家都懂的如何进行”获取队头“操作,唯一不一样的就是

他是只读操作,不会破坏”队列“结构,时间复杂度为O(1)。

代码段如下:

#region 获取队头元素

/// <summary>

/// 获取队头元素

/// </summary>

/// <typeparam name="T"></typeparam>

/// <param name="seqQueue"></param>

/// <returns></returns>

public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)

{

if (SeqQueueIsEmpty(seqQueue))

throw new Exception("队列已空,不能进行出队操作");

return seqQueue.data[seqQueue.head];

}

#endregion

www.2cto.com

5: 获取队长

大家都知道,我们是用数组来实现队列,所以千万不要想当然的认为数组长度是XXX,

我们维护的是一个head和tail的指针,所以长度自然就是tail-head咯,时间复杂度为O(1)。

\

代码段如下:

1 /// <summary>

2 /// 获取队列长度

3 /// </summary>

4 /// <typeparam name="T"></typeparam>

5 /// <param name="seqQueue"></param>

6 /// <returns></returns>

7 public int SeqQueueLen<T>(SeqQueue<T> seqQueue)

8 {

9 return seqQueue.tail - seqQueue.head;

10 }

www.2cto.com

然后上一下总的运行代码:

View Code

1 using System;

2 using System.Collections.Generic;

3 using System.Linq;

4 using System.Text;

5

6 namespace SeqQueue

7 {

8 public class Program

9 {

10 static void Main(string[] args)

11 {

12 SeqQueue<Student> seqQueue = new SeqQueue<Student>();

13

14 SeqQueueClass queueManage = new SeqQueueClass();

15

16 Console.WriteLine("目前队列是否为空:" + queueManage.SeqQueueIsEmpty(seqQueue) + "\n");

17

18 Console.WriteLine("将ID=1和ID=2的实体加入队列");

19 queueManage.SeqQueueIn(seqQueue, new Student() { ID = 1, Name = "hxc520", Age = 23 });

20 queueManage.SeqQueueIn(seqQueue, new Student() { ID = 2, Name = "一线码农", Age = 23 });

21

22 Display(seqQueue);

23

24 Console.WriteLine("将队头出队");

25 //将队头出队

26 var student = queueManage.SeqQueueOut(seqQueue);

27

28 Display(seqQueue);

29

30 //获取队顶元素

31 student = queueManage.SeqQueuePeek(seqQueue);

32

33 Console.Read();

34 }

35 //展示队列元素

36 static void Display(SeqQueue<Student> seqQueue)

37 {

38 Console.WriteLine("******************* 链表数据如下*******************");

39

40 for (int i = seqQueue.head; i < seqQueue.tail; i++)

41 Console.WriteLine("ID:" + seqQueue.data[i].ID +

42 ",Name:" + seqQueue.data[i].Name +

43 ",Age:" + seqQueue.data[i].Age);

44

45 Console.WriteLine("******************* 链表数据展示完毕*******************\n");

46 }

47 }

48

49 #region 学生数据实体

50 /// <summary>

51 /// 学生数据实体

52 /// </summary>

53 public class Student

54 {

55 public int ID { get; set; }

56

57 public string Name { get; set; }

58

59 public int Age { get; set; }

60 }

61 #endregion

62

63 #region 队列的数据结构

64 /// <summary>

65 /// 队列的数据结构

66 /// </summary>

67 /// <typeparam name="T"></typeparam>

68 public class SeqQueue<T>

69 {

70 private const int maxSize = 100;

71

72 public int MaxSize

73 {

74 get { return maxSize; }

75 }

76

77 /// <summary>

78 /// 顺序队列的存储长度

79 /// </summary>

80 public T[] data = new T[maxSize];

81

82 //头指针

83 public int head;

84

85 //尾指针

86 public int tail;

87

88 }

89 #endregion

90

91 #region 队列的基本操作

92 /// <summary>

93 /// 队列的基本操作

94 /// </summary>

95 public class SeqQueueClass

96 {

97 #region 队列的初始化操作

98 /// <summary>

99 /// 队列的初始化操作

100 /// </summary>

101 /// <typeparam name="T"></typeparam>

102 /// <param name="seqQueue"></param>

103 public SeqQueue<T> SeqQueueInit<T>(SeqQueue<T> seqQueue)

104 {

105 seqQueue.head = 0;

106 seqQueue.tail = 0;

107

108 return seqQueue;

109 }

110 #endregion

111

112 #region 队列是否为空

113 /// <summary>

114 /// 队列是否为空

115 /// </summary>

116 /// <typeparam name="T"></typeparam>

117 /// <param name="seqQueue"></param>

118 /// <returns></returns>

119 public bool SeqQueueIsEmpty<T>(SeqQueue<T> seqQueue)

120 {

121 //如果两指针重合,说明队列已经清空

122 if (seqQueue.head == seqQueue.tail)

123 return true;

124 return false;

125 }

126 #endregion

127

128 #region 队列是否已满

129 /// <summary>

130 /// 队列是否已满

131 /// </summary>

132 /// <typeparam name="T"></typeparam>

133 /// <param name="seqQueue"></param>

134 /// <returns></returns>

135 public bool SeqQueueIsFull<T>(SeqQueue<T> seqQueue)

136 {

137 //如果尾指针到达数组末尾,说明队列已经满

138 if (seqQueue.tail == seqQueue.MaxSize)

139 return true;

140 return false;

141 }

142 #endregion

143

144 #region 队列元素入队

145 /// <summary>

146 /// 队列元素入队

147 /// </summary>

148 /// <typeparam name="T"></typeparam>

149 /// <param name="seqQueue"></param>

150 /// <param name="data"></param>

151 /// <returns></returns>

152 public SeqQueue<T> SeqQueueIn<T>(SeqQueue<T> seqQueue, T data)

153 {

154 //如果队列已满,则不能进行入队操作

155 if (SeqQueueIsFull(seqQueue))

156 throw new Exception("队列已满,不能入队操作");

157

158 //入队操作

159 seqQueue.data[seqQueue.tail++] = data;

160

161 return seqQueue;

162 }

163 #endregion

164

165 #region 队列元素出队

166 /// <summary>

167 /// 队列元素出队

168 /// </summary>

169 /// <typeparam name="T"></typeparam>

170 /// <param name="seqQueue"></param>

171 /// <returns></returns>

172 public T SeqQueueOut<T>(SeqQueue<T> seqQueue)

173 {

174 if (SeqQueueIsEmpty(seqQueue))

175 throw new Exception("队列已空,不能进行出队操作");

176

177 var single = seqQueue.data[seqQueue.head];

178

179 //head指针自增

180 seqQueue.data[seqQueue.head++] = default(T);

181

182 return single;

183

184 }

185 #endregion

186

187 #region 获取队头元素

188 /// <summary>

189 /// 获取队头元素

190 /// </summary>

191 /// <typeparam name="T"></typeparam>

192 /// <param name="seqQueue"></param>

193 /// <returns></returns>

194 public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)

195 {

196 if (SeqQueueIsEmpty(seqQueue))

197 throw new Exception("队列已空,不能进行出队操作");

198

199 return seqQueue.data[seqQueue.head];

200 }

201 #endregion

202

203 /// <summary>

204 /// 获取队列长度

205 /// </summary>

206 /// <typeparam name="T"></typeparam>

207 /// <param name="seqQueue"></param>

208 /// <returns></returns>

209 public int SeqQueueLen<T>(SeqQueue<T> seqQueue)

210 {

211 return seqQueue.tail - seqQueue.head;

212 }

213 }

214 #endregion

215 }

\

三:顺序队列的缺陷

\

大家看这张图,不知道可有什么异样的感觉,在这种状态下,我入队操作,发现程序提示队列

已满,但是tnd我这个数组还有一个空间啊,是的,这就是所谓的“假溢出”

四:循环队列

俗话说的好啊,“没有跨不过的坎”。

1: 概念

之所以叫“循环”,得益于神奇的“%”。他让队列的首位进行相连,形成了一个我们思维中的

“圈圈”。

2:循环公式

tail=(tail+1)%array.Length;

多看几眼,大家就看通了其中循环的道理,我要做成如下的图:

\

3:对循环的改造

先前看了一些资料,有的压根就是错的,有的说想要循环,就要牺牲一个单位的空间。

我觉得没必要。我既要循环又不牺牲空间,所以反射了一下framework中的Queue类。

改造后代码如下:

1 using System;

2 using System.Collections.Generic;

3 using System.Linq;

4 using System.Text;

5

6 namespace SeqQueue

7 {

8 public class Program

9 {

10 static void Main(string[] args)

11 {

12 SeqQueue<Student> seqQueue = new SeqQueue<Student>();

13

14 SeqQueueClass queueManage = new SeqQueueClass();

15

16 Console.WriteLine("目前队列是否为空:" + queueManage.SeqQueueIsEmpty(seqQueue) + "\n");

17

18 Console.WriteLine("将ID=1,2,3的实体加入队列\n");

19 queueManage.SeqQueueIn(seqQueue, new Student() { ID = 1, Name = "hxc520", Age = 23 });

20 queueManage.SeqQueueIn(seqQueue, new Student() { ID = 2, Name = "一线码农", Age = 23 });

21 queueManage.SeqQueueIn(seqQueue, new Student() { ID = 3, Name = "51cto", Age = 23 });

22

23 Console.WriteLine("\n当前队列个数:" + queueManage.SeqQueueLen(seqQueue) + "");

24

25 Console.WriteLine("\n*********************************************\n");

26

27 Console.WriteLine("我要出队了\n");

28 queueManage.SeqQueueOut(seqQueue);

29

30 Console.WriteLine("哈哈,看看跟顺序队列异样之处,我再入队,看是否溢出\n");

31 queueManage.SeqQueueIn(seqQueue, new Student() { ID = 4, Name = "博客园", Age = 23 });

32 Console.WriteLine("\n....一切正常,入队成功");

33

34 Console.WriteLine("\n当前队列个数:" + queueManage.SeqQueueLen(seqQueue) + "");

35

36 Console.Read();

37 }

38 }

39

40 #region 学生数据实体

41 /// <summary>

42 /// 学生数据实体

43 /// </summary>

44 public class Student

45 {

46 public int ID { get; set; }

47

48 public string Name { get; set; }

49

50 public int Age { get; set; }

51 }

52 #endregion

53

54 #region 队列的数据结构

55 /// <summary>

56 /// 队列的数据结构

57 /// </summary>

58 /// <typeparam name="T"></typeparam>

59 public class SeqQueue<T>

60 {

61 private const int maxSize = 3;

62

63 public int MaxSize

64 {

65 get { return maxSize; }

66 }

67

68 /// <summary>

69 /// 顺序队列的存储长度

70 /// </summary>

71 public T[] data = new T[maxSize];

72

73 //头指针

74 public int head;

75

76 //尾指针

77 public int tail;

78

79 //队列中有效的数字个数

80 public int size;

81 }

82 #endregion

83

84 #region 队列的基本操作

85 /// <summary>

86 /// 队列的基本操作

87 /// </summary>

88 public class SeqQueueClass

89 {

90 #region 队列的初始化操作

91 /// <summary>

92 /// 队列的初始化操作

93 /// </summary>

94 /// <typeparam name="T"></typeparam>

95 /// <param name="seqQueue"></param>

96 public SeqQueue<T> SeqQueueInit<T>(SeqQueue<T> seqQueue)

97 {

98 seqQueue.size = seqQueue.head = seqQueue.tail = 0;

99

100 return seqQueue;

101 }

102 #endregion

103

104 #region 队列是否为空

105 /// <summary>

106 /// 队列是否为空

107 /// </summary>

108 /// <typeparam name="T"></typeparam>

109 /// <param name="seqQueue"></param>

110 /// <returns></returns>

111 public bool SeqQueueIsEmpty<T>(SeqQueue<T> seqQueue)

112 {

113 //如果两指针重合,说明队列已经清空

114 if (seqQueue.size == 0)

115 return true;

116 return false;

117 }

118 #endregion

119

120 #region 队列是否已满

121 /// <summary>

122 /// 队列是否已满

123 /// </summary>

124 /// <typeparam name="T"></typeparam>

125 /// <param name="seqQueue"></param>

126 /// <returns></returns>

127 public bool SeqQueueIsFull<T>(SeqQueue<T> seqQueue)

128 {

129 //采用循环队列后,头指针

130 if (seqQueue.size == seqQueue.MaxSize)

131 return true;

132 return false;

133 }

134 #endregion

135

136 #region 队列元素入队

137 /// <summary>

138 /// 队列元素入队

139 /// </summary>

140 /// <typeparam name="T"></typeparam>

141 /// <param name="seqQueue"></param>

142 /// <param name="data"></param>

143 /// <returns></returns>

144 public SeqQueue<T> SeqQueueIn<T>(SeqQueue<T> seqQueue, T data)

145 {

146 //如果队列已满,则不能进行入队操作

147 if (SeqQueueIsFull(seqQueue))

148 throw new Exception("队列已满,还入啥队列啊!");

149

150 //采用循环队列,必须先赋值,在自增tail指针

151 seqQueue.data[seqQueue.tail] = data;

152 seqQueue.tail = (seqQueue.tail + 1) % seqQueue.MaxSize;

153

154 //队列实际元素增加

155 seqQueue.size++;

156

157 return seqQueue;

158 }

159 #endregion

160

161 #region 队列元素出队

162 /// <summary>

163 /// 队列元素出队

164 /// </summary>

165 /// <typeparam name="T"></typeparam>

166 /// <param name="seqQueue"></param>

167 /// <returns></returns>

168 public T SeqQueueOut<T>(SeqQueue<T> seqQueue)

169 {

170 if (SeqQueueIsEmpty(seqQueue))

171 throw new Exception("队列已空,大哥,不要在出队了!");

172

173 //循环队列出队,展现的是head的灵活性

174 seqQueue.head = (seqQueue.head + 1) % seqQueue.MaxSize;

175

176 //队列实际元素递减

177 seqQueue.size--;

178

179 return seqQueue.data[seqQueue.head];

180 }

181 #endregion

182

183 #region 获取队头元素

184 /// <summary>

185 /// 获取队头元素

186 /// </summary>

187 /// <typeparam name="T"></typeparam>

188 /// <param name="seqQueue"></param>

189 /// <returns></returns>

190 public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)

191 {

192 if (SeqQueueIsEmpty(seqQueue))

193 throw new Exception("队列已空,不能进行出队操作");

194

195 return seqQueue.data[seqQueue.head];

196 }

197 #endregion

198

199 #region 获取队列长度

200 /// <summary>

201 /// 获取队列长度

202 /// </summary>

203 /// <typeparam name="T"></typeparam>

204 /// <param name="seqQueue"></param>

205 /// <returns></returns>

206 public int SeqQueueLen<T>(SeqQueue<T> seqQueue)

207 {

208 return seqQueue.size;

209 }

210 #endregion

211 }

212 #endregion

213 }

\

摘自 一线码农

相关文章
最新文章
热点推荐