[Algorithm] 덱(Deque)
Updated:
1. 개요
덱(Deque)은 Double Ended Queue의 약자로, 양 끝에서 자료를 넣고 뺼 수 있는 자료구조이고, push_front, push_back, pop_front, pop_back, front, back, size, empty 8개의 명령이 존재한다. 예제를 통해 덱(Deque)의 동작 방식에 대해 알아보도록 하자.
-
push_front {걊} : 덱의 맨 앞에 값을 넣음
-
push_back {값} : 덱의 맨 뒤에 값을 넣음
-
pop_front : 덱의 맨 앞의 데이터를 뺌
-
pop_back : 덱의 맨 뒤의 데이터를 뺌
-
front : 덱의 맨 앞의 값을 반환
-
back : 덱의 맨 뒤의 값을 반환
-
size : 덱의 크기 반환
-
empty : 덱이 비어있는지 여부 반환(비어있으면 true, 비어있지 않으면 false)
2. 예제
-
명령 : push_back 1 / 반환값 : X
덱의 빈 공간 중 가장 뒤에 1을 넣는다.
-
명령 : push_front 2 / 반환값 : X
덱의 빈 공간 중 가장 앞에 2를 넣는다.
-
명령 : front / 반환값 : 2
덱의 맨 앞의 값인 2를 반환한다.
-
명령 : back / 반환값 : 1
덱의 맨 뒤의 값인 1을 반환한다.
-
명령 : size / 반환값 : 2
덱에 들어있는 값의 크기(갯수)를 반환한다.
-
명령 : empty / 반환값 : false
덱이 비어있지 않으므로 false를 반환한다.
-
명령 : pop_front / 반환값 : X
덱의 맨 앞의 값인 2를 뺀다.
-
명령 : pop_back / 반환값 : X
덱의 맨 뒤의 값인 1을 뺀다.
-
명령 : empty / 반환값 : true
덱이 비어있으므로 true를 반환한다.
3. 구현 코드
3-1. C++
3-1-1. 구현
[소스 코드]
https://github.com/dev-aiden/problem-solving/blob/main/algorithm/deque.cpp
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
#include <iostream>
#include <vector>
using namespace std;
vector<int> v(20003);
int main(void) {
ios_base::sync_with_stdio(false);
int begin = 10000, end = 10001;
int n; for (cin >> n; n--;) {
string cmd; cin >> cmd;
if (cmd == "push_front") {
int num; cin >> num;
v[begin--] = num;
} else if (cmd == "push_back") {
int num; cin >> num;
v[end++] = num;
} else if (cmd == "pop_front") {
if (begin == end - 1) {
cout << "-1" << "\n";
} else {
cout << v[++begin] << "\n";
v[begin] = 0;
}
} else if (cmd == "pop_back") {
if (begin == end - 1) {
cout << "-1" << "\n";
}
else {
cout << v[--end] << "\n";
v[end] = 0;
}
} else if (cmd == "size") {
cout << end - begin - 1 << "\n";
} else if (cmd == "empty") {
cout << (begin == end - 1 ? 1 : 0) << "\n";
} else if (cmd == "front") {
cout << (begin == end - 1 ? -1 : v[begin + 1]) << "\n";
} else if (cmd == "back") {
cout << (begin == end - 1 ? -1 : v[end - 1]) << "\n";
}
}
return 0;
}
[실행 결과]
3-1-2. 라이브러리 이용
[소스 코드]
https://github.com/dev-aiden/problem-solving/blob/main/algorithm/deque2.cpp
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
#include <iostream>
#include <deque>
using namespace std;
deque<int> d;
int main(void) {
ios_base::sync_with_stdio(false);
int n; for (cin >> n; n--;) {
string cmd; cin >> cmd;
if (cmd == "push_front") {
int num; cin >> num;
d.push_front(num);
} else if (cmd == "push_back") {
int num; cin >> num;
d.push_back(num);
} else if (cmd == "pop_front") {
if (d.empty()) {
cout << "-1\n";
} else {
cout << d.front() << "\n";
d.pop_front();
}
} else if (cmd == "pop_back") {
if (d.empty()) {
cout << "-1\n";
}
else {
cout << d.back() << "\n";
d.pop_back();
}
} else if (cmd == "size") {
cout << d.size() << "\n";
} else if (cmd == "empty") {
cout << d.empty() << "\n";
} else if (cmd == "front") {
if (d.empty()) cout << "-1\n";
else cout << d.front() << "\n";
} else if (cmd == "back") {
if (d.empty()) cout << "-1\n";
else cout << d.back() << "\n";
}
}
return 0;
}
[실행 결과]
3-2. JAVA
3-2-1. 구현
[소스 코드]
https://github.com/dev-aiden/problem-solving/blob/main/algorithm/deque.java
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class DequeExample {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int arr[] = new int[20003];
int begin = 10000, end = 10001;
int n = Integer.parseInt(br.readLine());
for(int i = 0; i < n; ++i) {
StringTokenizer st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
if(cmd.equals("push_front")) {
int num = Integer.parseInt(st.nextToken());
arr[begin--] = num;
} else if(cmd.equals("push_back")) {
int num = Integer.parseInt(st.nextToken());
arr[end++] = num;
} else if(cmd.equals("pop_front")) {
if(begin == end - 1) {
sb.append("-1").append("\n");
} else {
sb.append(arr[++begin]).append("\n");
arr[begin] = 0;
}
} else if(cmd.equals("pop_back")) {
if(begin == end - 1) {
sb.append("-1").append("\n");
} else {
sb.append(arr[--end]).append("\n");
arr[end] = 0;
}
} else if(cmd.equals("size")) {
sb.append(end - begin - 1).append("\n");
} else if(cmd.equals("empty")) {
sb.append(begin == end - 1 ? 1 : 0).append("\n");
} else if(cmd.equals("front")) {
sb.append(begin == end - 1 ? -1 : arr[begin + 1]).append("\n");
} else if(cmd.equals("back")) {
sb.append(begin == end - 1? -1 : arr[end - 1]).append("\n");
}
}
System.out.println(sb);
}
}
[실행 결과]
3-2-2. 라이브러리 이용
[소스 코드]
https://github.com/dev-aiden/problem-solving/blob/main/algorithm/deque2.java
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class DequeExample {
static Deque<Integer> d = new ArrayDeque<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
for(int i = 0; i < n; ++i) {
StringTokenizer st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
if(cmd.equals("push_front")) {
d.offerFirst(Integer.parseInt(st.nextToken()));
} else if(cmd.equals("push_back")) {
d.offerLast(Integer.parseInt(st.nextToken()));
} else if(cmd.equals("pop_front")) {
if(d.isEmpty()) sb.append("-1\n");
else sb.append(d.pollFirst()).append("\n");
} else if(cmd.equals("pop_back")) {
if(d.isEmpty()) sb.append("-1\n");
else sb.append(d.pollLast()).append("\n");
} else if(cmd.equals("size")) {
sb.append(d.size()).append("\n");
} else if(cmd.equals("empty")) {
sb.append(d.isEmpty() ? 1 : 0).append("\n");
} else if(cmd.equals("front")) {
if(d.isEmpty()) sb.append("-1\n");
else sb.append(d.getFirst()).append("\n");
} else if(cmd.equals("back")) {
if(d.isEmpty()) sb.append("-1\n");
else sb.append(d.getLast()).append("\n");
}
}
System.out.println(sb);
}
}
[실행 결과]
Leave a comment