스택과 큐 자료구조

탐색이란

=> 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
=> 대표적인 그래프 탐색 알고리즘으로는 DFS & BFS 가 있음

스택 자료구조

• 먼저 들어온 데이터가 나중에 나가는 형식
• 선입후출
• 입구와 출구가 동일한 형태
• 예) 박스 쌓기

스택 동작

• 삽입 또는 삭제
• 리스트 자료형 사용

stack = []

stack.append(5)
stack.pop()

print(stack[::1]) #최상단 원소부터 출력 (먼저 나가고자 하는 원소)
print(stack) #최하단 원소부터 출력

큐 자료구조

• 먼저 들어온 데이터가 먼저 나가는 형식
• 선입선출
• 입구와 출구가 모두 뚫려 있는 터널과 같은 형태
• 일종의 대기열

큐 동작

• 리스트 자료형도 사용 가능하지만 시간 복잡도가 높아서 효율이 낮기 때문에 deque 라이브러리 사용
• 구현시 => 오른쪽으로 들어와서 왼쪽으로 나간다

왜 리스트 자료형 대신 deque 자료형을 사용할까?

• 리스트 자료형 사용시 특정 인덱스에 존재하는 원소를 꺼내기 위해 pop()메서드를 이용하여 원소를 꺼내게 되면 원소를 꺼낸 뒤에 원소의 위치를 조정하는 일이 필요함.
• 원소를 꺼내는 일 자체가 O(K)만큼의 시간 복잡도가 소요됨

queue = deque() # 댁 이라고 읽으면 됩니다 !

queue.append(5)
queue.popleft()

print(queue) #먼저 들어온 순서대로 출력
queue.reverse()
print(queue)