Deque를 직접 구현해보기
IT 지식/자료구조

Deque를 직접 구현해보기

반응형

큐는 삽입과 삭제가 리스트의 한쪽 방향에서만 이루어지지만 deque는 리스트의 양쪽 끝 모두에서 이루어질 수 있다.


따라서 양쪽 방향 모두 삽입과 삭제가 이루어질 수 있으므로 기존의 큐나 스택으로 사용할 수 있어 유연하게 사용할 수 있다.


사진출처 : https://dh00023.github.io/algorithm/ds/2018/04/25/algorithm-10/





이런 Deque를 직접 구현해 보자.





우선 Deque의 기능을 정리한 인터페이스이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package practice3;
 
public interface Deque<T> {
    public void addFirst(T item);
 
    public void addLast(T item);
 
    public T removeFirst();
 
    public T removeLast();
 
    public T peekFirst();
 
    public T peekLast();
 
    public boolean isEmpty();
 
    public int size();
 
    public String toString();
 
}
 
cs





그리고 인터페이스를 가지고 구현된 Deque

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
package practice3;
 
import java.util.ArrayList;
import java.util.List;
 
public class LinkedDeque<T> implements Deque<T>{
    private static class Node<T> {
        private T item;
        private Node<T> next;
        private Node<T> prev;
 
        private Node() {
            next = null;
            prev = null;
        }
 
        private Node(T item) {
            this.item = item;
            next = null;
            prev = null;
        }
    }
 
    private Node<T> front;
    private Node<T> rear;
    private int size;
 
    public LinkedDeque() {
        front = null;
        rear = null;
        size = 0;
    }
 
    @Override
    public void addLast(T item) {
        Node<T> node = new Node<>(item);
        
        if (front == null && rear == null) {
            addFirstItem(node);
        } else {
            rear.next = node;
            node.prev = rear;
            rear = node;
            size++;
        }
    }
 
    @Override
    public void addFirst(T item) {
        Node<T> node = new Node<>(item);
        
        if (front == null && rear == null) {
            addFirstItem(node);
        } else {
            front.prev = node;
            node.next = front;
            front = node;
            size++;
        }
    }
    
    private void addFirstItem(Node<T> item) {
        front = item;
        rear = item;
        size = 1;
    }
 
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
 
    @Override
    public T removeFirst() {
        T item = null;
        if (size == 0) {
            throw new java.util.NoSuchElementException("peek(): deque empty");
        } else if (size == 1) {
            item = front.item;
            front = null;
            rear = null;
            size = 0;
        } else {
            item = front.item;
            front = front.next;
            front.prev = null;
            size--;
        }
        
        return item;
    }
 
    @Override
    public T removeLast() {
        T item = null;
 
        if (size == 0) {
            throw new java.util.NoSuchElementException("peek(): deque empty");
        } else if (size == 1) {
            item = rear.item;
            front = null;
            rear = null;
            size = 0;
        } else {
            item = rear.item;
            rear = rear.prev;
            rear.next = null;
            size--;
        }
        
        return item;
    }
 
    @Override
    public T peekFirst() {
        if (size == 0)
            throw new java.util.NoSuchElementException("peek(): deque empty");
        return front.item;
    }
 
    @Override
    public T peekLast() {
        if (size == 0)
            throw new java.util.NoSuchElementException("peek(): deque empty");
        return rear.item;
    }
 
    @Override
    public int size() { return size; }
 
    @Override
    public String toString() {
        if (0 == size) {
            return "";
        } else {
            List<String> result = new ArrayList<>();
            Node<T> current;
            current = front;
            if (1 == size) {
                return current.item.toString();
            } else {
                while (current != null) {
                    result.add(current.item.toString());
                    current = current.next;
                }
                
                return String.join(",", result);
            }
            
        }
    }
 
    public String reverse() { // 역순으로 출력
        if (0 == size) {
            return "";
        } else {
            List<String> result = new ArrayList<>();
            Node<T> current;
            current = rear;
            if (1 == size) {
                return current.item.toString();
            } else {
                while (current != null) {
                    result.add(current.item.toString());
                    current = current.prev;
                }
                
                return String.join(",", result);
            }
            
        }
    }
 
}
 
cs




그리고 이 deque를 가지고 테스트를 진행할 Main클래스


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
package practice3;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        System.out.println("Enter a command: af(addFirst), al(addLast),\n"
                + "rf(removeFirst), rl(removeLast), pf(peekFirst), pl(peekLast),\n" + "p(rint), r(verse), or q(uit)");
        System.out.print("> ");
 
        Scanner input = new Scanner(System.in);
        String command = input.next();
        LinkedDeque<Integer> deque = new LinkedDeque<Integer>();
        int item;
 
        while (!command.equals("q")) {
            if (command.equals("af")) {
                item = input.nextInt();
                deque.addFirst(item);
            } else if (command.equals("al")) {
                item = input.nextInt();
                deque.addLast(item);
            } else if (command.equals("rf"))
                deque.removeFirst();
            else if (command.equals("rl"))
                deque.removeLast();
            else if (command.equals("s"))
                System.out.println("size: " + deque.size());
            else if (command.equals("pf"))
                System.out.println("Front of the deque: " + deque.peekFirst());
            else if (command.equals("pl"))
                System.out.println("Rear of the deque: " + deque.peekLast());
            else if (command.equals("r"))
                System.out.println(deque.reverse());
            else if (command.equals("p"))
                System.out.println(deque);
            System.out.print("> ");
            command = input.next();
        }
        System.out.println("Commands Terminated.");
        input.close();
    }
}
 
cs





출력결과


Enter a command: af(addFirst), al(addLast),

rf(removeFirst), rl(removeLast), pf(peekFirst), pl(peekLast),

p(rint), r(verse), or q(uit)

> af 20

> af 30

> af 10

> p

10,30,20

> rf

> p

30,20

> rl

> p

30

> al 33

> al 22

> p

30,33,22

> r

22,33,30

> p

30,33,22

> af 44

> al 88

> p

44,30,33,22,88

> rl

> rf

> p

30,33,22

> rf

> p

33,22

> rl

> p

33

> q

Commands Terminated.




다음 시간에는 이것을 이용해 버켓 정렬을 구현해보자.

반응형