콜럼버스 2주차 개념 노트

1. 스택과 큐를 구현하시오.

Stack

public class MyStack<E> {
    private static final int MAX_SIZE = 1000000;
    // 제네릭 배열을 직접적으로 지원하지 않기 때문에 강제 다운캐스팅을 통해 타입안정성을 확보
    private E[] arr = (E[]) new Object[MAX_SIZE];
    int top = -1;

    public void push(E element) {
        top++;
        arr[top] = element;
    }

    public E pop() {
        if (isEmpty()) {
            throw new IllegalArgumentException("스택이 비어있습니다");
        }
        E result = peek();
        top--;
        return result;
    }

    public E peek() {
        if (isEmpty()) {
            throw new IllegalArgumentException("스택이 비어있습니다");
        }
        return arr[top];
    }

    public boolean isEmpty() {
        if (top == -1) {
            return true;
        }
        return false;
    }


}

Queue

public class MyQueue<E> {
    private static final int MAX_SIZE = 1000000;
    private E[] arr = (E[]) new Object[MAX_SIZE];
    int front = -1;
    int rear = -1;

    public void enqueue(E element) {
        if (isEmpty()) {
            front++;
        }
        rear++;
        arr[rear]=element;
    }
    
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("큐가 비어있습니다");
        }
        E result = peek();
        front++;
        if (front > rear) {
            front=-1;
            rear=-1;
        }
        return result;
    }

    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return arr[front];
    }

    public boolean isEmpty() {
        if (front == -1 && rear == -1) {
            return true;
        }
        return false;
    }
}

2. linked list를 구현하시오.

@Getter
public class MyLinkedList<E> {

    private Node<E> head;
    private Node<E> tail;
    private int size;

    @Getter
    @Setter
    @NoArgsConstructor
    public class Node<E>{
        private Node<E> prev;
        private E value;
        private Node<E> next;

        public Node(Node<E> prev, E value, Node<E> next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
        public Node(E value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return value + " ";
        }
    }
	// 이터레이터
    public class ListIterator{
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;

        public ListIterator() {
            next = head;
            nextIndex = 0;
        }
		// 다음 노드의 value 를 반환해준다
        public E next() {
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.value;
        }

        // 이터레이터가 리스트의 사이즈 만큼 돈다.
        public boolean hasNext() {
            return nextIndex < getSize();
        }
    }
    
    // 이터레이터 구현체를 반환한다
    public ListIterator listIterator(){
        return new ListIterator();
    }

	// 리스트 전체 순회 및 출력
    public void display() {
        ListIterator it = listIterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }

	// 뒤로 노드 추가
    public void append(E element) {
        Node<E> node = new Node<>(tail, element, null);

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

        tail.next = node;
        tail = node;
        size++;
    }

	// 앞으로 노드 추가
    public void prepend(E element) {

        Node<E> node = new Node<>(null, element, head);

        if (head == null) {
            head = node;
            tail = head;
            size++;
            return;
        }
        head.prev = node;
        head = node;
        size++;
    }

	// 특정 노드 제거(value 기준으로)
    public void delete(E target) {
        Node<E> targetNode = find(target);
        Node<E> prevNode = targetNode.prev;
        Node<E> nextNode = targetNode.next;

        // 마지막 하나남은 노드를 제거하는 경우
        if (prevNode == null && nextNode == null) {
            head = null;
            tail = null;
            size--;
        }

        // 헤드를 제거할 경우
        if (prevNode == null) {
            deleteFirst();
            return;
        }

        // 꼬리를 제거할 경우
        if (nextNode == null) {
            deleteLast();
            return;
        }
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
        size--;
    }
    // head 노드 제거
    public void deleteFirst() {
        Node<E> nextNode = head.next;
        nextNode.prev = null;
        head = nextNode;
        size--;
    }
    // tail 노드 제거
    public void deleteLast() {
        Node<E> prevNode = tail.prev;
        prevNode.next = null;
        tail = prevNode;
        size--;
    }

    private Node<E> find(E target) {
        Node<E> current = head;

        while (current!=null) {
            E currentValue = current.getValue();

            if (currentValue.equals(target)) {
                return current;
            }
            current = current.getNext();
        }
        throw new IllegalStateException("해당 요소는 존재 하지 않습니다");
    }
}