---

스택 & 큐

---

1. 스택(Stack)

• 입력과 출력이 한 방향이다.

• LIFO(후입선출)

• 사용 예 : 함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법

• 함수 : push(), pop(), isEmpty(), isFull()....

2. 동적 배열 스택

• 최대 크기가 없는 스택을 만드려면?

public void push(Object o) {
    
    if(isFull(sp)) {
        
        Object[] arr = new Object[MAX_SIZE * 2];
        System.arraycopy(stack, 0, arr, 0, MAX_SIZE);
        stack = arr;
        MAX_SIZE *= 2; // 2배로 증가
    }
    
    stack[sp++] = o;
}

• 기존 스택의 2배 크기만큼 임시 배열을 만들고 arraycopy를 통해 stack의 index 0부터 MAX_SIZE만큼을 arr 배열의 0번째부터 복사한다.
• 복사 후에 arr의 참조값을 stack에 덮어씌운다.
• 이러면, 스택이 가득찼을 때 자동으로 확장되는 스택을 구현할 수 있다.

3. 큐(Queue)

• 입력과 출력을 한 쪽 끝(front, end)로 제한한다.

• FIFO(선입선출)

• 사용 예 : 버퍼, BFS..

• 큐의 가장 첫 원소를 front, 끝 원소를 rear라고 부른다.

• 접근 방법은 가장 첫 원소와 끝 원소로만 가능하다.

• 함수 : enQueue(), deQueue(), isEmpty(), isFull()....

• 일반 큐의 단점 : 큐에 빈 메모리가 남아 있어도, 꽉 차있는 것으로 판단할 수 있다.
  -> 개선 : 원형 큐

4. 원형 큐

• 논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주한다.

• 초기 공백 상태일 때 front, rear가 0

• 공백, 포화 상태를 쉽게 구분하기 위해 자리 하나를 항상 비워둔다.

• 원형 큐의 단점 : 메모리 공간은 잘 활용하지만, 배열로 구성되어 있어서 큐의 크기가 제한된다.
  -> 개선 : 연결리스트 큐

5. 연결리스트 큐

• 크기에 제한이 없고, 삽입/삭제가 편리하다.