Ruby实现循环队列(CircularQueue)
Varsion

昨天进行了队列的部分,准备今天把循环队列单独拿出来做一次笔记,关于Ruby的循环队列。

_没有找到什么值得参考的博文和例子,就只能自己慢慢摸索这着写。_同时参考了该题目662.设计循环队列

根据循环队列的需要列出了大概的结构框架,然后需要针对每个函数进行分析,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class LoopQueue

def initialize(size)

end

# 入队
def enQueue(item)

end

# 出队
def deQueue

end

# 判空
def is_empty?

end

# 判满
def is_full?

end
end

先来考虑的结构初始化所需要的内容:开辟循环队列所需要的空间,并指定头尾两个节点:

1
2
3
4
5
6
7
attr_reader :head, :last, :Maxsize
def initialize(size)
@Maxsize = ++size
@head = nil
@last = nil
@queue = Array.new(@Maxsize)
end

接下来考虑的是如何判满和判空

  • :当队列添加元素到last的下一个元素是head的时候,也就是转圈子要碰头了,(@last + 1) % @Maxsize == @head 我们就认为队列满了。
  • :当队列删除元素到 head == last 的时候,我们认为队列空了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def is_empty? 
if @head == @last
return true
else
return false
end
end

def is_full?
if (@last + 1) % @Maxsize == @head
return true
else
return false
end
end

最重要的两个操作是入队和出队,注意%的含义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 入队
def enQueue(item)
return false if is_full?
@queue[@last] = item
@last = (@last+1) % @Maxsize
return true
end

# 出队
def deQueue
return false if is_empty?
data = @queue[@head]
@queue[@head] = 0
@head = (@head+1) % @Maxsize
return data
end

获取队首元素和队尾元素,这里注意获取队尾时last应当-1

1
2
3
4
5
6
7
8
9
10
# 获取队首
def front
return -1 if is_empty?
return @queue[@head]
end
# 获取队尾
def rear
return -1 if is_empty?
return @queue[@last-1]
end

完整的代码我放在了最后这里:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class LoopQueue
attr_accessor :head, :last, :Maxsize
def initialize(size)
@Maxsize = size+1
@head = 0
@last = 0
@queue = Array.new(@Maxsize)
end

def getSize
return @Maxsize
end


# 入队
def enQueue(item)
return false if is_full?

@queue[@last] = item
@last = (@last+1) % @Maxsize

return true
end

# 出队
def deQueue
return false if is_empty?
data = @queue[@head]
@queue[@head] = 0
@head = (@head+1) % @Maxsize
return data
end

# 获取队首
def front
return -1 if is_empty?
return @queue[@head]
end
# 获取队尾
def rear
return -1 if is_empty?
return @queue[@last-1]
end

# 判空
def is_empty?
if @head == @last
return true
else
return false
end
end

# 判满
def is_full?
if (@last + 1) % @Maxsize == @head
return true
else
return false
end
end
end

这个代码并不符合题目662.设计循环队列的要求,我这里是根据我的编码习惯写出代码,完成题目的话,也仅仅是根据题目修改方法名称即可。

下面这个是符合题目要求的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class MyCircularQueue

=begin
Initialize your data structure here. Set the size of the queue to be k.
:type k: Integer
=end
attr_accessor :head, :last, :Maxsize
def initialize(k)
@Maxsize = k+1
@head = 0
@last = 0
@queue = Array.new(@Maxsize)
end
=begin
Insert an element into the circular queue. Return true if the operation is successful.
:type value: Integer
:rtype: Boolean
=end
def en_queue(value)
return false if is_full

@queue[@last] = value
@last = (@last+1) % @Maxsize

return true
end
=begin
Delete an element from the circular queue. Return true if the operation is successful.
:rtype: Boolean
=end
def de_queue()
return false if is_empty
data = @queue[@head]
@queue[@head] = 0
@head = (@head+1) % @Maxsize
return true
end
=begin
Get the front item from the queue.
:rtype: Integer
=end
def front()
return -1 if is_empty
return @queue[@head]
end
=begin
Get the last item from the queue.
:rtype: Integer
=end
def rear()
return -1 if is_empty
return @queue[@last-1]
end


=begin
Checks whether the circular queue is empty or not.
:rtype: Boolean
=end
def is_empty()
if @head == @last
return true
else
return false
end
end
=begin
Checks whether the circular queue is full or not.
:rtype: Boolean
=end
def is_full()
if (@last + 1) % @Maxsize == @head
return true
else
return false
end
end
end
  • Post title:Ruby实现循环队列(CircularQueue)
  • Post author:Varsion
  • Create time:2020-08-04 17:09:14
  • Post link:https://blog.varsion.cn/post/58d59d5e.html
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
Comments