2️⃣

큐 & 스택 (Queue & Stack)

큐(Queue)

큐(Queue)

Queue

queue는 먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out)형식으로 데이터를 저장하는 자료구조입니다.

queue의 rear(뒤)에 데이터를 추가하는 것을 enqueue라고 합니다. 또한 queue의 front(앞)에서 데이터를 꺼내는 것을 dequeue라고 합니다.

list 기반 구현

python에서 queue를 가장 간단히 구현하는 방법은 단순하게 list를 이용하는 것입니다. list의 append 메소드를 사용하면 맨 뒤에 데이터가 추가 되고, pop을 하게 되면, 맨 앞의 데이터가 나오기 떄문입니다.

# queue 선언
q = []

# enqueue O(1)
q.append(1) # [1]
q.append(2) # [1, 2]
q.append(3) # [1, 2, 3]

# dequeue O(n)
q.pop(0) # [2, 3]
q.pop(0) # [3]
Python
복사

Linked list 기반 구현

queue를 만들기 위해, 앞서 배운 linked list를 직접 구현하는 일은 없을 것입니다.python에서 정의된 deque의 구조를 살펴보면, doubly linked list로 구현되어 있습니다. deque은 맨 앞, 맨 뒤 모두 데이터의 삽입과 제거가 가능한 자료구조 입니다.

	맨 앞(왼쪽)	맨 뒤(오른쪽)
삽입	appendleft()	append()
제거	popleft()	pop()

모든 연산은 doubly linked list로 구현 되어 있기에 모든 연산이

O(1)

의 시간 복잡도를 갖습니다. 그렇기에 deque에서

O(n)

의 시간복잡도를 가지는 list 기반 구현 queue보다 효율적이라 할 수 있습니다.

from collections import deque

# deque 선언
q = deque()

# enqueue O(1)
q.append(1) # [1]
q.append(2) # [1, 2]
q.append(3) # [1, 2, 3]
q.appendleft(0) # [0, 1, 2, 3]

# dequeue O(1)
q.popleft() # [1, 2, 3]
q.popleft() # [2, 3]
q.pop() # [3]
Python
복사

스택 (Stack)

Stack

stack은 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO(Last In First Out)형식으로 데이터를 저장하는 자료구조입니다.

stack의 top에 데이터를 추가하는 것을 push라고 하고 stack의 top에서 데이터를 추출 하는 것은 pop이라고 합니다.

LIFO

python에서 stack을 구현하는 가장 간단한 방법은 역시 list를 선언하는 것입니다.

# 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]
Python
복사