[Python3] 스택, 큐 구현 (feat. collections.deque)

이 글에서는 Python3에서 collections.deque를 통해 스택과 큐를 구현하는 방법에 대해 서술하고자 한다.

 

collections.deque의 경우 '덱' 자료구조를 사용하기 위해 쓸 수도 있지만,

사실 덱 자체가 '스택'과 '큐'의 형태로 사용할 수 있기 때문에 스택이나 큐를 사용하고싶을 때 이것을 사용하면 된다.

 

기본적인 사용법은 다음과 같다.

>>> import collections
>>> S = collections.deque()
>>> S
deque([])

이런식으로 덱 하나를 만들어 주면 이것을 가지고 스택, 큐 처럼 사용이 가능해진다.

 

collections.deque()에서 제공하는 기본적인 함수는 아래와 같다

 

append(x)

- x를 deque 오른쪽에 추가한다.

 

appendleft(x)

- x를 deque 왼쪽에 추가한다.

 

clear()

- 덱에 있는 모든 원소를 지운다. ( 길이가 0으로 변함 )

 

count(x)

- 덱에 있는 원소중 x와 같은 값들이 몇개 있는지 세준다.

 

extendleft(iterable)

- 인자로 들어온 iterble 왼쪽부터 차례대로 appendleft()해준다

 

index(x[, start[, stop[[)

- 인자의 x가 [start, end) 구간 어느 위치에 있는지 확인하는 코드

- 만약 값이 없다면 ValueError가 발생한다.

 

insert(i, x)

- 값 x를 덱 위치중 i번째에 넣는다.

- 만약 인덱스 i가 maxlen보다 크다면 IndexError가 발생한다.

 

pop()

- 덱의 맨 오른쪽 원소를 반환하고 덱에서 해당 값을 제거한다.

 

popleft()

- 덱의 맨 왼쪽 원소를 반환하고 덱에서 해당 값을 제거한다.

 

remove(value)

- 덱에서 value를 찾아 해당 값을 제거해준다. 만약 발견하지 못하면 ValueError가 발생한다.

 

reverse()

- 덱의 원소들을 뒤집어 준다.

 

rotate(n=1)

- n 단계만큼 오른쪽으로 돌려준다. n이 음수일 경우에는 왼쪽으로 돌아간다.

- 덱이 비어있지 않을 때, n이 양수일 경우에는 d.appendleft(d.pop())과 같고

- n이 음수일 경우에는 d.append(d.popleft())와 같다.

 

maxlen

- 덱의 최대 크기를 지정해준다.

 

 

덱은 위의 함수 말고도 iteration, pickling, len(d), reversed(d), copy.copy(d), copy.deepcopy(d) 등을 사용 가능하게 해준다.

---

collections.deque를 이용한 STACK 구현

 

한번 스택을 구현해보자.

스택의 경우 FILO( First-In-Last-Out )의 구조를 가지기 떄문에

append와 pop함수를 사용해주면 된다.

>>> import collections
>>> S = collections.deque()
>>> S.append(1)
>>> S.append(2)
>>> S.append(3)
>>> print(S)
deque([1, 2, 3])
>>> S.pop()
3
>>> S.pop()
2
>>> S.pop()
1
>>> S.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from an empty deque
>>> 

 

 

---

collections.deque를 이용한 Queue 구현

 

이번에는 큐를 구현해보자.

큐의 경우에는 FIFO( Frist-In-First-Out )의 형태기 때문에 appendleft()와 pop을 해주면 된다.

>>> import collections
>>> Q = collections.deque()
>>> Q.appendleft(1)
>>> Q.appendleft(2)
>>> Q.appendleft(3)
>>> Q.pop()
1
>>> Q.pop()
2
>>> Q.pop()
3
>>> Q.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from an empty deque
>>>