스택
스택(Stack) 자료구조는 박스 쌓기에 비유할 수 있다. 박스는 아래에서부터 위로 차곡차곡 쌓으며, 아래에 있는 박스를 치우기 위해서는 위에 있는 박스를 먼저 내려야한다. 이러한 구조를 선입후출(First In Last Out) 또는 후입선출(Last In First Out) 구조라고 한다.
파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요 없다. 기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작한다.
큐
큐(Queue)는 놀이공원 대기 줄에 비유할 수 있다. 먼저 온 사람이 먼저 들어가게 된다. 이러한 구조를 선입선출(First In First Out) 구조라고 한다.
파이썬에서는 collections 모듈의 deque 클래스를 사용하면 된다.
from collections import deque
q = deque()
for i in range(4):
q.append(i)
print(q)
while q:
print(q.popleft())deque([0, 1, 2, 3])
0
1
2
3
선입후출 구조이므로 popleft() 메서드로 먼저 들어온 순서대로 꺼낸다.
deque 클래스는 넣고 뺴는 속도가 리스트 자료형에 비해 효율적이라서 자주 사용된다. 다음은 deque 클래스의 메서드들을 정리한 것이다.
| append(item) | deque의 오른쪽(끝)에 원소를 추가합니다. |
| appendleft(item) | deque의 왼쪽(앞)에 원소를 추가합니다. |
| clear() | deque의 모든 원소를 제거하고 비웁니다. |
| count(item) | deque 안에 있는 원소 중에서 해당하는 값과 일치하는 원소의 개수를 반환합니다. |
| extend(iterable) | iterable(반복 가능한 객체)의 모든 원소를 deque의 오른쪽(끝)에 추가합니다. |
| extendleft(iterable) | iterable(반복 가능한 객체)의 모든 원소를 deque의 왼쪽(앞)에 추가합니다. 추가되는 순서는 iterable의 역순입니다. |
| pop() | deque의 오른쪽(끝)에서 원소를 제거하고 반환합니다. deque가 비어있을 경우 IndexError가 발생합니다. |
| popleft() | deque의 왼쪽(앞)에서 원소를 제거하고 반환합니다. deque가 비어있을 경우 IndexError가 발생합니다. |
| remove(item) | deque에서 해당하는 값과 일치하는 첫 번째 원소를 제거합니다. 만약 해당하는 원소가 없을 경우 ValueError가 발생합니다. |
| reverse() | deque의 모든 원소들의 순서를 뒤집습니다. |
| rotate(n) | deque를 오른쪽으로 n번 회전합니다. 음수 값을 가질 경우 왼쪽으로 회전합니다. |
회전이 어떤 뜻이냐면 [1, 2, 3, 4]의 원소를 가진 deque에 rotate(1) 적용하면 [3, 0, 1, 2]가 된다. rotate(-1)을 적용한다면 [1, 2, 3, 0]이 된다.