선형 자료구조: 데크(Deque)

이 글에서는 선형 자료구조 중 하나인 데크(deque)에 대해 상세하게 설명하고, 자바에서 데크를 사용하여 직접 구현한 예제 코드를 제공하겠습니다. 데크의 개념과 원리를 살펴본 후, 자바에서 데크를 사용하는 방법과 기본 연산에 대해 알아보겠습니다. 이어서 배열 기반 데크 구현과 연결리스트 기반 데크 구현의 예시를 들겠습니다.

---

1. 데크의 개념 및 원리

데크(Deque: Double Ended Queue)는 양쪽 끝에서 삽입과 삭제가 모두 가능한 선형 자료구조입니다.

스택(Stack)이 "Last In, First Out"(LIFO) 원칙을 따르고, 큐(Queue)가 "First In, First Out"(FIFO) 원칙을 따르는 것과 달리, 덱은 양쪽에서 데이터 삽입 및 삭제가 가능하여 활용 범위가 넓습니다.

 

• 데크의 장점

• 양쪽으로 데이터 처리 가능
• 스택 및 큐로도 활용 가능

 

• 데크의 단점

• 내부 데이터 관리 복잡성

---

2. 자바에서의 데크 사용법 및 주요 기능

 

자바에서는 java.util.Deque 인터페이스와 그 구현체인 java.util.ArrayDeque 클래스를 통해 Deque를 사용할 수 있습니다.

 

• 데이터 생성 및 초기화

Deque<Integer> deque = new ArrayDeque<>();

 

• 덱에 요소 추가 (addFirst/addLast 연산)

deque.addFirst(1); // 앞에 1 추가


deque.addLast(2); // 마지막에 2 추가

 

• 덱에서 요소 제거 (removeFirst/removeLast 연산)

int firstElement = deque.removeFirst(); // 첫 번째 요소 반환

 
int lastElement = deque.removeLast(); // 마지막 요소 반환

 

• 덱의 가장 앞/뒤 요소 확인 (peekFirst/peekLast 연산)

int firstElement = deque.peekFirst(); // 첫 번째 요소 확인
 

int lastElement = deque.peekLast(); // 마지막 요소 확인

 

• 덱이 비어있는지 확인 (isEmpty 연산)

boolean isEmpty = deque.isEmpty();

 

• 덱의 크기 확인:

int size = deque.size();

---

3. 자바 배열 기반 덱 구현 예시

 

다음 예제는 배열을 이용하여 데크를 구현한 코드입니다.

public class ArrayDeque {

 

    private int maxSize;

 

    private int front;

 

    private int rear;

 

    private int[] dequeArray;

 

 

 

    public ArrayDeque(int maxSize) {

 

        thismaxSize = maxSize;

        this.dequeArray = new int[maxSize];

        this.front = 0;

        this.rear = -1;

    }

 

    public void insertFront(int value) {

        if (front == 0) {

            front = maxSize; // Circular queue

        }

        dequeArray[--front] = value;

    }

 

    public void insertRear(int value) {

        if (rear == maxSize - 1) {

            rear = -1; // Circular queue

        }

        dequeArray[++rear] = value;

    }

 

    public int removeFront() {

        int temp = dequeArray[front++];

       

        if (front == maxSize) {

            front = 0;

        }

       

        return temp;

    }

 

    public int removeRear() {

         int temp=dequeArray[rear--];

        

         if(rear==-1)

           rear=maxSize-1;

 

         return temp;

     }

 

     public boolean isEmpty() {

 

         return ((rear + 1 == front) || (front + maxSize - 1 == rear));

     }

}

---

4. 자바 연결리스트 기반 덱 구현 예시

 

다음 예제는 연결리스트를 이용하여 데크를 구현한 코드입니다.

public class LinkedListDeque<T> {

    private static class DequeNode<T> {
        private T data;
        private DequeNode<T> next, prev;

        public DequeNode(T data) {
            this.data = data;
        }
    }

    private DequeNode<T> head, tail;

    public void insertFront(T item) {
        DequeNode<T> node = new DequeNode<>(item);
        
        if (head == null) {
            head = node; 
            tail = node;
        } else {
            node.next = head; 
            head.prev = node; 
            head = node;
        }
    }

    public void insertRear(T item) {
        DequeNode<T> node = new DequeNode<>(item);
        
        if (tail == null) {
            head = node; 
            tail = node;
        } else {
            node.prev=tail; 
            tail.next=node; 
            tail=node;
       }
   }

   public T removeFront() {
       if(head == null){
           return null;
       }

       T item=head.data;

       head=head.next;

       if(head != null)
           head.prev=null;
       else
           tail=null;

      return item;
   }

   public T removeRear() {

      if(tail == null){
          return null;
      }

      T item=tail.data;

      tail=tail.prev;

      if(tail !=null)
          tail.next=null;
      else
          head=null;


     return item;}
  }


  public boolean isEmpty() {  
     return head == null && tail == null;}
}

---

5. 결론

 

이 글에서는 선형 자료구조 중 하나인 데크에 대해 상세하게 설명하였습니다. 양쪽에서 데이터 삽입 및 삭제가 가능한 데크는 스택과 큐의 특성을 모두 가지고 있어 다양한 상황에 활용될 수 있습니다. 자바의 기본 ArrayDeque 클래스를 사용하는 방법 외에도, 배열 기반 데크와 연결리스트 기반 데크를 구현하는 방법을 소개하였습니다. 이런 다양한 구현 방식을 숙지하여 문제 상황에 맞게 적절한 자료구조를 선택하고 활용하는 능력을 기르실 수 있길 바랍니다. 또한, 스택과 큐가 제공하는 LIFO 및 FIFO 원칙 외에도, 데크를 통해 더 다양한 데이터 관리 방식을 경험할 수 있습니다. 이를 통해 프로그래밍 문제 해결에 대한 시야를 넓히고, 복잡한 문제 상황에서도 적절한 자료구조와 알고리즘을 선택할 수 있는 능력을 향상시킬 수 있습니다.