스택, 큐, 덱

1. 스택 (Stack)

후입선출(LIFO : Last In First Out). 파이썬의 list를 사용해서 구현할 수 있다.

• 기본 연산
  • push : 스택에 원소 추가
  • pop : 스택에 가장 마지막으로 들어온 원소를 제거하고 그 값을 반환
  • peek : 스택에 가장 마지막으로 들어온 원소를 조회
• list로 스택 구현하기

stack = []
stack.append(3) # 3 push
stack.append(2) # 2 push
stack.append(5) # 5 push
stack.pop() # pop -> 5 가 제거됩니다
print(stack[-1]) # peek / python의 음수 인덱스를 활용. 맨 마지막 요소가 출력됨

2. 큐 (Queue)

선입선출(FIFO : First In First Out). 파이썬의 collections.deque 를 사용.

• 기본 연산
  • enqueue : 큐에 원소 추가
  • dequeue : 큐에 가장 먼저 들어온 원소를 제거하고 그 값을 반환
  • peek : 큐에 가장 먼저 들어온 원소를 조회
• collections.deque로 큐 구현하기

파이썬에서는 큐의 기본 연산을 모두 collections.deque에서 지원하고 있다.

from collections import deque

deck = deque()          # 신규 덱(큐) 생성 ([])
deck.append(1)          # 1 enqueue. 원소 추가
deck.append(3)          # 3 enqueue
b = deck.popleft()      # dequeue -> 가장 먼저 들어온 1이 제거됩니다. 
print(b[0])             # peek

3. 덱 (Deque)

양방향에서 데이터 조작을 할 수 있는 자료구조. 스택 + 큐라고 생각할 수 있다. 파이썬의 collections.deque 를 사용한다.

• 기본 연산
  • append : 오른쪽 끝에 원소 추가
  • appendleft : 왼쪽 끝에 원소 추가
  • pop : 오른쪽 끝 원소 제거 후 값 반환
  • popleft : 왼쪽 끝 원소 제거 후 값 반환
• collections.deque로 덱 구현하기

from collections import deque

deck = deque()          # 신규 데크 생성 ([])
deck.append(1)          # 오른쪽 끝에 1을 삽입 ([1])
deck.appendleft(2)      # 왼쪽 끝에 2를 삽입 ([2, 1])
deck.append(3)          # 오른쪽 끝에 3을 삽입 ([2, 1, 3])
a = deck.pop()          # 오른쪽 끝에서 삭제 후 a에 그 값을 저장 ([2, 1])
print(a)                # 3
b = deck.popleft()      # 왼쪽 끝에서 삭제 후 b에 그 값을 저장 ([1])
print(b)                # 2

Q. 그럼 list보다 많은 연산이 지원되는 deque를 list 대신 쓰면 안되나요?

A. 양쪽 끝의 값들만 조작하는 경우 deque를, 그 외의 경우에는 list를 사용하는 것이 유리하다.

⇒ 인덱스를 사용하는 액세스는 양쪽 끝에서는 O(1)이지만 중간에서는 O(n)으로 느려진다. 빠른 무작위 액세스를 위해서는 리스트를 사용하십시오. (링크)