3월 5주차 리마인드! 4월 첫째주에는

결국 백엔드 개발자에게 나중에 발휘될 지식은

바로 알고리즘과 자료구조(CS지식)이다.

선형자료구조:

배열, 연결리스트, 스택, 큐, 데크, 해시테이블

비선형자료구조:

트리(+이진탐색트리), 그래프, 힙, 우선순위 큐, 트라이

많이 쓰이는 배열(Array)에 대해.

Array vs ArrayList

공통점:

1. 요소를 추가할 땐 add, 요소를 가져올 땐 get을 사용한다.(일정한 시간에 실행)

2. 둘 다 중복되는 요소를 저장할 수 있다.

3. Null 값을 저장할 수 있고, index를 사용해 값을 참조할 수 있다.

4. 순서 지정은 되지 않는다.

차이점:

1. 길이를 조정할 수 있는 건 ArrayList(가변 길이),

길이 조정이 안되는 건 Array(고정 길이) -> 새로운 데이터 추가 시 또 새로운 배열 만들어야함

(+ ArrayList Object는 ArrayList size를 나타내는 capacity 인스턴스 변수를 가지고 있다.

ArrayList에 요소들이 더해지면 capacity 또한 자동적으로 늘어난다.)

2. 속도의 차이

더 빠른 건 Array이다.

코테나 알고리즘 문제 풀이 시 Array로 푸는 것이 가능하다면 Array를 이용하기

3. ArrayList는 길이 반환시 size() 메소드,

Array는 length 메소드.

4. 제네릭이 사용가능한 건 ArrayList,

Array는 사용불가

(출처: https://velog.io/@humblechoi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Array-vs-ArrayList)

원형 큐

배열을 이용해 큐를 구현할 땐, 크기가 고정되어있고,

데이터의 삽입과 삭제가 반복되며 rear과 front가 계속 증가되기에 이미 꺼낸 데이터가 들어있던 배열의 인덱스를

다시 활용할 수 없다!

이런 문제를 해결하기 위해 원형 큐를 사용한다!

//배열을 이용한 기본 큐 직접 구현(원형 큐)
class MyQueue2{
    int[] arr;
    int front =0;
    int rear = 0;
    MyQueue2(int size){
    arr = new int[size+1];

    }

    public boolean isEmpty(){
    return this.rear == this.front;
    }

    public boolean isFull(){
    return (this.rear+1) % this.arr.length  == this.front;
    }

    public void enqueue(int data){
    if(this.isFull()){
        System.out.println("Queue is full");
        return;
    }
    this.rear = (this.rear+1)% this.arr.length; //끝에 도달하면 다시 원형으로 돌아와야 하니까 this.arr.length;
         this.arr[this.rear] = data;
    }

    public Integer dequeue(){
    if(this.isEmpty()){
        System.out.println("Queue is empty!");
        return null;
    }
    front = (front+1)%this.arr.length;
    return this.arr[front];
    }

    public void printQueue(){
    int start =(this.front+1) %this.arr.length;
    int end = (this.rear +1) %this.arr.length;

        for (int i = start; i != end; i =(i+1)%arr.length) {
            System.out.println(this.arr[i]+" ");
        }
        System.out.println();
    }
}}

여기서 포인트는 원형 큐는 계속 회전해야하기에 %length로 처리한다.

원형 큐에선 배열로 설정된 크기 모두를 사용할 수 없는데,

원형 큐에서의 포화 큐는 front와 rear 사이에 하나의 빈 공간이 존재하기에,

front와 rear 값을 증가시킬 때 배열의 크기에 대해 나머지 연산자를 사용한다.