덱은 큐의 양쪽 끝에서 삽입/삭제가 모두 발생할 수 있는 큐이다.
덱은 스택의 성질과 큐의 성질을 모두 갖는다.
insert_front 와 delete_front 는 front 를 top으로 보았을 때 스택의 push 와 pop 에 해당하고, insert_rear 와 delete_rear 는 rear 를 top으로 보았을 때 스택의 push 와 pop 에 해당한다.
insert_rear 와 delete_front 는 큐의 enqueue 와 dequeue 에 해당한다.
덱은 양쪽 끝에서 삽입/삭제가 발생할 수 있으므로 이중 연결 리스트(Double Linkedlist)로 구현한다.
결과>
덱은 스택의 성질과 큐의 성질을 모두 갖는다.
insert_front 와 delete_front 는 front 를 top으로 보았을 때 스택의 push 와 pop 에 해당하고, insert_rear 와 delete_rear 는 rear 를 top으로 보았을 때 스택의 push 와 pop 에 해당한다.
insert_rear 와 delete_front 는 큐의 enqueue 와 dequeue 에 해당한다.
덱은 양쪽 끝에서 삽입/삭제가 발생할 수 있으므로 이중 연결 리스트(Double Linkedlist)로 구현한다.
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
# Dequeue Implementation
# Jungtaek Lim(Heart), 2009-03-04
class DequeNode
attr_accessor :left, :right, :data
def initialize
@left = nil
@right = nil
@data = nil
end
end
class Deque
def initialize
@front = nil
@rear = nil
end
def insert_front(data)
if @front == nil
@front = DequeNode.new
@front.data = data
@rear = @front
else
node = DequeNode.new
node.data = data
node.right = @front
@front.left = node
@front = node
end
end
def delete_front
return nil if @front == nil
data = @front.data
@front = @front.right
@front.left = nil unless @front == nil
return data
end
def insert_rear(data)
if @rear == nil
@rear = DequeNode.new
@rear.data = data
@front = @rear
else
node = DequeNode.new
node.data = data
node.left = @rear
@rear.right = node
@rear = node
end
end
def delete_rear
return nil if @rear == nil
data = @rear.data
@rear = @rear.left
@rear.right = nil unless @rear == nil
return data
end
def print_deque
if @front == nil
puts "Empty Deque"
return
end
node_ptr = @front
while node_ptr != nil
print node_ptr.data
node_ptr = node_ptr.right
end
puts
end
end
deque = Deque.new
deque.insert_front('A')
deque.print_deque
deque.insert_front('B')
deque.print_deque
deque.insert_rear('C')
deque.print_deque
deque.delete_front
deque.print_deque
deque.delete_rear
deque.print_deque
deque.delete_front
deque.print_deque
|
결과>
A
BA
BAC
AC
A
Empty Deque
'Dev.Programming > DS/Algorithm' 카테고리의 다른 글
| Binary Search Tree - in Ruby (0) | 2009/03/04 |
|---|---|
| Binary Tree - in Ruby (0) | 2009/03/04 |
| Deck(Deque, Double-ended Queue) - in Ruby (0) | 2009/03/04 |
| Circular Queue - in Ruby (0) | 2009/03/04 |
| Queue - in Ruby (4) | 2009/03/04 |
| Stack - in Ruby (0) | 2009/03/03 |
