📖 Queue 1

📌 Queue

✅ Queue의 특성

• 스택과 마찬가지로 삽입 삭제의 위치가 제한적인 자료구조
  • 큐의 뒤에서는 삽입만 하고 큐의 앞에서는 삭제만 이루어지는 구조
• 선입선출 (FIFO)
  • 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장 먼저 삭제된다.

✅ 큐의 구조 및 기본 연산

• 큐의 선입선출 구조

✅ 큐의 주요 연산

연산	기능
enQueue(item)	큐의 뒤쪽(rear 다음)에 원소를 삽입하는 연산
deQueue()	큐의 앞쪽(front)에서 원소를 삭제하고 반환하는 연산
createQueue()	공백 상태의 큐를 생성하는 연산
isEmpty()	큐가 공백 상태인지 확인하는 연산
isFull()	큐가 포화 상태인지 확인하는 연산
Qpeek()	큐의 앞쪽(front)에서 원소를 삭제하지 않고 반환하는 연산

✅ 큐의 연산 과정

1. 공백 큐 생성 : createQueue()

2. 원소 A 삽입 : enQueue(A)

3. 원소 B 삽입 : enQueue(B)

4. 원소 반환 / 삭제 : deQueue()

5. 원소 C 삽입 : enQueue()

6. 원소 반환 / 삭제 : deQueue()

7. 원소 반환 / 삭제 : deQueue()

✅ 선형 큐

• 1차원 배열을 이용한 큐
  • 큐의 크기 = 배열 크기
  • front : 마지막으로 삭제된 인덱스 : 배열에서 큐의 첫번째 원소의 인덱스에서 1을 뺀 것
  • rear : 저장된 마지막 원소의 인덱스
• 상태 표현
  • 초기 상태 : front = rear = -1
  • 공백 상태 : front = rear
  • 포화 상태 : rear = n-1 (n : 배열의 크기, n-1 : 배열의 마지막 인덱스)

✅ 큐의 구현

• 초기 공백 큐 생성
  • 크기 n인 1차원 배열 생성
  • front와 rear -1로 초기화
• 삽입 : enQueue(item) -> rear++
  • 마지막 원소 뒤에 새로운 원소를 삽입하기 위해
    1) rear 값을 하나 증가시켜 새로운 원소를 삽입할 자리 마련
    2) 그 인덱스에 해당하는 배열 원소 Q[rear]에 item 저장

enQueue(item) {
	if(isFull())
    	print("Queue_Full")
    else {
    	rear <- rear + 1;
        Q[rear] <- item;
    }
}

• 삭제 : deQueue() -> front++
  • 가장 앞에 있는 원소를 삭제하기 위해
    1) front 값을 하나 증가시켜 큐에 남아있는 첫 번째 원소 이동
    2) 새로운 첫 번째 원소를 리턴함으로써 삭제와 동일한 기능

deQueue() {
	if(isEmpty()) // front == rear
    	print("Queue_Empty");
    else {
    	front <- front + 1;
        return Q[front];
    }
}

• 공백상태 및 포화상태 검사 : isEmpty(), isFull()
  • 공백상태 : front = rear
  • 포화상태 : rear = n-1 (n : 배열의 크기, n-1 : 배열의 마지막 인덱스)

isEmpty() {
	if(front == rear)
    	return true;
    else
    	return false;
}

isFull() {
	if(rear == n-1)
    	return true;
    else
    	return false;
}

• 검색 : Qpeek()
  • 가장 앞에 있는 원소를 검색하여 반환하는 연산
  • 현재 front의 한자리 뒤(front+1)에 있는 원소, 즉 큐 첫번째에 있는 원소 반환

Qpeek() {
	if(isEmpty())
    	print("Queue_Empty");
    else
    	return Q[fromt+1]
}

✅ 선형 큐 문제점

• 잘못된 포화상태 인식

  • 선형 큐를 이용한 원소의 삽입/삭제 시, 배열의 앞부분에 활용할 수 있는 공간이 있지만 rear = n-1 즉 포화상태로 인식하여 더 이상의 삽입을 수행하지 않게됨.

    

  • tradeoff 관계 : 시간과 공간의 반비례

  • enQueue, deQueue : O(1)

• 해결 방법 1

  • 매 연산이 이루어질 때마다 저장된 원소들을 배열의 앞부분으로 모두 이동시킴
  • 원소 이동의 많은 시간이 소요되어 큐의 효율성 급격히 떨어짐. (tradeoff)

• 해결 방법 2

  • 1차원 배열을 사용하되, 논리적으로는 배열의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용

✅ 큐의 활용 : 버퍼 (buffer)

• 버퍼 : 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역

• 버퍼링 : 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작

• 버퍼 자료구조

  • 버퍼는 일반적으로 입출력 및 네트워크 관련 기능에서 이용
  • 순서대로 입력/출력/전달 되어야 하므로 FIFO 방식 자료구조인 큐가 활용됨

✅ Stack vs Queue

구분	Stack	Queue
추상 자료구조	O	O
선형	O	O
삽입/삭제	한쪽 끝에서 삽입/삭제 동시	한쪽 끝에서만 삽입 / 한쪽 끝에서만 삭제
연산	push(top++), pop(top--)	enqueue(rear++), dequeue(front++ 또는 rear--)
연산 시간복잡도	push(O(1)), pop(O(1))	enqueue(O(1)), dequeue(O(1) 또는 O(N) (rear--일때))
Java에 구현 여부	stack : 클래스	Queue : 인터페이스, 구현체 : LinkedList(클래스)