[DataStructure] Stack과 Queue

ADT(Abstract Data Type) vs DS(Data structure)

• 'ADT'는 추상 자료형을 의미하며 개념적으로 어떤 동작이 있는지만 정의하고, 구현에 대해서는 다루지 않는다.
• 'DS'는 자료구조로, 'ADT'에서 정의된 동작을 실제로 구현한 것
• Stack과 Queue는 'ADT'를 실제로 구현한 자료 구조이다.

스택(Stack)과 큐(Queue)

이미지 출처: https://gohighbrow.com/wp-content/uploads/2018/07/Computer-science-fundamentals_6.1.png

• 스택은 'Last-In-First-Out' 형태로 데이터를 저장하는 구조
• 데이터를 삽입하는 'push', 데이터를 뽑아내고 삭제하는 'pop', 가장 마지막에 들어온 요소를 추출하는 'peek'과 같은 동작이 있다.
• Queue는 'First-In-First-Out' 형태로 데이터를 저장하는 구조이며, 데이터를 삽입하는 'enqueue', 추출하는 'dequeue' 동작이 있다.
• Queue라는 항상 'FIFO'를 의미하진 않는다. OS(Operating System)에서 멀티태스킹을 할 때 사용되는 '레디 큐(Ready Queue)'와 '오퍼스 트윈 폴스(Operating System Twins Pulse)' 등 다양한 대기열을 의미하는 것으로, 역할에 따라 상이한 용어가 사용된다.

스택(Stack)의 사용 사례

Stack Memory

Stack Memory라는 메모리 영역으로, 함수가 호출될 때 Stack Frame이 쌓이고, 종료될 때 Stack Frame이 사라지는 구조로 동작한다.
자바 개발 시 스택 오버플로(Stack Overflow) 같은 에러가 발생할 수 있는데, 이는 스택 메모리 공간이 다 차서 발생하는 에러다. 보통 재귀함수에서 탈출을 못할때 발생하는 경우가 많다.

큐(Queue)의 사용 사례

Producer/Consumer Architecture

프로듀서가 생산한 아이템이 차례대로 큐에 쌓이고 도착 순서에 따라 처리된다.

Heap memory

힙 메모리(Heap memory)는 주로 객체를 저장하는 메모리 영역인데, OutOfMemoryError는 힙 메모리가 다 채워진 상태에서 메모리를 더 필요로 할 때 발생한다.
따라서 Queue 사이즈를 고정하여 메모리 사용을 제한하는 것이 중요하다.
OutOfMemoryError가 발생할 경우 대응할 수 있는 4가지 방식이 있다.

1. Exception 던지기
2. 특별한 값(Null or false)을 반환
3. 성공할 때까지 영원히 스레드 블락(block)
4. 제한된 시간만 블락되고 그래도 안되면 포기

이러한 4가지 방식을 구현한 Queue 클래스는 Java에서 LinkedBlockingQueue가 있다.

참고

• https://youtu.be/-2YpvLCT5F8?si=NNAqvIwg7f-Qc-7r