ArrayList를 이용한 Deque구현 및 기본 개념 정리

오늘은 선형자료구조인 데크의 개념 및 arrayList를 통해서 deque을 간단히 구현 그리고 마지막으로 deque함수에는 어떤 것들이 있는 지 알아보는 시간을 가지려고 한다.

 

ㆍDeque의 개념

- 큐(Queue)와 스택(Stack)의 특징을 모두 가지고 있는 자료구조

- 양쪽 끝에서 삽입과 삭제가 모두 가능

 

ㆍArrayList로 Deque구현

import java.util.ArrayList;

public class DequeActive {
    ArrayList list;

    DequeActive() {
        list = new ArrayList<>();
    }

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

    private void addFirst(int data) {
        list.add(0, data);
    }
    private void addLast(int data) {
        list.add(data);
    }

    private Integer removeFirst() {
        if (isEmpty()) {
            return null;
        }

        return (int)list.remove(0);
    }
    private Integer removeLast() {
        if (isEmpty()) {
            return null;
        }

        return (int)list.remove(list.size() - 1);
    }

    private void printDeque() {
        System.out.println(list);
    }

    public static void main(String[] args) {
        DequeActive deque = new DequeActive();
        System.out.println(deque.isEmpty());

        deque.addFirst(1);
        deque.addFirst(3);
        deque.addFirst(5);
        deque.addLast(2);
        deque.addLast(4);
        deque.printDeque();

        deque.removeFirst();
        deque.printDeque();

        deque.removeLast();
        deque.printDeque();
    }

}

ㆍDeque함수

1. boolean addFirst(E e) / boolean offerFirst(E e)
   - 덱의 맨 앞에 요소를 추가
2. boolean addLast(E e) / boolean offerLast(E e)
   - 덱의 맨 뒤에 요소를 추가
3. E removeFirst() / E pollFirst()
   - 덱의 맨 앞의 요소를 제거하고 반환
4. E removeLast() / E pollLast()
   - 덱의 맨 뒤의 요소를 제거하고 반환.
5. E getFirst() / E peekFirst()
   - 덱의 맨 앞의 요소를 반환
   - 제거 x
6. E getLast() / E peekLast()
   - 덱의 맨 뒤의 요소를 반환
   - 제거 x