[자료구조, 알고리즘 스터디] 스택과 큐

1. 자료구조

1) 스택

스택은 사입과 삭제 연산이 LIFO 후입선출로 이루어진 자료구조이다

 

후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다

 

위치

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

 

연산

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

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

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

 

스택은 깊이 우선 탐색 DFS (Depth First Search), 백트래킹 종류의

코딩테스트에 효과적이라 알아두어야 한다

 

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

 

2) 큐

큐는 삽입과 삭제 연산이 FIFO 선입선출로 이루어진 자료구조이다

 

스택과 다르게 먼저 들어온 데이터가 먼저 나간다

 

그래서 삽입과 삭제가 양방향에서 이뤄진다

 

새 값 추가는 큐의 rear 에서

삭제는 큐의 front에서 이뤄진다

 

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

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

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

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

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

 

큐는 너비 우선 탐색 BFS (Breadth First Search) 에서 자주 사용하므로

스택과 함께 잘 알아 두어야 하는 개념이다

 

우선순위 큐도 있다

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

 

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

 

2. 문제 정리

// 문제를 이해한 후 올릴 예정

 

참고

- Do it 알고리즘 코딩 테스트