[알고리즘] 스택과 큐

[ Do it! 알고리즘 코딩테스트 with JAVA ] 강의를 듣고 정리한 글 입니다.

 

스택(stack)____________

스택은 삽입과 삭제 연산이 후입 선출로 이뤄지는 자료구조 이다,(Last-In-First-Out) 후입 선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징을 가진다.

 

새 값이 스택에 들어가면 top이 새 값을 가리키고 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 되어 있으므로 결과적으로는 가장 마지막에 넣었던 값이 나오게 된다.

 

용어

위치

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

연산

- push : top 위치에 새로운 데이터를 삽입하는 연산

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

- peek : top 위치에 있는 데이터를 단순 확인하는 연산

 

 

활용 

스택의 후입선출 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통하기 때문에, 

깊이 우선 탐색, 백트래킹 종류에 효과적이다. 

 

 

큐(Queue)_____________

큐는 삽입과 삭제 연산이 선입 선출로 이뤄지는 자료구조이다. (First-In-First-Out) 먼저 들어온 데이터가 먼저 나간다. 그래서 삽입과 삭제가 양 방향에서 이뤄진다.

 

새 값 추가는 큐의 rear에서 이뤄지고 삭제는 큐의 front에서 이뤄진다.

 

용어

위치

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

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

연산

- add : rear부분에 새로운 데이터를 삽입하는 연산

- poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산

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

 

활용

큐는 순서정보를 유지하기 때문에 노드들의 계층정보를 저장할 수 있다. 따라서 너비우선 탐색에 자주 사용한다.

 

 

- 우선순위 큐

 

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

큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다. heap을 이용해 구현한다.