스택과 큐의 차이와 예시

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

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

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

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

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

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

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

힙

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

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

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

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

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