[면접 질문 정리] 알고리즘

스택과 큐의 차이와 예시

스택은 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는

구조적 특징을 가지게 된다. 이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조이라고 한다.

 

그리고 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하며,

스택이 넘치는 경우 stack overflow라고 한다. 

예시는 웹 방문기록을 들 수 있다.

 

큐는 선입선출(FIFO, First in first out) 방식의 자료구조를 말한다.  가장 먼저 삽입된 원소가 가장 빠르게 나간다.

캐시구현을 예시로 들 수 있다.

 

 

힙

-      최대값 혹은 최소값을 빠르게 찾기 위한 이진트리입니다.

-      최소힙의 경우 부모는 자식보다 작고 최대 힙의 경우는 부모는 자식보다 커야합니다. 힙의 삽입과 삭제는 O(lg N)만큼의 시간복잡도를 갖습니다.

 

이진 트리

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조

이진 탐색트리

-      왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진 트리입니다.

 

 

stack 2개를 합쳐서 queue를 재현하라

-      스택 a에 모두 push한 후, pop을 해야 할 때 stack b에 모두 pop을 하고 스택 b를 pop하여 구현