forked from onlybooks/java-algorithm-interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathP26_1.java
More file actions
104 lines (92 loc) · 2.98 KB
/
P26_1.java
File metadata and controls
104 lines (92 loc) · 2.98 KB
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
package ch10;
public class P26_1 {
// 이중 연결 리스트로 사용할 클래스 선언
static class DoublyLinkedList {
// 왼쪽으로 연결할 이중 연결 리스트
DoublyLinkedList left;
// 오른쪽으로 연결할 이중 연결 리스트
DoublyLinkedList right;
int val;
public DoublyLinkedList(int val) {
this.val = val;
}
}
int len; // 현재 큐의 크기
int k; // 전체 큐의 크기
DoublyLinkedList head; // 이중 연결 리스트 head 노드
DoublyLinkedList tail; // 이중 연결 리스트 tail 노드
public P26_1(int k) {
// 이중 연결 리스트 2개 생성
head = new DoublyLinkedList(0);
tail = new DoublyLinkedList(0);
// 서로 연결
head.right = tail;
tail.left = head;
// 전체 큐의 크기 지정
this.k = k;
// 현재 큐의 크기 지정
this.len = 0;
}
public boolean insertFront(int value) {
// 꽉 차 있으면 진행하지 않음
if (isFull())
return false;
DoublyLinkedList node = new DoublyLinkedList(value);
// 신규 노드는 head 바로 오른쪽에 삽입
node.right = head.right;
node.left = head;
head.right.left = node;
head.right = node;
len++;
return true;
}
public boolean insertLast(int value) {
// 꽉 차 있으면 진행하지 않음
if (isFull())
return false;
DoublyLinkedList node = new DoublyLinkedList(value);
// 신규 노드는 tail 바로 왼쪽에 삽입
node.left = tail.left;
node.right = tail;
tail.left.right = node;
tail.left = node;
len++;
return true;
}
public boolean deleteFront() {
// 텅 비어 있다면 진행하지 않음
if (isEmpty())
return false;
// head 바로 오른쪽 노드를 연결에서 끊음
head.right.right.left = head;
head.right = head.right.right;
len--;
return true;
}
public boolean deleteLast() {
// 텅 비어 있다면 진행하지 않음
if (isEmpty())
return false;
// tail 바로 왼쪽 노드를 연결에서 끊음
tail.left.left.right = tail;
tail.left = tail.left.left;
len--;
return true;
}
public int getFront() {
// 맨 앞(head 오른쪽)의 값을 가져온다.
return (isEmpty()) ? -1 : head.right.val;
}
public int getRear() {
// 맨 뒤(tail 왼쪽)의 값을 가져온다.
return (isEmpty()) ? -1 : tail.left.val;
}
public boolean isEmpty() {
// 현재 큐의 크기가 0이면 비어 있음
return len == 0;
}
public boolean isFull() {
// 현재 큐의 크기가 처음 선언한 큐의 크기와 일치하면 꽉 차 있음
return len == k;
}
}