[Java 풀스택 과정 강의] 3월 6일

※ TIL와는 별개로 적는 개인 개발 일지라서 말은 좀 편하게하는 페이지입니다.
일지이기 때문에 일기의 성격이 더 강합니다.

 

 

스택보다 좀 더 걸리는 큐 이야기.

강의일지에 비해서 코테런이 늦어지고 있는데, 양도 많기도 하고 개인적인 코테런도 있어서… 한동안은 수업 위주로 올려볼까 싶기도 한다. 어차피 수업도 곧 끝이 나기 때문에…

 

Queue 개념

지난 번 Stack과는 달리 Queue는 FIFO(First-In First-Out) 방식의 자료 구조이다. 제일 먼저 들어온 게 제일 먼저 삭제되는 형태다. Stack과는 완전히 반대 개념에 가깝다고 보면 좋다. Stack의 경우 입출구가 동일하지만, Queue의 경우 입구와 출구가 정 반대의 방향에 있다. 이런 걸 줄서기 방식과 비슷하다고 생각하면 좋다.

 

Queue 연산

연산명	해설
enqueue(x)	큐의 맨 뒤(rear)에 x 원소 삽입
dequeue()	큐의 맨 앞에 있는 원소를 반환 및 삭제
peek()	큐의 맨 앞에 있는 원소를 반환(삭제하지 않음)
isEmpty()	큐가 비었는지 확인
isFull()	큐가 가득찼는지 확인

 

이 외 연산 시각화에 대해서 짚고 넘어갔다.

 

선형 큐

그야말로 선형Linear 큐Queue라고 할 수 있다. 선형 큐의 기본 구성 요소는 아래와 같다.

• 데이터를 저장할 배열(arr)
• 삭제 위치를 가리키는 front
• 삽입 위치를 가리키는 rear
• 최대 크기인 capacity

 

이 경우 배열 생성 시 크기는 고정시키고 초기 front와 rear는 -1로 설정한다.

다만, 이 선형 큐의 경우 데이터를 삭제하거나 할 때 메모리적인 낭비가 있기도 하여 회전에는 자주 사용되지 못한다.

 

 

원형 큐

선형 큐의 위와 같은 문제점을 해결하기 위해서 나온 것이 원형 큐이다. 그야말로 원형으로 된 큐로, 배열의 끝과 처음이 연결된 구조라고 할 수 있다. 중요한 것은 선형과 별개로 이동이 없이 인덱스만이 순회되는데, 이때 이 인덱스들을 사용할 때 나머지 연산이 들어가게 된다.

공백은 front == rear, 포화는 (rear + 1) % N == front로 판별한다. 포화 판별을 위해서 한칸 정도는 비워둔다(N+1)

 

 

기타

Deque와 LinkedList에 대해서 비교했는데, Deque는 양방향 큐인 지점이 꽤 장점으로 나타난다.

다만 Deque 관련 연산 소개는 9일에 해주셨는데, 여기에다가 적어보기로 한다.

 

연산명	해설
addFirst(e)	데크 앞쪽에 요소 추가
addLast(e)	데크 뒷쪽에 요소 추가
removeFirst()	앞쪽 요소를 제거 및 반환
removeLast()	뒤쪽 요소를 제거 및 반환
peekFirst()	앞쪽 요소를 조회
peekLast()	뒤쪽 요소를 조회
isEmpty() / size()	비어있는가 크기는 어떠한가 확인

 

최근은 add보다는 offer를, remove보다는 poll을 더 사용하는 것 같다.