[Data Structure] 선형 자료구조: Stack, Queue, Priority Queue, Deque

자료구조 추출되는 데이터

스택	가장 나중에 삽입된 데이터
큐	가장 먼저 삽입된 데이터
우선순위 큐	가장 우선순위가 높은 데이터

스택

• LIFO 방식 (Last In First Out, 나중에 들어온게 먼저 나감, 후입선출), 선입후출
• 박스 쌓기에 비유. 아래(왼쪽)부터 위(오른쪽)로 점점 올리고 맨 위부터 뺌
• 원소의 삽입/삭제가 한쪽 끝(top)에서만 이루어짐 유한 순서 리스트
• append(): 리스트 가장 뒤쪽(오른쪽)에 데이터 삽입
• pop(): 리스트 가장 뒤쪽(오른쪽)에서 데이터 꺼냄

큐

• FIFO 방식 (First In First Out, 먼저 들어온게 먼저 나감)
• 줄서기에 비유. 먼저 온 사람이 먼저 들어감.
• 원소의 삽입 및 삭제가 양쪽 끝에서 일어남 (front, rear)
  • rear에는 삽입(enqueue)만, front에서는 삭제(dequeue)만
• from collections import deque 라이브러리 사용 → queue = deque()
• append(): 온 순서대로 차례로 채움 - 뒤쪽(오른쪽)에 삽입
• popleft(): 처음 온 애부터 꺼냄 - 앞쪽(왼쪽)에서 꺼냄

덱 (Deque)

• double-ended queue의 줄임말
• 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐
• 양쪽에서 삽입, 삭제가 가능하여야 하므로 일반적으로 이중연결 리스트 사용
• from collections import deque

우선순위 큐

• 우선순위(priority)가 가장 높은 데이터를 먼저 삭제.
• 원소의 우선순위 표현과 연산
  • 원소의 우선순위는 key 값으로 표현
  • 삭제 : 우선순위가 가장 높은 원소가 제일 먼저 삭제
  • 삽입 : 우선순위와 관계없이 임의의 순서로 삽입
• 데이터를 우선순위에 따라 처리하고 싶을 때 사용.
• Stack과 Queue도 우선순위 큐의 일종
  • Stack: 삽입 시간이 가장 짧은 원소에 가장 높은 우선순위를 부여한 우선순위 큐
  • Queue: 삽입 시간이 가장 오래된 원소에 가장 높은 우선순위를 부여한 우선순위 큐
• heapq, PriorityQueue 라이브러리 사용 (더 빠른 heapq 주로 사용)
• 우선순위 큐 라이브러리에 데이터 묶음 넣으면 첫 번째 원소 기준으로 우선순위 설정
• 최소 힙(값이 낮은 데이터가 먼저 삭제) or 최대 힙(값이 큰 데이터가 먼저 삭제) 이용
  • 파이썬 라이브러리는 기본적으로 최소 힙(항상 부모 노드가 자식 노드보다 크기가 작은 트리 자료구조.) 구조 이용.
  • 최소 힙을 최대 힙처럼 사용하기 위해 일부러 우선순위에 해당하는 값에 음수 부호(-) 붙여서 넣었다가, 나중에 우선순위 큐에서 꺼낸 후 다시 음수 부호 붙여 원래 값으로 돌리는 방식 사용 가능
• 구현법
  1. 배열
     1. 삽입/삭제 $O(N)$ (shift 필요)
     2. 삽입 위치를 찾기 위해 데이터를 탐색해야 함
  2. 연결 리스트
     • 삽입/삭제 $O(1)$
     • 삭제 시 모든 원소 확인해 우선순위가 가장 높은 것 찾아야 함 → 최악의 경우 $O(N)$ 소요
  3. 힙
     • 데이터 삽입은 트리의 leaf node(자식이 없는 노드)부터 시작
     • 데이터의 삭제는 root node를 삭제함 (우선순위가 가장 큰 것)
     • 힙 자료구조에 N개의 데이터를 모두 넣은 뒤 모두 꺼내면 삽입/삭제 시 $O(logN)$(트리니까)을 N번 반복해서 $O(NlogN)$ → 전체 연산 횟수 $2Nlog_2N$ → $O(NlogN)$
   

  우선순위 큐 구현 방식	삽입 시간	삭제 시간
  리스트	O(1)	O(N)
  힙	O(logN)	O(logN)

 

---

참고 링크

• <자료구조와 C>, 이석호
• <이것이 취업을 위한 코딩테스트다 with 파이썬>, 나동빈
• tech-interview-for-developer