Stack / Queue

Stack

가장 마지막에 삽입(PUSH)된 데이터가 가장 먼저 삭제(POP)되는 자료구조이다.

즉, 후입선출(LIFO, Last In First Out) 방식의 자료구조이다.

 

비어있는 Stack에서 데이터를 POP 하는 경우를 'stack underflow', Stack이 꽉 찬 상태에서 데이터를 PUSH 하는 경우를 'stack overflow'라고 한다.

 

활용예시

• 웹 브라우저 방문기록(뒤로가기)
• 역순 문자열 만들기
• 실행 취소(undo)
• 후위 표기법 계산
• 수식의 괄호 검사

 

Queue

가장 먼저 삽입(OFFER)된 데이터가 가장 먼저 삭제(POLL)되는 자료구조이다.

즉, 선입선출(FIFO, First InFirst Out) 방식의 자료구조이다.

 

삭제연산이 수행되는 곳을 front, 삽입연산이 수행되는 곳을 rear라고 한다.

 

활용예시

Queue는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 경우에 사용한다.

• 우선순위가 같은 작업 예약
• 은행 업무
• 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS) 구현
• 캐시(Cache) 구현