알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 스택과 큐

03-5 스택과 큐

스택과 큐의 핵심 이론

① 스택

- 스택은 삽입과 삭제 연산이 후입선출(LIFO: Last-in First-out)로 이뤄지는 자료구조

- 후입선출은 삽입과 삭제가 한 쪽에서만 일어남

- 깊이우선탐색(DFS), 백트래킹 종류의 코딩테스트에 효과

파이썬의 스택

위치

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

연산(리스트 이름이 s일 때)

- s.append(data): top 위치에 새로운 데이터를 삽입하는 연산

- s.pop(): top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산

- s[-1]: top 위치에 현재 있는 데이터를 단순 확인하는 연산

 

② 큐- 큐는 삽입과 삭제 연산이 선입선출(FIFO: First-in First-out)로 이뤄지는 자료구조- 삽입과 삭제가 양방향에서 이뤄짐- 너비우선탐색(BFS:Breadth First Search)에서 자주 사용 

파이썬의 큐

위치

- rear: 큐에서 가장 끝 데이터를 가리키는 영역

- front: 큐엥서 가장 앞의 데이터를 가리키는 영역

연산(리스트 이름이 s일 때)

- s.append(date): rear 부분에 새로운 데이터를 삽입하는 연산

- s.popleft(): front 부분에 있는 데이터를 삭제하고 확인하는 연산

- s[0]: 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산

 

+ 우선순위 큐

- 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

- 큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치

- 주로 힙(max/min)을 통해 구현