[자료구조] 데크

달공·2022년 11월 21일
0

자료구조

목록 보기
6/7
post-thumbnail

데크 (Dequeue) 란?

  • 양쪽에서 삽입과 삭제가 모두 가능한 구조

  • Double-ended-queue의 줄임말

  • 입력 제한 데크 : 한 쪽 입력을 제한한 데크 (Scroll)

  • 출력 제한 데크 : 한 쪽 출력을 제한한 데크 (Shelf)

데크의 연산

  • addFirst() : front 부분 입력

  • addLast() : last 부분 입력

  • removeFirst() / removeLast() : 출력

위 메서드 말고도 poll, offer, push, pop 모두 사용 가능하다.

데크의 구현 1 - ArrayDeque

아래와 같이 ArrayDeque를 통해 Deque를 구현할 수 있다.

import java.util.ArrayDeque;
import java.util.Deque;
 
public class Main {
    public static void main(String[] args) {
        Deque deque = new ArrayDeque();
 
        // Front 부분 입력
        deque.addFirst(1);
 
        // Rear 부분 입력
        deque.addLast(10);
        deque.addLast(20);
 
        // Front 부분 출력
        System.out.println(deque.removeFirst());
       
        // Rear 부분 출력
        System.out.println(deque.removeLast());
 
        System.out.println(deque.pollLast());
        System.out.println(deque);
    }
}

데크의 구현 2 - ArrayList

MyDeque를 ArrayList를 통해 구현해보는 과정이다. 데크 또한, 빈 데크인지 확인해주는 과정이 필수적이다.

class MyDeque {
    ArrayList list;

    MyDeque1() {
        this.list = new ArrayList();
    }

    public boolean isEmpty() {
        if (this.list.size() == 0) {
            return true;
        } else {
            return false;
        }
    }

데크의 경우, 양방향에서 데이터 삽입, 반출이 가능하기 때문에 각 연산에 해당되는 메서드들을 ArrayList 구조에 맞춰 구현해주어야한다.

데이터 삽입

Front 방향으로 데이터를 삽입할 경우, 위치를 지정해주어야하지만 Last라면 그냥 데이터를 추가하면 된다.

데이터 삭제

데이터를 삭제할 때는 데크의 empty 여부를 먼저 확인해주어야한다.
해당 위치에 해당하는 데이터의 값을 data 변수에 넣는다.
실제 list 안에 해당 위치의 데이터를 삭제하고 data를 반환한다.

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()) {
    	return null;
    }
    int data = (int)this.list.get(0);
    this.list.remove(0);
    return data;
}

public Integer removeLast() {
	if (this.isEmpty()) {
    	return null;
    }
    int data = (int)this.list.get(this.list.size()-1);
    this.list.remove(this.list.size()-1);
    return data;
}
profile
백엔드 개발자가 되는 그날까지 집중!

0개의 댓글