스택(Stack)과 큐(Queue) - P 89부터 다시
기본적인 자료구조의 입출력에 대한 정의는 알고 있다. 스택은 LIFO(Last In First Out)이고 큐는 FIFO(First in First Out)
이다. 이를 토대로 알고리즘 관련을 푼다.
스택
스택은 삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조이다. 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다.
다음의 그림과 같다.
파이썬의 스택
위치
- top : 삽입과 삭제가 일어나는 위치를 뜻한다.
연산(리스트 이름이 s일 때)
- s.appned(data) : top 위치에 새로운 데이터를 삽입하는 연산이다.
- s.pop() : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.
- s[-1] : top위치에 현재 있는 데이터를 단순 확인하는 연산이다.
다음의 그림은 예시이다.
스택은 깊이 우선 탐색(DFS : Depth First Search), 백트래킹 종류에 활용된다. 또한 개념 자체가 재귀 함수 알고리즘
원리와 일맥 상통하다.
큐
큐는 연산이 선입선출로 이뤄지는 자료구조이다. 먼저 들어왔던 것들의 데이터가 나간다. 삽입과 삭제가 양방향에서 이루어진다.
파이썬의 큐
위치
- rear : 큐에서 가장 끝 데이터를 가리키는 영역이다.
- front : 큐에서 가자 앞의 데이터를 가리키는 영역이다.
연산(리스트 이름이 s일 때)
- s.append(data) : rear부분에 새로운 데이터를 삽입하는 연산이다.
- s.popleft() : front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
- s[0]: 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산이다.
다음 그림은 예시이다.
※ from collections import deque 를 해야한다.
큐는 너비 우선 탐색(BFS : Breadth Frist Search)에서 자주 사용하므로 이 역시도 스택과 함께 잘 알아두어야
하는 개념이다.