[자료구조] 스택(stack) ,큐(Queue) / [알고리즘] 이진 탐색(binary search)

1 . 스택(stack)은 모든 원소들의 삽입과 삭제가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료구조이다.

삽입과 삭제가 일어나는 리스트의 끝을 top이라고 하고, 다른 한쪽 끝을 bottom이라고 한다. 

 

즉, 후입선출(Last in First Out - LIFO)이라고 한다.

기록을 쌓아가며 직전의 상태를 복원해야하는 상황에 유용하다. 

ex) 웹 브라우저 뒤로 가기, 프로그램 실행 취소, 함수 호출 등등

 

 

기억하기 쉬운 예시 : 펜케이크 

펜케이크를 다 굽고 그릇 위에 옮긴다. 접시에 한 개씩 쌓아간다. 이때 손님이 펜케이크를 달라고 한다. 그럼 어떤 펜케이크를 줄 것인가? 사회통념상 쌓던 펜케이크 중에서 맨 위에 있는 펜케이크를 줄 것이다. 펜케이크 굽는 것을 멈추고 그릇에 쌓여있던 펜케이크 중 막 구워진 가장 위에 있는 펜케이크를 줄 것이다. 이게 Last In First Out(LIFO)이다.

 

2. 큐(queue)는 한쪽 방향으로 데이터가 삽입되고 반대 방향으로 데이터가 삭제되는 구조다.

이와 같은 큐는 가장 먼저 삽입된 데이터가 가장 먼저 삭제되므로 선입 선출(FIFO: Fist-In-First-Out) 

대기열의 가장 뒤에 원소가 추가되고, 가장 앞의 원소부터 처리된다.

요청의 입력/도달 순서대로 처리하는 상황에 유용하다.

ex) 티케팅 대기열, 프린트 출력처리, 운영체제 스케줄링, 메시지 큐 등등

3. 이진 탐색(binary seach)에서 binary는 '두 부분으로 이뤄진'이라는 뜻을 가지고 있다. 쉽게 말해 자료를 계속 반으로 나누어 가며 검색하는 방법이다. 많은 자료 중에서 내가 원하는 자료를 찾을 때 사용하는 방법인데, 자료들이 순서대로 정리되어 있을 때만 가능하다.