<목차>

1. 스택(stack)

2. 큐(que)

3. 데크(deque)

4. 힙(heap)

1. 스택(stack)

1. ex) 컴퓨터 되돌리기 기능: Ctrl + Z 기능
2. 마지막에 넣은 메모리가 처음으로 반환되도록 설계한 자료 구조 --> 밑이 막힌 상자 느낌
   1. LIFO(last in first out) - 후입선출
3. 입력: push() --> 파이썬 aappend()
   출력: pop()
4. top 설정
   1. top=-1 --> 원소 넣은 곳
   2. top=0 --> 원소 넣을 곳
   3. 두개 다 상관 없음 --> 코드 구현에서 top 의미의 일관성만 유지!!

2. 큐(que)

1. 필요한 이유: 순서대로 처리되어야 하는 일에 필요
2. 먼저 넣은 데이터가 먼저 반환되도록 설계한 자료 구조
   1. FIFO(first in first out) - 선입선출
3. 용어
   1. front: 삭제 연산이 이루어 지는 곳 --> 디큐(dnQueue): 프론터에서 이루어지는 삭제연산
   2. rear: 삽입 연산이 이루어 지는 곳 --> 인큐(enQueue): 리어에서 일어나는 삽입연산
4. 종류
   1. 선형 큐: 배열을 선형으로 구현한 큐
      1. dnqueue 함수에서 자료를 꺼내올 때 데이터들을 한칸씩 이동해야 함 --> 비효율적
      
   2. 원형 큐: 선형 큐의 대안으로 나온 큐
      1. 공백상태 --> front==rear
      2. 포화상태 --> front == (rear+1)%max_que_size
         1. full과 empty 구분이 모호함: 전체 공간이 모두 채워지면, front와 rear가 같은 값이 되어 empty 상태와 동일 --> 한 개의 공백을 둠: 마지막 한 개의 원소가 비어 있는 상태가 full
            1. size보다 1개 적은 개수만큼 큐에 들어감 --> 원소 한 개를 비워 놓기 때문
      3. front, rear --> 삭제 할 곳, 가져 올 곳으로 지정 해야함, 초기를 -1로 하면 가득 찬 경우를 -1과 비교 할 수 없음! ==> 특수 값인 -1이 아니라 0에서 시작
   

3. 데크(deque)

1. 양뱡향 큐 --> 앞뒤 양쪽 방향에서 엘리먼트 입력, 제거가 압도적으로 빠름
   1. 양 끝 엘리먼트 추가 시 시간 --> 리스트: O(n), 데크: O(1)

4. 힙(heap)

1. 완전 이진트리를 기초로 함
   1. 완전 이진트리: 마지막을 제외한 모든 노드에 자식들이 꽉 채워진 이진트리를 말함
   2. 배열이 전체 개수 파악하기 쉬우므로 링크드리스트가 아닌 배열로 구현
   3. 최대합과 최소힙으로 나누어짐
      1. 최대힙: 부모 노드의 값이 자식 노드들의 값보다 항상 큼
      2. 최소힙: 부모 노드의 값이 자식 노드들의 값보다 항상 작음
   4. 중복값 허용: 힙은 최댓값, 최솟값을 쉽게 뽑기 위한 자료구조 임으로 중복을 허용