[핵심요약] 스택과 큐 핵심 이론

스택과 큐는 리스트에서 조금 더 발전한 형태의 자료구조입니다.

스택과 큐는 구조는 비슷하지만 처리 방식은 다릅니다.

 

♥스택

스택은 삽입과 삭제 연산이 후입선출로 이뤄지는 자료구좋입니다. 
후입선출은 삽입과 삭제가 한쪽에서만 일어나는 특징이 있습니다.

 

파이썬의 스택

→위치

＊ top : 삽입과 삭제가 일어나느 위치를 뜻한다.

 

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

＊s.append(data) : top 위치에 새로운 데이터를 삽입하는 연산이다.
＊s.pop() : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.
＊s[-1] : top 위치에 현재 있는 데이터를 단순 확인하는 연산이다.

 

-> 내용

스택은 깊이 우선 탐색, 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아 두어야 한다.
후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통하기 때문이다.

 

 

♥ 큐

큐는 삽입과 삭제 연산이 선입선출로 이뤄지는 자료구조입니다.
스택과 다르게 먼저 들어온 데이터가 먼저 나갑니다.
그래서 삽입과 삭제가 양방향에서 이뤄집니다.

파이썬의 큐

→위치

＊ rear : 큐에서 가장 끝 데이터를 가리키는 영역이다.
＊ front : 큐에서 가장 앞의 데이터를 가리키는 영역이다.

 

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

＊s.append(data) : rear부분에 새로운 데이터를 삽입하는 연산이다.
＊s.pop() : front 부부넹 있는 데이터를 삭제하고 확인하는 연산이다.
＊s[0] : 큐의 맨 앞(front)에 있는 데이터를 확인하는 연산이다.

 

큐는 너비 우선 탐색에서 자주 사용하므로 이 역시도 스택과 함께 잘 알아두어야 하는 개념입니다.

 

※ 우선순위 큐도 있어요!

우선순위 큐는 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조입니다. 
큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치합니다.
우선순위 큐는 일반적으로 힙을 이용해 구현하는데 힙은 트리 종류 중 하나이므로 여기서는 개념정도만 알아두면 된다.