스택과 큐

스택

 

 

LIFO: Last-in First-out. 나중에 들어온 데이터가 먼저 나간다.

스택은 DFS: Depth First Search, 백트래킹 문제를 풀 때 사용한다.

후입선출은 재귀 함수 알고리즘 원리와 같다.

 

top: 삽입, 삭제가 일어나는 위치

 

파이썬 연산(리스트 이용)

• s.append(data): top 위치에 data를 저장
• s.pop(): top 위치에 있는 데이터를 삭제, 확인
• s[-1]: top 위치에 있는 데이터 확인

 

 

큐

FIFO: First-in First-out. 먼저 들어온 데이터가 먼저 나간다.

삽입과 삭제가 양방향에서 이루어진다.

BFS: Breadth First Search에서 사용됨.

 

rear: 큐에서 가장 끝데이터

front: 큐에서 가장 앞 데이터

 

파이썬 연산(리스트 이용)

• s.append(data): rear에 새로운 데이터 삽입
• s.popleft(): front 부분에 있는 데이터 삭제, 확인
• s[0]: front 부분에 있는 데이터 확인

 

우선순위 큐

• 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
• front에 항상 우선순위가 높은 값(최댓값 또는 최솟값)이 위치한다.
• 우선순위 큐는 일반적으로 힙을 이용해서 구현한다.

# 파이썬에서는 데이터의 순서가 정렬의 우선순위가 된다.