1. 스택(Stack)

'쌓는다'는 의미.
하나의 리스트에 대해 한쪽 방향에서만 접근이 가능한 구조.
LIFO (Last-In, First-Out) 가 기본원리

1) 스택의 구조

• push : 새로운 데이터를 리스트의 가장 마지막 데이터 뒤에 넣음
• peek : 가장 마지막 데이터가 무엇인지 확인함
• pop : 가장 마지막 데이터를 꺼냄

2) 스택 구현하기

1. 직접 구현

class Stack(list):
    # push
    push = list.append
    
    # peek
    def peek(self):
    	return self[-1]
    
    # pop은 원래 list의 내장함수라서 따로 구현하지 않음

2. List를 스택으로 구현

s = []

# push
s.append(1)
s.append(2)
s.append(3)

print(s)  # [1,2,3]

# pop
print(s.pop())  # 3
print(s)  # [1,2]

# peek
print(s[-1])  # 2
print(s)  # [1,2]

3) 스택의 활용

• 웹브라우저에서 이전 페이지 / 다음 페이지
• 깊이우선탐색(DFS)

---

2. 큐 (Queue)

'일이 처리되기를 기다리는 리스트'라는 의미.
하나의 리스트에 양쪽에서 접근이 가능한 구조.
FIFO (First-In, First-Out) 가 기본원리.

먼저 줄선 사람이 먼저 입장하는 걸 상상하자

1) 큐의 구조

• put : 새로운 데이터를 리스트의 가장 마지막 데이터 뒤에 넣음
• peek : 가장 먼저 들어간 데이터가 무엇인지 확인
• get : 가장 먼저 들어간 데이터를 꺼냄

2) 큐 구현

1. 직접 구현

class Queue(list):
    # put
    put = list.append
    
    # peek
    def peek(self):
    	return self[0]
    
    # get
    def get(self):
    	return self.pop(0)

2. 이미 구현된 클래스 import

from queue import Queue

q = Queue()

# put
q.put(1)
q.put(2)
q.put(3)
print(q)  # [1,2,3]

# get
print(q.get())  # 1
print(q)  # [2,3]

# peek
print(q.peek())  # 2
print(q)  # [2,3]

3. List를 큐로 활용

q = []

# put
q.append(1)
q.append(2)
q.append(3)
print(q)  # [1,2,3]

# get
print(q.pop(0))  # 1
print(q)  # [2,3]

# peek
print(q[0])  # 2
print(q)  # [2,3]

3) 큐의 활용

• 프린터 인쇄 대기열
• 너비우선탐색(BFS)

---

3. 데크 (Deque)

양쪽에서 모두 데이터를 처리할 수 있는 자료형.
양방향이기 때문에 리스트보다 출입 연산이 더 효율적이다.

1) 데크 구현

1. 파이썬 모듈 import

from collections import deque

d = deque()

d.append(1)
d.append(2)
d.append(3)
print(d)  # [1,2,3]

d.appendleft(4)
d.appendleft(5)
print(d)  # [4,5,1,2,3]

print(d.pop())  # 3
print(d)  # [4,5,1,2]

print(d.popleft())  # 4
print(d)  # [5,1,2]

문제 풀 때 큐를 리스트로 사용하는 것보다 deque로 사용하는 것이 효율적이다.

• 리스트에서 get 메서드를 구현하기 위해 pop(0)을 사용시 시간복잡도는 O(n)이다. 맨 앞 데이터를 추출하고 빈 자리에 모든 데이터들을 한칸씩 앞으로 당겨야 하기 때문이다.
• 반면 deque의 popleft() 메서드를 사용하면 시간복잡도는 O(1)이다.

2) deque 활용 문제

1. 리스트트를 n만큼 회전시키기
   a = [1,2,3,4,5] 일 때, 이 리스트를 2만큼 오른쪽으로 회전시켜 [4,5,1,2,3] 으로 만들기

from collections import deque

a = [1,2,3,4,5]
q = deque(a)
q.rotate(2)
result = list(q)
print(result)  # [4,5,1,2,3]