큐?

Queue

데이터가 들어오는 위치는 가장 뒤에 있고, 데이터가 나가는 위치는 가장 앞에 있어서, 먼저 들어오는 데이터가 먼저 나가게된다. 이러한 구조를 선입선출(FIFO)의 자료구조라고 하며 대기열이라고도 한다.

특징

• 삭제 연산만 수행되는 front와 삽입 연산만 수행되는 rear

활용

• 프로세스 관리
• 캐시 구현
• 너비 우선 탐색

연산

• enqueue : queue의 맨 뒤에 원소를 추가
• dequeue : queue의 맨 앞에 있는 원소를 삭제

큐 연산과 시간 복잡도

1. Enqueue (큐에 요소 추가)

• 시간 복잡도:
• 설명: 큐의 끝에 요소를 추가하는 연산은 포인터나 인덱스를 업데이트하는 간단한 작업이므로 상수 시간에 수행됩니다.

2. Dequeue (큐에서 요소 제거)

• 시간 복잡도: O(1)
• 설명: 큐의 앞에서 요소를 제거하는 연산도 포인터나 인덱스를 업데이트하는 간단한 작업이므로 상수 시간에 수행됩니다.

3. Peek/Front (큐의 앞 요소 접근, 제거 없이)

• 시간 복잡도: O(1)
• 설명: 큐의 앞 요소에 접근하는 것은 탐색이 필요하지 않기 때문에 상수 시간에 수행됩니다.

4. IsEmpty (큐가 비었는지 확인)

• 시간 복잡도: O(1)
• 설명: 큐가 비었는지 확인하는 것은 보통 front와 rear 포인터를 비교하거나 크기 변수를 확인하는 간단한 작업이므로 상수 시간에 수행됩니다.

5. IsFull (큐가 가득 찼는지 확인, 제한된 큐에서 해당)

• 시간 복잡도: O(1)
• 설명: 큐가 가득 찼는지 확인하는 것도 보통 크기 변수를 최대 용량과 비교하는 간단한 작업이므로 상수 시간에 수행됩니다.

구현

1. 배열 기반 큐

• 장점
  - 고정된 메모리사용
  - 인덱스 접근 속도
• 단점
  - 고정된 크기 : 배열로 고정되어 있어 큐가 가득차면 더이상 요소를 추가할 수 없다.
  - 메모리 낭비 가능성 : 배열 크기를 활용하지 못하면 메모리가 낭비될 가능성이 있음
  - 순환 큐 필요 : 효율적인 요소를 추가 제거하려면 순환 큐를 사용해야한다.

2. 연결리스트 기반 큐

• 장점
  - 동적 크기: 큐의 크기가 가변적이어서 필요에 따라 확장 또는 축소할 수 있습니다.
  - 메모리 효율성: 필요한 만큼만 메모리를 사용합니다.
• 단점
  - 추가 메모리 사용: 각 노드가 데이터 외에 포인터(링크)를 저장하기 때문에 추가 메모리가 필요합니다.
  - 접근 속도: 배열보다 접근 속도가 느립니다. 노드의 탐색은 선형 시간에 수행됩니다. O(n)
  

Java Queue