자료구조 활용 [개념]

spring_sunshine 2022. 8. 13. 10:04

나중에 입력된 데이터가 먼저 출력되는 LIFO 자료구조 (하노이의 탑..)
파이썬에서는 리스트 자료형을 사용하여 스택 구조로 데이터를 처리할 수 있다.
리스트로 데이터의 입출력을 하려면 아래와 같은 함수를 사용한다.
- 데이터 입력: push → append()
- 데이터 출력: pop → pop()
- pop은 데이터 맨 마지막 값을 뽑아 반환시켜 준다. pop으로 뽑아낸 데이터는 리스트에서 없어진다.

stack = [] # 빈 리스트 선언
stack.append(2)
stack.append(5)
stack.append(8)
# stack: [2,5,8]
stack.pop() # 8
stack.pop() # 5
stack.pop() # 2

queue = [4,5,6]
queue.append(7)
# queue: [4,5,6,7]
queue.pop(0)
# queue: [5,6,7]

위와 반대 방향으로 큐 자료구조를 이용하고 싶다면 insert(0,x) 함수를 사용하여 맨 앞에 데이터를 삽입하고, 맨 뒤 데이터를 제거할 수도 있다.

queue = [4,5,6]
queue.insert(0,3)
# queue: [3,4,5,6]
queue.pop()
# queue: [3,4,5]

collections 모듈의 deque는 double-ended queue의 약자로, 데이터를 양방향으로 추가/제거할 수 있는 자료구조이다.
deque는 popleft() 메서드를 이용하여 맨 앞 데이터를 제거할 수 있다. list 객체의 pop(0) 을 사용할 때 처럼 데이터는 뒤에서 앞으로 흐르게 된다.

from collections import deque
queue = deque([4,5,6])
queue.append(7)
# queue: [4,5,6,7]
queue.popleft()
>> 4
# queue: [5,6,7]

deque는 appendleft(x) 라는 메서드도 제공하는데, 이걸 사용하면 데이터를 맨 앞에 삽입할 수도 있다. list 객체의 insert(0,x) 를 사용할 때 처럼 데이터는 앞에서 뒤로 흐르게 된다.

from collections import deque
queue = deque([4,5,6])
queue.appendleft(3)
# queue: [3,4,5,6]
queue.pop()
>> 6
# queue: [3,4,5]

deque의 popleft()와 appendleft()는 모두 O(1)의 시간 복잡도를 갖기 때문에 앞에서의 list의 pop(0)과 insert(0,x) 대비 성능 상의 큰 이점이 있다.
하지만 deque도 무작위 접근(random access)의 시간 복잡도는 O(N)이라는 단점이 있다. 내부적으로 연결 리스트(linked list)를 사용하고 있기 때문에 i번째 데이터에 접근하려면 맨 앞/뒤부터 i번의 순회가 필요하기 때문이다.
마지막 방법은 queue 모듈의 Queue 클래스를 사용하는 방법이다.
주로 멀티 쓰레딩(threading) 환경에서 사용되며, 내부적으로 라킹(locking)을 지원하여 여러 개의 쓰레드가 동시에 데이터를 추가하거나 삭제할 수 있다.
deque와 달리 방향성이 없기 때문에 데이터 추가/삭제가 하나의 메서드로 처리된다. 데이터를 추가하려면 put(x) 메서드를, 데이터를 삭제하려면 get() 메서드를 사용한다.

from queue import Queue
que = Queue()
que.put(4)
que.put(5)
que.put(6)
que.get()
>> 4
que.get()
>> 5
que.get()
>> 6