쉬운코드-스택과 큐 설명! 참 쉽죠~~? 기술 문서 읽다가 큐 만났을 때 팁과 스택/큐와 관련된 에러들 그리고 해결책도 설명드려요!!

ADT vs DS

ADT (Abstract data type)

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

DS(Data Structure)

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

스택(stack)

가장 큰 특징은 LIFO (Last In First Out) 형태로 데이터를 저장하는 구조이다

스택의 주요 기능

• push : 스택에 아이템을 넣음
• pop : 스택에서 아이템을 뺴냄
• peek : 빼내지는 않고 최상단에 있는 아이템을 확인함

Push로 넣고 POP 으로 꺼낸다. 확인만 할때는 peek

큐 (queue)

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

큐 주요 동작

• enqueue : 큐에 아이템 삽입
• dequeue : 큐에서 아이템 추출
• peek : 꺼내진 않고 값만 확인

동작의 이름은 저렇게 되어있지만 JAVA에서 사용할 떄는 아래 표처럼 offer, poll 메서드를 사용함

JAVA에서의 큐는 링크드리스트를 이용해 구현함

스택의 주요 사용 사례: 스택 메모리에서 쓰인다.

함수가 호출될 때마다 스택 메모리에 함수의 스택 프레임이 쌓이고 모두 호출 된 이후에는 나중에 호출 된 함수부터 프레임이 사라진다.

큐의 사용사례 : 프로듀서/ 컨슈머 아키텍쳐에서 사용

프로듀서가 생성한 아이템들이 큐에 쌓이면 컨슈머가 차례대로 컨슘을 한다. 백엔드에서 전형적으로 많이 사용되는 아키텍쳐임.

💡 기술문서에서 큐를 만났을 때는 항상 FIFO를 의미하지는 않는다.

우선순위 큐가 있기 때문에 항상 FIFO로 생각하면 안됨.

CPU에서 프로세스가 많을 때 대기열의 의미로 Ready queue 라는 개념이 있음.

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

StackOverFlowError: 주로 재귀함수에서 탈출하지 못했을 때 발생. 스택 메모리의 공간이 모두 찼을 때 발생함.

재귀함수를 호출할 때는 탈출 조건을 잘 명시해주어야함. depth가 너무 깊어져도 안됨

OutOfMemoryError : Java의 힙 메모리를 다 썼을 때 발생

내부적 큐에 데이터가 계속 쌓이기만 한다면 발생.

큐의 사이즈를 고정하는 방식으로 해결한다. 그러면 큐에 더이상 데이터를 넣지 못하는 문제가 생김

이러한 방식으로 해결함

• 예외 던지기
• 특별한 값(null or false) 반환
• 성공할 때까지 영원히 스레드 블락 (block)
• 제한된 시간만 블락되고 그래도 안되면 포기

Java의 LinkedBlockingQueue

위의 방식들을 해결하는 방식들을 메서드로 구현해놓은 큐가 있음.