[자료구조] 스택과 큐

✔ 스택과 큐

• 배열에서 발전된 형태의 자료구조
• 스택과 큐는 구조는 비슷하지만 처리 방식이 다름 (LIFO ↔ FIFO)

✔ 스택

스택이란?

• 삽입과 삭제 연산이 후입선출(LIFO : Last-in First-out, FILO : First-in Last-out)로 이뤄지는 자료구조
• 삽입과 삭제가 한 쪽에서만 일어나는 특징을 가짐
• 새 값이 스택에 들어가면 top이 새 값을 가리킴
• 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 됨

스택 용어

• top : 삽입과 삭제가 일어나는 위치
• push : top 위치에 새로운 데이터를 삽입하는 연산
• pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
• peak : top 위치에 현재 있는 데이터를 단순 확인하는 연산

스택은 언제 사용할까?

• 깊이 우선 탐색, 백트래킹 종류의 코딩 테스트에 효과적
• 개념 자체는 재귀 함수 알고리즘 원리와 일맥상통

✔ 큐

큐란?

• 삽입과 삭제 연산이 선입선출(FIFO : First-in First-out, LILO : Last-in Last-out)로 이뤄지는 자료구조
• 먼저 들어온 데이터가 먼저 나감
• 삽입과 삭제가 양방향에서 이뤄짐
• 새 값 추가는 큐의 rear에서 이뤄지고, 삭제는 큐의 front에서 이뤄짐

큐 용어

• rear : 큐의 가장 끝 데이터를 가리키는 영역
• front : 큐에서 가장 앞의 데이터를 가리키는 영역
• add : rear 부분에 새로운 데이터를 삽입하는 연산
• poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산
• peek : 큐의 맨 앞인 front에 있는 데이터를 확인할 때 사용하는 연산

큐는 언제 사용할까?

• 너비 우선 탐색에서 자주 사용

✔ 우선순위 큐

우선순위 큐란?

• 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
• 큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치함
• 하지만 front가 아닌 데이터가 정렬되어 있는 것은 아니므로 주의

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn