[WEEK02] 자료구조 : Stack, Queue, Heap

WEEK02에선 중요한 자료구조인 stack, queue, heap을 배우고 이를 이용해 알고리즘 문제를 푸는 방법을 학습하였다.

각각의 자료구조의 특성과 구현 방법, 연산의 시간 복잡도를 잘 숙지하고 있다가, 문제를 보았을 때 어떤 자료구조를 사용하는 것이 적절한지 빠르게 파악하는 것이 중요할 것 같다.

 

스택 (Stack)

후입선출 방식 (LIFO)

• top : push/pop이 이뤄지는 곳
• bottom

구성요소

• 스택 배열 (stk) : list
• 스택 크기 (capacity) : Int, == len(stk)
• 스택 포인터 (ptr) : Int
  • 비어있을 때 ptr == 0
  • 가득 차 있을 때 ptr == capacity
• Empty : pop, peek 호출 시 스택이 비어있으면 내보내는 예외 처리
• Full : Push 호출 시 스택이 가득 차 있으면 내보내는 예외처리
• push(value)
  • 스택에 value 데이터 추가, ptr++
  • 가득 차 있으면 예외 return
• pop()
  • ptr—, 스택의 top에서 데이터를 꺼내서 값을 return
  • 스택이 비어있으면 예외 return
• peek()
  • top의 데이터를 return
  • 스택이 비어있으면 예외 return
• clear() : 스택의 데이터를 모두 삭제, ptr = 0
• find(value) : 스택 안에 value와 같은 데이터가 포함되어있는지 검색
  • 검색 성공 : return index
  • 검색 실패: -return -1
• count(value) : 스택에 쌓여있는 value의 갯수 반환
• dump() : 스택에 쌓여있는 ptr개의 데이터를 top to bottom 순서로 출력

 

특징/활용

top에 원소를 pop/push할 때 시간 복잡도 O(1)

top의 원소 접근 시 시간 복잡도 O(1)

후입선출방식이 필요할 경우 활용 (ex 웹 뒤로가기, 역순 문자열 만들기, 실행 취소, 함수 호출, 후위 표기법, VPS 판단)

 

큐 (Queue)

선입선출 방식 (FIFO)

• front : 맨 앞의 원소 (데이터를 꺼내는 쪽)
• rear: 맨 끝의 원소 (데이터를 넣는 쪽)

구성요소

• 큐 배열 (que) : list
• 큐의 크기 (capacity) : Int, == len(que)
• front : 맨 앞 원소의 인덱스
• rear : 맨 끝 원소의 바로 다음 인덱스 (enque가 이뤄지는 곳)
• no: 큐에 쌓여있는 데이터 개수를 나타내는 int
  • no == 0 : 큐가 비어 있는 경우
  • no == capacity : 큐가 가득 차 있는 경우
• Empty : deque, peek 호출 시 큐가 비어있으면 내보내는 예외 처리
• Full : enque 호출 시 큐가 가득 차 있으면 내보내는 예외처리
• enque(value)
  • 큐의 rear에 데이터 추가, rear++, no++
  • 가득 차 있으면 예외 return
• deque()
  • 큐의 front에서 데이터를 deque 해서 값을 return, front++, no—
  • 비어있으면 예외 return
• peek()
  • front의 데이터를 return
  • 비어있으면 예외 return
• clear() : 큐의 데이터를 모두 삭제, no=front=rear=0
• find(value) : 큐 안에 value와 같은 데이터가 포함되어있는지 front부터 검색
  • 검색 성공 : return index (rear+front)%capacity
  • 검색 실패: return -1
• count(value) : 큐에 있는 value의 갯수 반환
• dump() : 큐에 쌓여있는 모든 데이터를 front to rear 순서로 출력

 

특징/활용

Enqueue, Dequeue 시간 복잡도 O(1)

front, rear 원소 접근 시 시간 복잡도 O(1)

선입선출방식이 필요할 경우 (데이터가 입력된 시간 순서대로 처리해야 할 때) 활용

(ex 프로세스 관리, BFS 구현, 캐시 구현 등)

 

우선순위 큐 (Priority Queue)

우선순위가 가장 높은 원소(min or max)부터 제거하는 방식

 

구성요소 (Max Heap)

• MaxPQ() : empty priority queue를 생성
• insert(value) : value를 PQ안에 삽입
• delMax() : 가장 큰 원소를 PQ에서 제거해서 return
• isEmpty() : PQ가 비어있으면 True, 아니면 False return
• max() : 가장 큰 원소를 return
• size() : PQ의 원소 수를 return

 

Binary Heap

• Priority-queue를 구현하기 위한 자료구조
• Property 
  • heap-ordered(힙 속성): binary tree의 각 노드들은 자식노드보다 항상 크거나 같다. (혹은 항상 작거나 같다)
  • complete binary tree property (완전이진트리) : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다
• Array로 표현 가능
  • a[1]: 가장 큰 (혹은 가장 작은) 원소
  • 노드 k의 부모 노드 : [k/2]
  • 노드 k의 자식 노드 : 2k, 2k+1
    

    

• Heapify
  • Heap-order를 유지하는 작업
  • Top-down (sink) / Bottom-up (swim)
  • 시간복잡도 : O(logN)
• Insertion
  • 새 노드를 맨 끝에 추가하고, heap-order를 만족할 때까지 부모 노드와 교환 (swim)
  • 시간복잡도 : O(logN)
    

    

• Deletion
  • a[1]를 가장 끝 원소랑 교환하고 제거, 새 root를 heap-order를 만족할 때까지 자식 노드와 교환 (sink)
  • 시간복잡도 : O(logN)
    

    

    

특징/활용

시간복잡도 O(logN)을 보장하면서 insertion/deletion을 수행 가능 

최대, 최소값을 뽑아내는데에 용이함

 

 

+ Deque (doubly-ended-queue)

• 앞, 뒤 모두에서 자료를 넣고 뺄 있는 자료구조. Stack 또는 Queue 처럼 사용 가능함.
• 파이썬에서 collections.deque 모듈 지원
• Double-linked list로 구현되어 있음
• pop, append의 시간복잡도 O(1) 
• 그러나 양 끝이 아닌 중간 원소를 접근해야 할 때 시간복잡도 O(N) 

 

 

 

참고자료

- 자료구조와 함께 배우는 알고리즘 입문 파이썬 편

- 이진 힙 https://yoongrammer.tistory.com/80

- Deque의 접근 연산 시간 복잡도 https://velog.io/@mindol/파이썬-deque의-인덱스-접근-연산-시간-복잡도

- 덱 vs 리스트 속도 차이 https://wellsw.tistory.com/122