스택 ( Stack )
-
후입선출(Last In First Out, LIFO)의 형태를 가진 자료구조
-
데이터의 개수가 스택의 크기를 초과하면 overflow가 일어나고, 아무것도 없을 때 pop을 하거나 데이터에 접근시 underflow가 일어나기 때문에 구현시 예외처리가 필수적
큐 ( Queue )
- 선입선출(First In First Out, FIFO)의 형태를 가지고 있는 자료구조
- 먼저 온 것이 먼저 나가는 특성을 가지는 것이, 줄을 서서 기다릴 때 먼저 온 사람이 먼저 들어가는 것과 같은 이치
덱 ( Deque )
- Deque ( Double Ended Queue )
- 스택과 큐와 달리 양쪽 모두 삽입과 삭제가 가능한 자료구조
파이썬에서 사용법
- 스택
'''
파이썬에서는 list를 이용하여 쉽게 스택을 구현 할 수 있으며
실제 사용시에는 collections에 구현되어 있는 deque를 이용하면 더 빠름
from collections import deque
dq = deque()
# 스택으로 사용시
dq.append() # 가장 오른쪽에 추가
dq.pop() # 가장 오른쪽 원소 삭제 및 반환
# 큐로 사용시
dq.append() # 가장 오른쪽에 추가
dq.popleft() # 가장 왼쪽 원소 삭제 및 반환
'''
stack = []
stack.append(1) # push
stack.append(2)
stack.pop() # pop, 2
stack[-1] # top, 1
len(stack) # size, 1- 큐
'''
stack과 마찬가지로 파이썬에서는 list를 이용하여 쉽게 구현 할 수 있다.
하지만 이 또한 deque를 사용하는 것이 빠르고 쉽다.
from collections import deque
dq = deque()
# 스택으로 사용시
dq.append() # 가장 오른쪽에 추가
dq.pop() # 가장 오른쪽 원소 삭제 및 반환
# 큐로 사용시
dq.append() # 가장 오른쪽에 추가
dq.popleft() # 가장 왼쪽 원소 삭제 및 반환
'''
queue = []
queue.append(1) # 가장 오른쪽에 원소 추가 push
queue.append(2) # 가장 오른쪽에 원소 추가 push
queue.pop(0) # 가장 왼쪽 원소 삭제 및 반환, pop, 1
len(queue) # size 및 empty 판단
queue[0] # 제일 앞의 원소를 읽기, getFront
queue[-1] # 제일 마지막의 원소를 읽기, getBack- 덱
# python에서는 collections의 deque를 사용하면 된다
from collections import deque
dq = deque()
dq.append(x) # 오른쪽(끝)에 삽입
dq.appendleft(x) # 왼쪽(앞)에 삽입
dq.extend(iterable) # iterable arguments를 오른쪽(끝)에 삽입
dq.extendleft(iterable) # iterable arguments를 왼쪽(앞)에 삽입.
# 'de'를 삽입하면, 'e','d' 순서로 삽입된다
dq.pop() # 오른쪽(끝)에서 제거와 반환
dq.popleft() # 왼쪽(앞)에서 제거와 반환
dq.rotate(n) # n번만큼 elements를 이동시켜주는 method. 양수면 오른쪽으로, 음수면 왼쪽으로 rotateReference
글 쓰는 개발자