오느른 선형 자료구조의 대표적인 스택과 큐에 대해서 알아보고, 이를 Python으로 구현하는 방법에 대해서 알아보는 시간을 가져보았다
스택 (Stack)
스택은 데이터를 차례대로 쌓아올린 형태의 자료구조라고 볼 수 있다. 데이터를 차례대로 넣고 데이터를 삭제할 때는 위에서 부터 삭제하는 구조로, 처음 들어온 데이터가 가장 마지막에 삭제되는 구조이다.
위의 그림처럼 데이터가 들어오는 순서대로 쌓이고 삭제를 할 땐 제일 최근에 들어오는 데이터가 먼저 삭제되는, Last In First Out(LIFO)!! 선입선출 구조를 가지고 있다.
일상생활속의 스택구조의 예를 들면 박스를 쌓기나 연탄사용할 때를 예로 들 수 있다.
그렇다면 이제 스택을 파이썬으로 구현하는 방법에 대해서 알아보자
스택 Python 구현
스택을 Python으로 구현할때는 리스트를 사용하면 된다. 리스트를 사용하여 데이터를 넣을 때는 append()를 사용하고, 데이터를 삭제할 때는 pop()을 사용하면 된다 .
append()는 리스트의 마지막에 데이터를 넣어주는 메소드고, pop()은 리스트의 가장 마지막에 들어간 데이터를 삭제해주는 메소드이다.
stack = list()
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.pop()
stack.append(5)
stack.append(6)
stack.pop()
print(stack) # 출력값 : [1,2,3,5]큐 (Queue)
큐는 선입선출의 구조를 가지고 있다. 데이터가 들어온 순서대로 삭제되는 Last In Last Out(LILO) 구조이다. 다르게 말하면 First In First Out (FIFO) 구조라고도 할 수 있다.
위의 그림처럼 먼저 들어간 데이터가 먼저 삭제된다. 일상속에서 예를 들면 은행창구 번호표 처럼 대기표를 뽑은 순서대로 일을 처리하는 구조와 비슷하다고 볼 수 있다.
큐 Python 구현
파이썬에서 큐를 구현하는 방법은 세가지가 있다. 첫번째는 리스트를 이용하는 방법, 두번째는 Queue 모듈을 사용하는 방법, 세번째는 collections 모듈의 deque를 사용하는 방법이 있다. 먼저 큐에 데이터를 넣는 것을 enqueue, 삭제하는 것을 dequeue 라고 부르는 것을 알아두고 방법을 알아보겠다 !
List 구현
첫번째, 리스트로 구현하는 방법은 스택과 비슷하게 enqueue는 append(), dequeue는 pop(0)을 사용하면 된다. 그러나 pop(0)은 O(n)의 시간복잡도를 가지기 때문에 효율성이 매우 떨어진다.
queue = list()
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.pop(0)
queue.append(5)
queue.append(6)
queue.pop(0)
print(queue) #출력값 : [3,4,5,6]Queue모듈로 구현
두번째로 Queue모듈을 사용하는 방법이다. Queue모듈의 queue는 데이터를 단방향에서 추가하고 삭제하는 구조이다. enqueue 시에는 put()메소드를, dequeue 시에서는 get()메소드를 사용한다. get() 메소드는 시간복잡도가 O(1)이기 때문에 리스트로 구현하는 queue보다 비교적 효율적이라고 볼 수 있다.
import queue
queue = queue.Queue()
queue.put(1)
queue.put(2)
queue.put(3)
queue.put(4)
print(queue.get()) # 1
queue.put(5)
queue.put(6)
print(queue.qsize()) # 출력값 : 5collections모듈의 deque로 구현
마지막으로는 collections모듈의 deque를 사용하는 방법이다. deque는 double-ended queue의 약자로 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조이다.
deque는 양방향이기때문에 append(),pop()과 더불어 appendleft(), popleft()가 있다. appendleft(), popleft()는 왼쪽에 데이터를 삽입하고, 데이터를 삭제하는 메소드이다. appendleft(), popleft()는 각각 시간복잡도가 O(1)이기 때문에 리스트로 구현하는 것 보다 효율적이다.
큐를 구현할때 일반적으로 양방향을 지원하고 효율이 좋은 deque를 자주 사용한다.
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
queue.popleft()
queue.append(4)
queue.append(5)
queue.popleft()
print(queue) # 출력 : deque([3, 4, 5])
스택과 큐에 대한 기본적인 것들을 알아봤으니 이제 알고리즘 문제풀러가야지 ~
