Do it! 알고리즘 코딩테스트 자바 정리본 - 스택과 큐

minjung·2023년 1월 7일
0
post-thumbnail

💡스택과 큐

스택배열에서 발전된 형태의 자료구조이다.
스택는 비슷하지만 처리 방식이 다르다.


💡스택

스택은 삽입, 삭제 연산이 후입선출(LIFO)로 이루어지는 자료구조이다.
(LIFO: Last In First Out)

아마 자바의 정석-남궁성 유튜브를 봤다면 스택은 익숙한 내용이지 않을까 싶다.

깊이 우선 탐색(DFS), 백트래킹 종류의 코딩테스트에 효과적이다.

후입선출은 삽입과 삭제가 한쪽에서만 일어난다는 특징이 있다.
top 부분에서만 연산이 일어난다.


스택 용어

  • 위치

    • top : 삽입삭제가 일어나는 위치
  • 연산

    • push : top 위치에 새로운 데이터를 삽입하는 연산
    • pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 (데이터를 꺼내서 확인)
    • peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산 (데이터를 꺼내지 않고 확인)



💡큐

큐는 삽입과 삭제 연산이 선입선출(FIFO)로 이루어지는 자료구조이다.
(FIFO: First In First Out)

너비 우선 탐색(BFS)에서 자주 사용한다.

선입선출은 삽입과 삭제가 양방향에서 이루어진다.


큐 용어

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



💡우선순위 큐

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

front에 항상 최댓값 또는 최솟값이 위치한다.

우선순위 큐는 일반적으로 을 이용해 구현한다.

0개의 댓글