1. 덱
- Deque; Double-Ended QUEue
: 데이터의 추가/삭제를 양방향으로 모두 수행 가능한 선형 자료구조- 스택과 큐의 특성을 모두 보유
2. 덱 구현
- 전체 구현 코드는 여기에서 확인 가능
덱의 주요 기능 정의
Deque 인터페이스
package datastructure.deque;
import datastructure.queue.Queue;
import datastructure.stack.Stack;
public interface Deque<E> extends Queue<E>, Stack<E> {
void offerFirst(E e); // 덱의 맨 앞에 데이터를 추가
void offerLast(E e); // 덱의 맨 뒤에 데이터를 추가
E pollFirst(); // 덱의 맨 앞에 저장된 데이터를 덱에서 삭제한 후 반환
E pollLast(); // 덱의 맨 뒤에 저장된 데이터를 덱에서 삭제한 후 반환
E peekFirst(); // 덱의 맨 앞에 저장된 데이터를 삭제 없이 반환
E peekLast(); // 덱의 맨 뒤에 저장된 데이터를 삭제 없이 반환
boolean isEmpty(); // 빈 덱인지 확인
int getSize(); // 덱에 저장된 데이터의 개수 반환
void dump(); // 덱의 모든 데이터를 저장된 순서대로 출력
void dumpReverse(); // 덱의 모든 데이터를 저장 순서의 역순으로 출력
}Deque 인터페이스에 정의된 덱의 핵심 기능에 관한 메서드를 그대로 사용하는 것으로도 스택과 큐의 기능을 수행할 수 있지만 아래와 같이 인터페이스 업캐스팅을 통해 덱 자료구조를 어떤 용도로 사용하는지 명확히 드러나도록 구현해보고 싶었다.
Deque<Integer> deque = new ListBaseDeque();
Stack<Integer> stack = new ListBaseDeque();
Queue<Integer> queue = new ListBaseDeque();이를 위해 인터페이스가 다중 상속을 허용한다는 점을 활용하여 datastructure.deque.Deque 인터페이스가 이전에 만들었던 datastructure.stack.Stack, datastructure.queue.Queue 인터페이스를 상속받게 했다.
또한 양쪽 방향에서 데이터 노드의 추가/삭제가 가능해야 하므로 Deque 인터페이스를 구현한 ListBaseDeque 클래스에서는 이중 연결 리스트를 사용하여 덱의 핵심 기능뿐만 아니라 이를 활용한 스택, 큐의 기능 역시 구현하였다.
연결리스트를 이용한 덱의 주요 기능 구현
Node2 클래스
package datastructure.util;
public class Node2<E> {
private final E data; // 이 노드에 저장할 데이터
private Node2<E> prev; // 이 노드의 이전 노드
private Node2<E> next; // 이 노드의 다음 노드
// 노드 생성
public Node2() {
data = null;
prev = next = this;
}
public Node2(E obj, Node2<E> prev, Node2<E> next) {
this.data = obj;
this.prev = prev;
this.next = next;
}
// 이 노드에 저장된 데이터 불러오기
public E getData() {
return data;
}
// 이 노드의 다음 노드 불러오기
public Node2<E> getNext() {
return next;
}
// 이 노드의 다음 노드를 지정한 노드로 변경
public void setNext(Node2<E> next) {
this.next = next;
}
// 이 노드의 이전 노드 불러오기
public Node2<E> getPrev() {
return prev;
}
// 이 노드의 이전 노드를 지정한 노드로 변경
public void setPrev(Node2<E> prev) {
this.prev = prev;
}
}ListBaseDeque 클래스
package datastructure.deque;
import datastructure.util.Node2;
public class ListBaseDeque<E> implements Deque<E> {
// 노드의 양방 통행이 가능해야 하므로 이중 연결리스트로 구현
private Node2<E> head; // 덱의 첫번째 노드를 가리키는 변수
private Node2<E> tail; // 덱의 마지막 노드를 가리키는 변수
private int size; // 덱에 저장된 노드의 개수
// 이중 연결리스트 기반 덱 생성
public ListBaseDeque() {
size = 0; // 덱의 크기는 0으로 초기화
head = tail = null; // 덱의 머리 노드, 꼬리 노드의 위치는 null로 초기화
}
/* 덱의 핵심 기능 구현 */
// 새로운 데이터 노드를 덱의 맨 앞에 추가
@Override
public void offerFirst(E e) {
// 1. 새로운 노드 생성
Node2<E> newNode = new Node2<>(e, null, head);
if (isEmpty()) {
// 2-1. 빈 덱이면 덱의 맨 끝에 새로운 노드 추가
tail = newNode;
} else {
// 2-2. 저장된 노드가 존재하면 기존의 첫번째 노드 앞에 새로운 노드 추가
head.setPrev(newNode);
}
// 3. 덱의 첫번째 노드를 새로운 노드로 변경
head = newNode;
// 4. 덱의 크기는 1 증가
size++;
}
// 새로운 데이터를 덱의 맨 뒤에 추가
@Override
public void offerLast(E e) {
// 1. 새로운 노드 생성
Node2<E> newNode = new Node2<>(e, tail, null);
if (isEmpty()) {
// 2-1. 빈 덱이면 덱의 맨 앞에 새로운 노드 추가
head = newNode;
} else {
// 2-2. 덱에 저장된 노드가 존재하면 기존의 마지막 노드 뒤에 새로운 노드 추가
tail.setNext(newNode);
}
// 3. 덱의 마지막 노드를 새로운 노드로 변경
tail = newNode;
// 4. 덱의 크기는 1 증가
size++;
}
// 덱의 맨 앞에 저장된 노드를 삭제
@Override
public E pollFirst() {
// 빈 덱일 경우 그대로 종료
if (isEmpty()) {
return null;
}
// 1. 삭제할 첫번째 노드의 데이터는 반환해야 하므로 별도로 저장
E removedData = head.getData();
// 2. 덱의 첫번째 노드를 기존의 두번째 노드로 변경
head = head.getNext();
if (isEmpty()) {
// 3-1. 삭제 시 빈 덱이 되면 덱의 마지막 노드도 존재하지 않음
tail = null;
} else {
// 3-2. 삭제 이후에도 저장된 노드가 있다면 기존의 첫번째 노드를 삭제
head.setPrev(null);
}
// 4. 덱의 크기는 1 감소
size--;
// 5. 삭제된 데이터를 반환
return removedData;
}
// 덱의 맨 뒤에 저장된 노드를 삭제
@Override
public E pollLast() {
// 빈 노드일 경우 그대로 종료
if (isEmpty()) {
return null;
}
// 1. 삭제할 마지막 노드의 데이터는 별도로 저장
E removedData = tail.getData();
// 2. 덱의 마지막 노드를 그 직전 노드로 변경
tail = tail.getPrev();
if (isEmpty()) {
// 3-1. 삭제 시 빈 덱이 될 경우, 덱의 맨 앞에도 노드가 존재하지 않아야 함
head = null;
} else {
// 3-2. 삭제 시 여전히 저장된 노드가 있으면, 기존의 마지막 노드는 덱에서 제거됨
tail.setNext(null);
}
// 4. 덱의 크기는 1 감소
size--;
// 5. 삭제된 데이터를 반환
return removedData;
}
// 덱의 첫번째 노드에 저장된 데이터를 삭제 없이 반환
@Override
public E peekFirst() {
return head.getData();
}
// 덱의 마지막 노드에 저장된 데이터를 삭제 없이 반환
@Override
public E peekLast() {
return tail.getData();
}
// 현재 덱이 빈 덱인지 판별하는 조건
@Override
public boolean isEmpty() {
return head == null;
}
// 현재 덱에 저장된 노드의 개수
@Override
public int getSize() {
return size;
}
// 덱에 저장된 모든 데이터를 삭제
@Override
public void clear() {
while (!isEmpty()) {
pollFirst();
}
head = tail = null;
}
// 덱에 저장된 데이터를 머리->꼬리 순으로 모두 출력
@Override
public void dump() {
if (isEmpty()) {
System.out.println("Deque is empty!!");
return;
}
Node2<E> current = head;
while (current != null) {
System.out.print(head.getData() + " ");
current = current.getNext();
}
System.out.println();
}
// 덱에 저장된 데이터를 꼬리->머리 순으로 모두 출력
@Override
public void dumpReverse() {
if (isEmpty()) {
System.out.println("Deque is empty!!");
return;
}
Node2<E> current = tail;
while (current != null) {
System.out.print(current.getData() + " ");
current = current.getPrev();
}
System.out.println();
}
...(코드 생략)
}샘플 코드 및 실제 실행 결과
package datastructure.deque;
public class ListBaseDequeMain {
public static void main(String[] args) {
Deque<Integer> deque = new ListBaseDeque<>();
// 데이터 넣기 1차
System.out.println("Data adding 1:");
for (int i = 3; i >= 1; i--) {
deque.offerFirst(i);
}
for (int i = 4; i <= 6; i++) {
deque.offerLast(i);
}
// 현재 덱에 저장된 데이터를 저장 순서대로 출력
System.out.printf("Deque size: %d\n", deque.getSize());
System.out.print("Data in order: ");
deque.dump();
// 현재 덱에 저장된 데이터를 저장 순서의 역순으로 출력
System.out.print("Data in reverse order: ");
deque.dumpReverse();
System.out.println();
// 데이터 꺼내기 1차: 덱의 맨 앞에 저장된 데이터부터 삭제
System.out.println("Data removing 1:");
while (!deque.isEmpty()) {
System.out.printf("Deque element: %d, Deque size: %d\n", deque.peekFirst(), deque.getSize());
deque.pollFirst();
}
System.out.printf("Deque size: %d\n", deque.getSize());
deque.dump();
System.out.println();
// 데이터 넣기 2차(1차 때와 저장 방식, 저장되는 데이터와 그 개수는 모두 동일)
System.out.println("Data adding 2:");
for (int i = 3; i >= 1; --i) {
deque.offerFirst(i);
}
for (int i = 4; i <= 6; i++) {
deque.offerLast(i);
}
System.out.printf("Deque size: %d\n", deque.getSize());
System.out.print("Data in order: ");
deque.dump();
System.out.print("Data in reverse order: ");
deque.dumpReverse();
System.out.println();
// 데이터 꺼내기 2차: 덱의 맨 뒤에 저장된 데이터부터 삭제
System.out.println("Data removing 2:");
while (!deque.isEmpty()) {
System.out.printf("Deque element: %d, Deque size: %d\n", deque.peekLast(), deque.getSize());
deque.pollLast();
}
System.out.printf("Deque size: %d\n", deque.getSize());
deque.dump();
System.out.println();
}
}
덱을 이용한 큐의 기능 구현
ListBaseDeque 클래스 내 큐 관련 메서드
import datastructure.util.Node2;
public class ListBaseDeque<E> implements Deque<E> {
... (코드 생략)
/* queue의 주요 메서드 구현 */
// 새로운 데이터는 큐의 맨 뒤에 저장
@Override
public void enqueue(E e) {
offerLast(e);
}
// 큐의 맨 앞에 저장된 데이터를 삭제
@Override
public E dequeue() {
return pollFirst();
}
// 큐의 맨 앞에 저장된 데이터를 삭제 없이 반환
@Override
public E peek() {
return peekFirst();
}
... (코드 생략)
}실행용 샘플 코드 및 실제 실행 결과
- 실행용 샘플 코드는 이전에 작성했던
LinkedListBaseQueueMain과 동일
package datastructure.deque;
import datastructure.queue.Queue;
public class DequeBaseQueueMain {
public static void main(String[] args) {
Queue<Integer> queue = new ListBaseDeque<>();
// 연결리스트 기반 큐에 1~5의 정수를 저장
System.out.println("Adding data 1:");
for (int i = 1; i <= 5; ++i) {
queue.enqueue(i);
}
// 데이터 추가 후 큐의 길이, 저장된 데이터 출력
System.out.printf("Queue length: %d\n", queue.getSize());
System.out.print("data in queue(head->tail): ");
queue.dump();
System.out.println();
// 큐에 저장된 데이터를 1개씩 제거
System.out.println("Removing data from queue:");
while (!queue.isEmpty()) {
System.out.printf("first data: %d, Queue length: %d\n", queue.peek(), queue.getSize());
queue.dequeue();
}
System.out.println();
// 현재 큐가 빈 큐인지 확인
System.out.printf("Queue length: %d\n", queue.getSize());
if (queue.isEmpty()) {
System.out.println("Queue is empty!");
}
System.out.println();
// 동일한 데이터를 큐에 추가한 후 큐에 저장된 데이터를 모두 삭제
System.out.println("Adding data 2:");
for (int i = 1; i <= 5; i++) {
queue.enqueue(i);
}
System.out.printf("Queue length: %d\n", queue.getSize());
System.out.print("data in queue(head->tail): ");
queue.dump();
System.out.println();
System.out.println("Clearing data from queue:");
queue.clear();
System.out.printf("Queue length: %d\n", queue.getSize());
if (queue.isEmpty()) {
System.out.println("Queue is empty!!");
}
}
}
덱을 이용한 스택의 기능 구현
ListBaseDeque 클래스 내 스택 관련 메서드
peek()메서드는 이미 앞에서 구현했으므로 다루지 않음
import datastructure.util.Node2;
public class ListBaseDeque<E> implements Deque<E> {
... (코드 생략)
/* stack의 주요 메서드 */
// 스택의 맨 위에 새로운 데이터를 저장
@Override
public void push(E e) {
offerFirst(e);
}
// 스택의 맨 위에 저장된 데이터를 삭제
@Override
public E pop() {
return pollFirst();
}
}실행용 샘플 코드 및 실제 실행 결과
- 실행용 샘플 코드는 이전에 작성했던
ListBaseStackMain과 동일
package datastructure.deque;
import datastructure.stack.Stack;
public class DequeBaseStackMain {
public static void main(String[] args) {
// Stack 인터페이스로의 업캐스팅을 통해 덱을 바탕으로 구현한 스택의 기능을 사용
Stack<Integer> stack = new ListBaseDeque<>();
// 스택에 1~5까지의 정수를 순서대로 저장
for (int i = 1; i <= 5; ++i) {
stack.push(i);
}
// 현재 스택에 저장된 데이터 개수, 저장된 데이터(꼭대기 → 바닥 순) 출력
System.out.printf("Stack size: %d\n", stack.getSize());
System.out.print("data in stack(top -> bottom): ");
stack.dump();
System.out.println();
// 스택에 저장된 1개씩 꺼냈을 때, 꺼낸 데이터와 그 때의 스택의 크기 출력
while (!stack.isEmpty()) {
System.out.printf("popped: %d, stack size: %d\n", stack.peek(), stack.getSize());
stack.pop();
}
System.out.println();
// 현재 스택이 빈 스택인지 출력
System.out.println("Stack size: " + stack.getSize());
if (stack.isEmpty()) {
System.out.println("Stack is empty!!");
}
}
}
3. java.util.Deque
java.util.Deque 개괄
- Java 언어에서 덱의 주요 기능들을 정의한 인터페이스
java.util.Queue인터페이스의 자손 인터페이스java.util.LinkedList,java.util.ArrayDeque등의 컬렉션 클래스로 구현됨
java.util.Deque의 주요 메서드
데이터 추가
void addFirst(Object o)/boolean offerFirst(Object o)
- 덱의 맨 앞에 지정한 객체를 추가
void addLast(Object o)/boolean offerLast(Object o)
- 덱의 맨 뒤에 지정한 객체를 추가
void push(Object o)
- 덱의 맨 뒤에 지정한 객체를 추가
- 덱을 이용하여 스택의 데이터 추가 기능을 구현할 때 사용되는 메서드
데이터 삭제
첫번째/마지막 객체 삭제
Object removeFirst()/Object pollFirst()
- 덱의 맨 앞에 저장된 객체를 반환하면서 제거
Object removeLast()/Object removeLast()
- 덱의 맨 뒤에 저장된 객체를 반환하면서 제거
Object pop()
- 덱의 맨 뒤에 저장된 객체를 제거
- 덱을 이용하여 스택의 데이터 삭제 기능을 구현할 때 사용되는 메서드
특정 객체 삭제
boolean removeFirstOccurence(Object o)
- 지정한 객체와 첫번째로 일치하는 객체를 덱에서 제거
- 지정한 객체를 찾기 위해 덱의 맨 앞부터 차례대로 탐색
boolean removeFirstOccurence(Object o)
- 지정한 객체와 마지막으로 일치하는 객체를 덱에서 제거
- 지정한 객체를 찾기 위해 덱의 맨 뒤부터 역순으로 탐색
데이터 조회
Object getFirst()/Object peekFirst()
- 덱의 첫번째 객체를 반환
Object getLast()/Object peekLast()
- 덱의 마지막 객체를 반환
void peek()
- 덱의 첫번째 객체를 반환
- 덱을 이용하여 스택/큐의 데이터 조회 기능을 구현할 때 사용되는 메서드
: 스택에서는 마지막 데이터를, 큐에서는 첫번째 데이터를 반환
반복자 사용
Iterator descendingIterator()
- 덱을 역순으로 조회하기 위한 DescendingIterator를 반환
Iterator iterator()
- 덱을 차례대로 조회하기 위한 Iterator를 반환
Reference
- 윤성우의 열혈 자료구조(윤성우 지음)
- 자바의 정석 3판(남궁성 지음)
- Java 공식 문서 - Deque 인터페이스
