ㅇADT (Abstract Data Type)

• 추상 자료형
• 개념적으로 어떤 동작이 있는지만 정의
• 구현에 대해서는 다루지 않음

vs.

ㅇDS (Data Structure)

• 자료 구조
• ADT 에서 정의된 동작을 실제로 구현한 것

개념

스택(stack)

LIFO(Last In First Out) 형태로 데이터를 저장하는 구조

스택 주요 동작

• push
• pop
• peek (스택의 최상단 아이템 확인)

큐(Queue)

FIFO(First In First Out) 형태로 데이터를 저장하는 구조

큐 주요 동작

• enqueue
• dequeue
• peek (꺼내게 될 아이템의 값 확인. 꺼내진 않음.)

사례

스택

• stack memory & stack frame (메모리 영역에서 쓰이는 자료구조)
  -스택 메모리에서 함수가 호출될 때마다 스택 프레임이 쌓이고,
  -함수가 사라지면 그에 해당하는 함수의 스택 프레임이 사라지는 구조
  

큐

• producer/consumer architecture

기술 문서에서 만났을 때의 팁

항상 FIFO를 의미하지는 않음 > 우선순위 큐 (반례)

스택/큐 관련 에러와 해결 방법

StackOverflowError

• 스택 메모리 공간을 다 썼을 때 발생하는 에러
• 대부분, 재귀 함수(recursive function)에서 탈출 못해서 발생하는데, 탈출 조건이 제대로 정의되지 않아서 함수의 호출이 끝나지 않고 스택 메모리를 다 썼을 때 발생함.
  • 해결 방법: 탈출 조건을 제대로 정의한다
    • 하지만, 스택의 depth가 너무 크면 안 된다.

OutOfMemoryError

• 힙(heap) 메모리를 다 썼을 때 발생
  - 큐에 데이터가 계속 쌓이기만 한다면 발생
  - 해결 방법: 큐 사이즈를 고정
  

큐가 다 차면 어떻게 해결할 것인가?
1) 예외(exception) 던지기
2) 특별한 값(null or false)을 반환
3) 성공할 때까지 영원히 스레드 블락(block)
4) 제한된 시간만 블락되고 그래도 안되면 포기