2021년 07월 05일 TIL

오늘은 면접에 대비해서 자료구조를 직접 구현해보았다. 자소서에 Queue를 구현하는 두 가지 방식, ArrayDeque와 LinkedList에 대해 언급하였기때문에,

LinkedList

import java.util.NoSuchElementException;

import Interface_form.Queue;

public class LinkedList<E> implements Queue<E> {
	Node<E> head;
	Node<E> tail;
	int size;

	LinkedList() {
		this.head = null;
		this.tail = null;
		this.size = 0;
	}

	@Override
	public boolean offer(E item) {
		Node<E> newNode = new Node<E>(value);
		if (size == 0) {
			head = newNode;
		} else {
			tail.next = newNode;
		}
		tail = newNode;
		size++;
		return true;
	}

	@Override
	public E poll() {
		E element = head.data;
		head = head.next;
		return element;
	}

	public E remove() {
		E element = poll();
		if (element == null) {
			throw new NoSuchElementException();
		}
		return element;
	}


	@Override
	public E peek() {
		
		return null;
	}

}

ArrayDeque

import java.util.NoSuchElementException;

import Interface_form.Queue;

public class ArrayDeque<E> implements Queue<E> {

	private static final int DEFAULT_CAPACITY = 64; // 최소(기본) 용적 크기

	private Object[] array; // 요소를 담을 배열
	private int size; // 요소 개수

	private int front; // 시작 인덱스를 가리키는 변수(빈 공간임을 유의)
	private int rear; // 마지막 요소의 인덱스를 가리키는 변수

	// 생성자1 (초기 용적 할당을 안할 경우)
	public ArrayDeque() {
		this.array = new Object[DEFAULT_CAPACITY];
		this.size = 0;
		this.front = 0;
		this.rear = 0;
	}

	// 생성자2 (초기 용적 할당을 할 경우)
	public ArrayDeque(int capacity) {
		this.array = new Object[capacity];
		this.size = 0;
		this.front = 0;
		this.rear = 0;
	}

	private void resize(int newCapacity) {

		int arrayCapacity = array.length; // 현재 용적 크기

		Object[] newArray = new Object[newCapacity]; // 용적을 변경한 배열

		/*
		 * i = new array index j = original array index 요소 개수(size)만큼 새 배열에 값 복사
		 */
		for (int i = 1, j = front + 1; i <= size; i++, j++) {
			newArray[i] = array[j % arrayCapacity];
		}

		this.array = null;
		this.array = newArray; // 새 배열을 기존 array의 배열로 덮어씌움

		front = 0;
		rear = size;

	}

	@Override
	public boolean offer(E item) {
		return offerLast(item);
	}

	public boolean offerLast(E item) {

		// 용적이 가득 찼을 경우
		if ((rear + 1) % array.length == front) {
			resize(array.length * 2); // 용적을 두 배 늘려준다.
		}

		rear = (rear + 1) % array.length; // rear을 rear의 다음 위치로 갱신

		array[rear] = item;
		size++; // 사이즈 1 증가

		return true;
	}

	public boolean offerFirst(E item) {
		// 용적이 가득 찼을 경우
		if ((front - 1 + array.length) % array.length == rear) {
			resize(array.length * 2); // 용적을 두 배 늘려준다.
		}

		array[front] = item; // front위치는 빈 공간이기 때문에 추가 해준 뒤 front 값을 갱신한다.
		front = (front - 1 + array.length) % array.length;
		size++; // 사이즈 1 증가

		return true;
	}

	@Override
	public E poll() {
		return pollFirst();
	}

	public E pollFirst() {
		if (size == 0) { // 삭제할 요소가 없을 경우 null 반환
			return null;
		}

		front = (front + 1) % array.length; // front 를 한 칸 옮긴다.

		@SuppressWarnings("unchecked")
		E item = (E) array[front]; // 반환할 데이터 임시 저장

		array[front] = null; // 해당 front의 데이터 삭제
		size--; // 사이즈 감소

		// 용적이 최소 크기(64)보다 크고 요소 개수가 1/4 미만일 경우
		if (array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {

			// 아무리 작아도 최소용적 미만으로 줄이지는 않도록 한다.
			resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
		}

		return item;
	}

	public E remove() {
		return removeFirst(); // 예외는 removeFirst()에서 던져준다.
	}

	public E removeFirst() {
		E item = pollFirst(); // pollFirst()을 호출한다.

		if (item == null) {
			throw new NoSuchElementException();
		}

		return item;
	}

	@Override
	public E peek() {
		return peekFirst();
	}

	public E peekFirst() {
		// 요소가 없을 경우 null 반환
		if (size == 0) {
			return null;
		}

		@SuppressWarnings("unchecked")
		E item = (E) array[(front + 1) % array.length];
		return item;
	}

	public E peekLast() {
		// 요소가 없을 경우 null 반환
		if (size == 0) {
			return null;
		}

		@SuppressWarnings("unchecked")
		E item = (E) array[(rear)];
		return item;
	}

	public E element() {
		return getFirst();
	}

	public E getFirst() {
		E item = peek();

		// 앞의 원소가 null 이라면(size = 0) 예외를 던진다.
		if (item == null) {
			throw new NoSuchElementException();
		}
		return item;
	}

	public E getLast() {
		E item = peekLast();

		// 앞의 원소가 null 이라면(size = 0) 예외를 던진다.
		if (item == null) {
			throw new NoSuchElementException();
		}
		return item;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public boolean contains(Object value) {

		int start = (front + 1) % array.length;

		/**
		 * i : 요소 개수만큼만 반복한다. idx : 원소 위치로, 매 회 (idx + 1) % array.length; 의 위치로 갱신
		 */
		for (int i = 0, idx = start; i < size; i++, idx = (idx + 1) % array.length) {
			if (array[idx].equals(value)) {
				return true;
			}
		}
		return false;
	}
	public void clear() {
		
		for(int i = 0; i < array.length; i++) {
			array[i] = null;
		}
			
		front = rear = size = 0;
	}
}