ArrayList 를 사용하여 Deque 구현하기
import java.util.ArrayList;
class MyDeque1 {
ArrayList list;
MyDeque1() {
this.list = new ArrayList();
}
public boolean isEmpty() {
if (this.list.size() == 0) {
return true;
} else {
return false;
}
}
public void addFirst(int data) {
this.list.add(0, data);
}
public void addLast(int data) {
this.list.add(data);
}
public Integer removeFirst() {
if (this.isEmpty()) {
System.out.println("Deque is empty");
return null;
}
int data = (int)this.list.get(0);
this.list.remove(0);
return data;
}
public Integer removeLast() {
if (this.isEmpty()) {
System.out.println("Deque is empty");
return null;
}
int data = (int)this.list.get(this.list.size() - 1);
this.list.remove(this.list.size() - 1);
return data;
}
public void printDeque() {
System.out.println(this.list);
}
}
public class Practice1 {
public static void main(String[] args) {
// Test code
MyDeque1 myDeque = new MyDeque1();
// Front 부분 입력
myDeque.addFirst(1);
myDeque.addFirst(2);
myDeque.addFirst(3);
myDeque.printDeque(); // 3 2 1
// Rear 부분 입력
myDeque.addLast(10);
myDeque.addLast(20);
myDeque.addLast(30);
myDeque.printDeque(); // 3 2 1 10 20 30
// Front 부분 출력
System.out.println(myDeque.removeFirst()); // 3
myDeque.printDeque(); // 2 1 10 20 30
// Rear 부분 출력
System.out.println(myDeque.removeLast()); // 30
myDeque.printDeque(); // 2 1 10 20
System.out.println(myDeque.removeLast()); // 20
System.out.println(myDeque.removeLast()); // 10
System.out.println(myDeque.removeLast()); // 1
System.out.println(myDeque.removeLast()); // 2
myDeque.printDeque();
}
}- 클래스 선언 및 멤버 변수
class MyDeque1 {
ArrayList list;
MyDeque1() {
this.list = new ArrayList();
}-class MyDeque : deque를 구현하기 위한 클래스
-ArrayList list : deque의 데이터를 저장하는 ArrayList
-MyDeque1() : deque의 생성자. ArrayList를 초기화
- deque의 비어있는지 확인하는 메서드
public boolean is Empty() {
if (this.list.size() == 0) {
return true;
} else {
return false;
}
}-isEmpty() : deque가 비어있는지 확인. list의 크기가 0이면 true를 반환하고 그렇지 않으면 false를 반환
- deque의 앞과 뒤에 요소를 추가하는 메서드
public void addFirst(int data) {
this.list.add(0, data);
}
public void addLast(int data) {
this.list.add(data);
}-addFist(int data) : deque의 앞쪽에 요소를 추가. list의 0번째 인덱스에 data를 삽입
-addLast(int data) : deque의 뒤쪽에 요소를 추가. list의 끝에 data를 추가
- deque의 앞과 뒤에서 요소를 제거하는 메서드
public Integer removeFirst() {
if (this.isEmpty()) {
System.out.println("Deque is empty");
return null;
}
int data = (int)this.list.get(0);
this.list.remove(0);
return data;
}
public Integer removeLast() {
if (this.isEmpty()) {
System.out.println("Deque is empty");
return null;
}
int data = (int)this.list.get(this.list.size() - 1);
this.list.remove(this.list.size() - 1);
return data;
}-removeFirst() : deque의 앞쪽에서 요소를 제거. deque가 비어있으면 메세지를 출력하고 null을 반환. 그렇지 않으면 list의 0번째 인덱스 요소를 제거하고 반환
-removeLast() : deque의 뒤쪽에서 요소를 제거. deque가 비어있으면 메세지를 출력하고 null을 반환. 그렇지 않으면 list의 마지막 요소를 제거하고 반환
- deque의 요소를 출력하는 메서드
public void printDeque() {
System.out.println(this.list);-printDeque() : deque의 모든 요소를 출력
배열을 사용하여 Deque를 구현하기
class MyDeque2 {
int[] arr;
int front = 0;
int rear = 0;
MyDeque2(int size) {
this.arr = new int[size + 1];
}
public boolean isEmpty() {
return this.rear == this.front;
}
public boolean isFull() {
return (this.rear + 1) % this.arr.length == this.front;
}
public void addFirst(int data) {
if (this.isFull()) {
System.out.println("Deque is Full");
return;
}
this.arr[this.front] = data;
this.front = (this.front - 1 + this.arr.length) % this.arr.length;
}
public void addLast(int data) {
if (this.isFull()) {
System.out.println("Deque is Full");
return;
}
this.rear = (this.rear + 1) % this.arr.length;
this.arr[this.rear] = data;
}
public Integer removeFirst() {
if (this.isEmpty()) {
System.out.println("Deque is empty");
return null;
}
this.front = (this.front + 1) % this.arr.length;
return this.arr[this.front];
}
public Integer removeLast() {
if (this.isEmpty()) {
System.out.println("Deque is empty");
return null;
}
int data = this.arr[this.rear];
this.rear = (this.rear - 1 + this.arr.length) % this.arr.length;
return data;
}
public void printDeque() {
int start = (this.front + 1) % this.arr.length;
int end = (this.rear + 1) % this.arr.length;
for (int i = start; i != end; i = (i + 1) % this.arr.length) {
System.out.print(this.arr[i] + " ");
}
System.out.println();
}
}
public class Practice2 {
public static void main(String[] args) {
// Test code
MyDeque2 myDeque = new MyDeque2(5);
// Front 부분 입력
myDeque.addFirst(1);
myDeque.addFirst(2);
myDeque.addFirst(3);
myDeque.printDeque(); // 3 2 1
// Rear 부분 입력
myDeque.addLast(10);
myDeque.addLast(20);
myDeque.addLast(30); // Deque is full!
myDeque.printDeque(); // 3 2 1 10 20
// Front 부분 출력
System.out.println(myDeque.removeFirst()); // 3
myDeque.printDeque(); // 2 1 10 20
// Rear 부분 출력
System.out.println(myDeque.removeLast()); // 20
myDeque.printDeque(); // 2 1 10
System.out.println(myDeque.removeLast()); // 10
System.out.println(myDeque.removeLast()); // 1
System.out.println(myDeque.removeLast()); // 2
System.out.println(myDeque.removeLast()); // Deque is empty!
}
}- 클래스 선언 및 멤버 변수
class MyDeque2 {
int[] arr;
int front = 0;
int rear = 0;
MyDeque2(int size) {
this.arr = new int[size + 1];
}-class MyDeque2 : deque를 구현하기 위한 클래스
-int[] arr : deque의 데이터를 저장하는 배열. 크기는 주어진 size보다 1 크게 설정하여 배열의 순환(circular) 구조를 쉽게 구현
-int front = 0; int rear = 0; : deque의 앞과 뒤를 가리키는 인덱스
-MyDeque2(int size) : deque의 생성자. 주어진 size에 1을 더하여 배열을 초기화
- deque가 비어있는지 확인하는 메서드
public boolean isEmpty() {
return this.rear == this.front;
}-isEmpty() : deque가 비어있는지 확인. rear과 front가 같으면 deque가 비어있는것
- deque가 가득찼는지 확인하는 메서드
public boolean isFull() {
return (this.rear + 1) % this.arr.length == this.front;
}-isFull() : deque가 가득 찼는지 확인. (rear + 1) % arr.length 가 front와 같으면 덱이 가득찬것. (이 식은 순환배열 에서 다음위치를 계산하는 방식)
- deque의 앞과 뒤에 요소를 추가하는 메서드
public void addFirst(int data) {
if (this.isFull()) {
System.out.println("Deque is Full")
return;
}
this.arr[this.front] = data;
this.front = (this.front - 1 + this.arr.length) % this.arr.length;
}
public void addLast(int data) {
if (this.isFull()) {
System.out.println("Deque is Full");
return;
}
this.rear = (this.rear + 1) % this.arr.length;
this.arr[this.rear] = data;
}-addFirst(int data) : deque의 앞쪽에 요소를 추가. deque가 가득 찼으면 메세지를 출력하고 종료. 그렇지않으면 front 인덱스를 이전 위치로 이동시킨 후 데이터를 추가
-addLast(int data) : deque의 뒤쪽에 요소를 추가. deque가 가득 찼으면 메세지를 출력하고 종료. 그렇지 않으면 rear 인덱스를 다음 위치로 이동시킨 후 데이터를 추가
- deque의 앞과 뒤에서 요소를 제거하는 메서드
public Integer removeFirst() {
if (this.isEmpty()) {
System.out.println("Deque is empty");
return null;
}
this.front = (this.front + 1) % this.arr.length;
return this.arr[this.front];
}
public Integer removeLast() {
if (this.isEmpty()) {
System.out.println("Deque is empty");
return null;
}
int data = this.arr[this.rear];
this.rear = (this.rear - 1 + this.arr.length) % this.arr.length;
return data;
}-removeFirst() : deque의 앞쪽에서 요소를 제거. deque가 비어있으면 메세지를 출력하고 null을 반환. 그렇지 않으면 front인덱스를 다음 위치로 이동시킨 후 그 위치의 데이터를 반환
-removeLast() : deque의 뒤쪽에서 요소를 제거. deque가 비어있으면 메세지를 출력하고 null을 반환. 그렇지 않으면 rear인덱스를 이전 위치로 이동시킨 후 그 위치의 데이터를 반환
- deque의 요소를 출력하는 메서드
public void printDeque() {
int start = (this.front + 1) % this.arr.length;
int end = (this.rear + 1) % this.arr.length;
for (int i = start; i != end; i = (i + 1) % this.arr.length) {
System.out.print(this.arr[i] + " ");
}
System.out.println();
}-printDeque() : deque의 모든 요소를 출력. front와 rear의 위치를 고려하고 순환배열(circular array) 구조로 요소들을 출력
