[Python] Stack and Queue

 

 

대표적인 자료구조로는 스택과 큐가 존재한다.

간단하게 말하자면 스택은 Last in , First out 이고 큐는 First in , First out 이라고 할 수 있다.

이를 간단하게 예를들어 설명해보자

 

스택 ( Stack )

나중에 넣은 데이터를 먼저빼는 후입선출을 따른다.

예를들면 박스를 쌓는다거나 , 트럭에서 물건을 넣는 상황을 상상해보면 쉽다.

박스를 쌓을 때 박스를 차곡차곡 쌓다가, 뺄 때는 가장 최근에 넣은 것 부터 빼는 구조이다. 당연히 맨 아래것부터 빼는것은 불가능하겠지.

 

파이썬에서는 기본 리스트에서 append()를 사용하거나 pop() 매서드를 사용하여 구현한다.

 

stack = []

stack.append(1) # stack: [1]
stack.append(2) # stack: [1, 2]
stack.append(3) # stack: [1, 2, 3]
stack.append(4) # stack: [1, 2, 3, 4]

stack.pop() # stack: [1, 2, 3]
stack.pop() # stack: [1, 2]
stack.append(3) # stack: [1, 2, 3]
stack.pop() # stack: [1, 2]

큐 ( Queue )

큐(Queue)는 데이터를 먼저 넣은 것을 먼저 빼는 FIFO(First-In-First-Out) 구조를 가지고 있다. 

이는 줄을 서는 것과 유사한데  먼저 온 사람이 먼저 서비스를 받는 것과 같은 개념이다.

 

큐는 파이썬에서 리스트와 함께 구현될 수 있다. 큐를 리스트로 구현하는 것은 가능하지만, 리스트의 pop(0) 메서드를 사용하는 것은 비효율적일 수 있다. 리스트의 pop(0) 메서드는 해당 요소를 삭제하고, 모든 요소를 왼쪽으로 이동시켜야 하기 때문이다.

 

이러한 연산은 많은 데이터를 다룰 때 성능 저하를 초래할 수 있다. 따라서 큐를 효율적으로 구현하기 위해 파이썬의 collections 모듈에서 제공하는 deque(덱, double-ended queue)를 사용하는 것이 좋다.

deque는 양쪽 끝에서의 append와 pop 연산이 O(1) 시간복잡도를 가지므로 큐에 적합하다.

 

from collections import deque

queue = deque()

queue.append(1) # queue: [1]
queue.append(2) # queue: [1, 2]
queue.append(3) # queue: [1, 2, 3]
queue.append(4) # queue: [1, 2, 3, 4]

queue.popleft() # queue: [2, 3, 4]
queue.popleft() # queue: [3, 4]
queue.append(5) # queue: [3, 4, 5]
queue.popleft() # queue: [4, 5]