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

2011-12-20

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 //头指针

22

23 //尾指针

24 public int tail;

25

26 }

27 #endregion

①： 初始化队列。

②: 出队。

③： 入队。

④： 获取队头。

⑤： 获取队长。

1：初始化队列

2：出队

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

14

17

18 return single;

19

20 }

21 #endregion

www.2cto.com

3：入队

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： 获取队头

#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("队列已空，不能进行出队操作");

}

#endregion

www.2cto.com

5: 获取队长

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 {

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

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 //头指针

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 {

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 //如果两指针重合，说明队列已经清空

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

178

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

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 {

212 }

213 }

214 #endregion

215 }

1: 概念

“圈圈”。

2：循环公式

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

3：对循环的改造

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

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 //头指针

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

175

176 //队列实际元素递减

177 seqQueue.size--;

178

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

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 }