스택(Stack), 큐(Queue), 힙(heap), 우선순위 큐(Priority Queue), heapq

1. 스택(Stack)

• 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 출력되는 후입선출(LIFO, Last In First Out) 형식으로 데이터를 다루는 자료구조
• 데이터를 추가하는 것을 push, 데이터를 꺼내는 것을 pop이라고 한다
• 활용 예시: 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS)

 

 

1) 리스트(list) 기반 구현

• python에서 stack을 가장 간단히 구현하는 방법은 list를 이용하는 것이다.
• append 메소드를 사용하면 맨 뒤에 데이터가 추가 되고, pop을 하게 되면, 맨 앞의 데이터가 나온다
• 시간복잡도: $O(1)$

# stack 선언
s = []

# push - O(1)
s.append(1) # [1]
s.append(2) # [1, 2]
s.append(3) # [1, 2, 3]

# pop - O(1)
s.pop() # [1, 2]
s.pop() # [1]

 

 

 

 

2. 큐(Queue)

• 먼저 저장한 데이터가 먼저 출력되는 선입선출(FIFO, First In First Out)형식으로 데이터를 다루는 자료구조
• 데이터를 추가하는 것을 enqueue라고 하고, 데이터를 꺼내는 것을 dequeue라고 한다
• 시간복잡도
  • Enqueue: $O(1)$
  • Dequeue: $O(1)$

 

 

1) deque (덱)기반 구현

• Double-eneded Queue
• 양 끝에 추가/삭제를 지원하며 Python에서 Queue를 구현할 수 있는 자료구조
• append 메소드를 사용하면 맨 뒤에 데이터가 추가 되고, popleft을 하게 되면, 맨 뒤의 데이터가 나온다 -> O(1)
• 활용 예시: Cache구현, 프로세스 관리, 너비우선탐색(BFS) 등

 

deque (덱) 내부 구조

typedef struct BLOCK {
    struct BLOCK *leftlink;
    PyObject *data[BLOCKLEN];
    struct BLOCK *rightlink;
} block;

typedef struct {
    PyObject_VAR_HEAD
    block *leftblock;
    block *rightblock;
    Py_ssize_t leftindex;       /* 0 <= leftindex < BLOCKLEN */
    Py_ssize_t rightindex;      /* 0 <= rightindex < BLOCKLEN */
    size_t state;               /* incremented whenever the indices move */
    Py_ssize_t maxlen;
    PyObject *weakreflist;
} dequeobject;

• 블락 단위로 묶인 이중 연결 리스트
  • deque는 단순히 데이터를 하나씩 연결한 구조가 아닌 64개의 데이터를 담을 수 있는 블락들을 이중 연결 리스트로 연결한 구조
• C언어로 구현된 블락의 구조
  • 각 블락은 leftlink와 rightlink라는 포인터를 통해 이전 블락과 다음 블락을 가리킴
  • 또한, 각 블락에는 64개의 데이터를 담을 수 있는 배열이 존재하며, 이를 통해 데이터를 저장함
• dequeobject 구조
  • leftblock과 rightblock이라는 포인터 두 개를 가리키며, 데이터의 삽입 및 삭제가 여기에서 일어남
  • leftindex와 rightindex라는 두 변수가 있어, 각 블락 내에서 실제로 데이터가 추가되거나 삭제되는 위치를 가리킴
• link와 block의 차이
  • leftlink와 rightlink는 현재 블락에서 그 이전/다음 블락을 가리키는 포인터
  • deque -> [Block 1] <-> [Block 2] <-> [Block 3] ^ ^ leftlink rightlink
  • leftblock와 rightblock은 deque의 가장 왼쪽/오른쪽에 있는 블락을 나타내는 포인터
  • leftblock -> Block 1 <-> Block 2 <-> Block 3 <- rightblock

 

초기화

from collections import deque

# 비어있는 큐 만들기
que = deque()

# 원소가 있는 큐 만들기
que = deque([1, 2, 3])

 

데이터 추가

• 왼쪽 끝에 새로운 값 을 추가: appendleft()
• 오르쪽 끝에 새로운 값을 추가: append()

from collections import deque

que = deque()
que.append(3)
que.append(6)
que.append(9)
que.append(12)
print(que) # deque([3, 6, 9, 12])

que = deque()
que.appendleft(3)
que.appendleft(6)
que.appendleft(9)
que.appendleft(12)
print(que) # deque([12, 9, 6, 3])

 

데이터 추출

from collections import deque

que = deque([1, 2, 3])
while que:
    print([que.popleft())
# 1
# 2
# 3

que = deque([1, 2, 3])
while que:
    print([que.pop())
# 3
# 2
# 1

 

주요 연산 시간복잡도

Operation	Average Case	Amortized Worst Case
Copy	$O(n)$	$O(n)$
append	$O(1)$	$O(1)$
appendleft	$O(1)$	$O(1)$
pop	$O(1)$	$O(1)$
popleft	$O(1)$	$O(1)$
extend	$O(k)$	$O(k)$
extendleft	$O(k)$	$O(k)$
rotate	$O(k)$	$O(k)$
remove	$O(n)$	$O(n)$
Get Length	$O(1)$	$O(1)$
- $k$: 회전수

 

appendleft 작동 원리

1. 비어있는 블락
   1. 초기 상태
      • 이때 deque는 내부적으로 하나의 블락을 할당하고 있음
      • 초기 상태에서 leftindex는 블락의 끝(BLOCKLEN)인 64를 가리키고 있고, rightindex는 블락의 시작(0)을 가리키고 있음
   2. appendleft 호출
      • 예를 들어, appendleft(10)을 호출하면, leftindex를 하나 줄인 후(leftindex--), 그 자리에 10을 넣음
      • 이제 leftindex는 63을 가리키게 되고, 10은 블락의 맨 끝에서 한 칸 앞에 저장됨
      • Block (64 slots): [_, _, _, ..., 10] leftindex: 63 rightindex: 0
   3. appendleft 재호출
      • 예를 들어, appendleft(20)을 호출하면, 마찬가지로 leftindex를 하나 줄인 후(leftindex--), 그 자리에 20을 넣음
      • 이제 leftindex는 62를 가리키게 되고, 20은 10 앞에 저장함
2. 공간이 있는 블락
   1. 초기 상태
      • 한 블락안에 데이터가 저장되어 있으나 추가로 데이터를 저장할 수 있음
      • deque([10, 20, 30])가 있고, 한 블락 안에 저장되어 있다고 가정해 보자
      • 블락의 크기는 64이지만, 현재는 3개의 데이터만 저장되어 있고, leftindex는 61, rightindex는 63을 가리키고 있음
   2. appendleft 호출
      • 예를 들어, appendleft(5)를 호출하면, leftindex를 하나 줄이고(leftindex--), 그 자리에 5를 저장함
      • Block (64 slots): [..., _, _, 5, 10, 20, 30] leftindex: 60 rightindex: 63
   3. appendleft 재호출
      • 예를 들어, appendleft(1)을 호출하면, 마찬가지로 leftindex를 하나 줄여서 그 자리에 1을 저장합니다.
      • Block (64 slots): [..., _, 1, 5, 10, 20, 30] leftindex: 59 rightindex: 63
3. 블락이 가득 찼을 때
   1. 초기 상태
      • appendleft()를 여러 번 호출하여, 블락이 가득 차게 되면, 이 블락에는 더 이상 데이터를 추가할 수 없음
      • Block 1 (64 slots): [64, 63, 62, ..., 1] leftindex: 0 rightindex: 63
      • 이제 새로운 데이터를 appendleft() 하려면 새로운 블락을 생성해야 함
   2. appendleft 호출
      • 예를 들어, appendleft(65)를 호출하면 새로운 블락이 생성되고, 새 블락의 첫 번째 자리에 65가 추가됨
      • New Block 2 (64 slots): [65, _, _, _, _, ..., _] (이 블락에 데이터가 추가됨) Block 1 (64 slots): [64, 63, 62, ..., 1] (이전 블락은 그대로 유지됨)
      • 새 블락은 이전 블락과 이중 연결 리스트로 연결됨
      • 새 블락의 rightlink는 기존 블락을 가리키고, 기존 블락의 leftlink는 새 블락을 가리킴

 

 

 

3. 우선순위 큐(Priority Queue)

1) heap

정의

• 요소의 우선순위를 매기고 관리하는 대표적인 알고리즘
• 완전 이진 트리 형태로 루트 노드가 언제나 최대값/최소값을 가짐 → 최대 힙(max heap), 최소 힙(min heap)
  • min heap: 자식 노드의 값이 부모 노드의 값보다 크며 이 속성이 모든 노드에 재귀적으로 적용된 트리 형태의 자료구조
  • max heap: 자식 노드의 값이 부모 노드의 값보다 작으며 이 속성이 모든 노드에 재귀적으로 적용된 트리 형태의 자료구조
• 서브트리보다 항상 큰 키를 갖고으며 위로 올라갈수록 큰 값을 가지지만, 왼쪽 서브트리와 오른쪽 서브트리 간 관계가 정의 되어있지 않음

 

최대 힙의 원소 삽입

1. 트리의 마지막 자리에 새로운 원소를 임시로 저장
2. 부모 노드와 키 값을 비교하며 자신 보다 큰 값을 가진 부모 노드를 만나기 전 까지 위로 이동 ⇒ 시간복잡도: $O({\log}n)$

 

최대 힙의 원소 삭제

1. 루트 노드의 제거
2. 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치
3. 자식 노드들과의 값 비교로 자신 보다 작은 값을 가진 자식 노드를 만나기 전 까지 아래로 이동⇒ 시간복잡도: $O({\log}n)$

      → 자식 노드가 두 개면 더 큰 키값을 가진 쪽으로 이동

 

 

2) 우선순위 큐(Priority Queue)

• 힙을 큐 형태로 구현한 자료구조
• 큐(Queue)가 FIFO(선입선출) 방식을 따르지 않고 원소들의 갖고 있는 우선순위에 따라 나오는 자료구조
• 대표적인 예로 '운영체제의 CPU 스케쥴러'가 있다
• 우선순위 큐는 두가지 방식으로 구현 가능하다
  1. Enqueue 시 우선순위를 유지하도록 한다
  2. Dequeue 시 우선순위를 유지하도록 한다
  • 위 두가지 방식 중 'Enqueue 시 우선순위를 유지' 가 미세하게 유리하다
  • 왜냐하면 Dequeue 시 우선순위가 높은 것을 선택하도록 할 경우 모든 데이터에 대하여 다 살펴봐야하기 때문

 

 

3) heapq

• 파이썬에서 제공하는 힙(Heap) 기반의 우선순위 큐(priority queue)를 구현한 모듈
• 최소 힙(min-heap)을 기본적으로 사용하여, 우선순위가 가장 작은 값이 가장 먼저 처리되도록 구현되어 있음

 

주요 기능

• heappush(heap, item)
  • item을 힙에 추가합니다
  • 힙 구조를 유지하면서 새로운 요소가 적절한 위치에 추가됨
  • 시간 복잡도: O(log N) (N은 힙에 있는 요소의 개수)
• heappop(heap)
  • 힙에서 가장 작은 요소를 제거하고 반환함
  • 힙 특성을 유지하면서 재정렬됨
  • 시간 복잡도: O(log N)
• heapify(iterable)
  • 리스트를 힙으로 변환함
  • 주어진 iterable(리스트)를 힙 구조로 바꾸어줌
  • 시간 복잡도: O(N) (N은 iterable의 길이)
• heappushpop(heap, item)
  • item을 힙에 추가하고, 바로 가장 작은 요소를 제거
  • heappush()와 heappop()을 함께 수행하는 것과 유사하지만, 힙을 재정렬하는 횟수가 줄어듬
  • 시간 복잡도: O(log N)
• heapreplace(heap, item):
  • 힙에서 가장 작은 요소를 제거하고, 그 자리에 새로운 item을 추가
  • 이는 heappop()과 heappush()를 함께 수행하는 것과 비슷하지만, 힙 재정렬이 한 번만 이루어짐
  • 시간 복잡도: O(log N)

 

주요 시간 복잡도

Operation	Average Case
heapify(iterable)	$O(N)$
heappush(heap, item)	$O(\log N)$
heappop(heap)	$O(\log N)$
heappushpop(heap, item)	$O(\log N)$
heapreplace(heap, item)	$O(\log N)$