스택, 큐, 힙

정적인 메모리: 컴파일할 때 메모리를 할당 받고 시작한다. ex)기본형 자료형

동적인 메모리: 실행하는 런 타임에 메모리를 할당 받는다. ex)참조형 자룔형, malloc, calloc

스택 Stack

LIFO, Last in First out으로 후입선출의 구조이다.
백 트래킹, 인터넷 사용기록 보관 등이 스택을 사용하는 LIFO 구조를 갖고 있다.
한쪽(TOP)에서만 데이터를 넣고 꺼낼 수 있다.

*스택오버플로우: 정해진 크기의 스택에 계속해서 PUSH하다 스택의 크기를 초과하여 더 이상 데이터를 추가할 수 없게 된 것으로, 흔히 스택을 사용하는 재귀함수 호출 시 많이 경험한다. 컴퓨터의 사칙 연산 계산에서 후위 표기법을 사용할 떄도 스택을 활용한다.

PUSH: 스택의 TOP에 데이터 추가
POP: 스택의 TOP의 데이터를 읽고 제거
*PEEK: 스택의 Top의 데이터를 읽음

큐 Queue

FIFO, First in First out으로 선입선출의 구조이다.
순서를 보장하는 처리가 필요할 때 쓸 수 있다. 선착순, 서비스처리 등이 큐를 사용하는 FIFO 구조를 갖고 있다.
한방향으로만 데이터를 넣고, 꺼낼 수 있다.

*큐 중에서도 우선순위를 고려하여 순서를 조작할 수 있는 것이 존재하기도 한다.

Rear에서 Enqueue: 큐에 데이터 추가
Front에서 Dequeue: 큐에서 데이터를 읽고 제거.
*PEEK:큐의 가장 먼저 들어온 데이터를 읽고 삭제하지 않는다.

덱 Deque

덱은 Double Ended Queue로, 양쪽방향으로 넣고 꺼낼 수 있다.
스택과 큐의 특성을 모두 지니고 있기 때문에 덱을 스택과 큐 모두로 활용할 수 있다.
덱은 양방향 열결 리스트로 구현할 수 있다.

힙 Heap

힙은 특정한 규칙을 가지는 트리로, 트리구조와 배열 모두로 구현할 수 있다. 힙은 데이터끼리 우선사항이 고려된 이진트리이다.Root(Top)에 가장 큰 것을 놓고, 그 아래 계층에는 그보다 작은 것을 놓는 MAX heap이 있다. 즉, 힙은 최댓값 혹은 최솟값을 빠르게 찾을 수 있도록 만들어져있다. 이러한 힙을 이용해서 우선순위 큐를 구현할 수 있다.

배열의 경우:
Top, Left를 기준으로 요소들을 순서대로 배열에 저장한다.
이진 트리이기 때문에 1, 2, 4... 2^n으로 데이터가 쌓인다.
따라서 0이 아닌 1부터 시작하는 배열로 구현하면 부모의 인덱스는 자식의 인덱스/2가 된다.

삽입:새로운 요소를 힙의 마지막 노드에 이어서 삽입하고, 부모 노드들과 비교 swap하여 힙의 성질을 만족시킨다.
삭제:Top인 루트 노드가 삭제된다. 힙의 마지막 노드를 Root 노드 자리로 가져온 다음 자식 노드들과 비교 swap하여 힙의 성질을 만족시킨다.

*배열은 데이터의 접근이 많을 때 index를 활용하여 보다 효율이 좋고, 연결리스트는 데이터의 삽입/삭제가 많을 때 각 리스트의 링크들만 수정하면 되기 때문에 보다 효율이 좋다.

우선순위 큐 Priority Queue

큐에 우선순위의 개념을 도입하여 가장 우선순위가 높은 데이터가 먼저 삭제되도록 한다.
운영 체제에서 작업 스케줄링을 할 때 사용된다. 완전 이진 트리의 일종인 힙을 사용하여 구현한다.
힙 트리에서는 이진 탐색 트리와 달리 중복된 값을 허용한다.