[python_dataStructure] 7. 큐(Queue)

🧩 큐(Queue) : 데이터를 순차적으로 쌓아 두고, 먼저 적재된 데이터부터 꺼내쓸 수 있도록 자료를 저장해둔 형태

• enqueue : 데이터삽입 + dequeue : 데이터추출
• 선입선출 (FIFO, First in First out)
  • 🔄 스택 : 후입선출 (LIFO, Last in First out)

---

1 실생활에서 큐

📎 웹서버 접속자관리

• 웹서버 : 동시수용 가능 접속자 수 제한적 ⛔️

구분	결과
큐 적용 ✅	접속자 → 대기열, 순차적으로 Client Request 처리
큐 적용 ❌	접속자 > 동시수용가능인원 → 서버다운

---

2 큐 형태

🧩 큐 형태 : 데이터가 들어가는 입구와 나가는 출구가 따로 존재

• 입/출구 따로 존재 → 먼저들어간 자료가 먼저나오는 구조 ✅

1️⃣ 선형 큐 (Linear Queue)

• 데이터 빈자리 발생 → 빈자리 처리를 위해 다음데이터가 위치 이동을 해야함 🚨
• 제한된 메모리 공간을 활용하기 위해 빈자리 ⛔️

2️⃣ 원형 큐 (Circular Queue)

• 선형 큐의 끝을 처음으로 연결해놓은 형태
• 빈자리에 대한 처리 ❌
• 빈자리를 두어도 제한된 메모리 공간 활용가능 ✅

---

3 큐 특징

• 가장먼저 들어간 데이터가 가장먼저 나옴
  • 선입선출(FIFO)
• front : 큐에서 가장 앞 → 처리(삭제)
• rear : 큐에서 가장 마지막 → 삽입

---

4 큐 원리

• 선형 큐 : rear가 메모리공간 마지막 → 더이상 데이터삽입 불가 ⛔️
  • deQueue로 인해 발생한 빈 공간도 활용 불가 ⛔️
• 원형 큐 : 계속해서 데이터 삽입 가능 (위의 단점 해결) ✅

---

5 큐 구현

1️⃣ 큐 생성

>>> queue = [None, None, None] # 미리공간지정
>>> front = rear = -1

2️⃣ enQueue

📍 첫번째데이터
>>> rear += 1 # rear 위치 +1칸 이동
>>> queue[rear] = 'python'

📍 두번째데이터
>>> rear += 1
>>> queue[rear] = 'java'

📍 데이터출력
>>> for i in range(0, len(queue), 1):
		print(queue[i], end = ' ')
        # python java

3️⃣ deQueue

>>> front += 1 # front 위치 +1칸 이동
>>> data = queue[front] # queue[0]
>>> queue[front] = None # none처리
>>> print(data) # python

>>> front += 1 # front 위치 +1칸 이동
>>> data = queue[front] # queue[1]
>>> queue[front] = None # none처리
>>> print(data) # java

---

6 큐 함수구현

1️⃣ enQueue

📍 큐가 꽉찼는지 확인하는 함수
>>> def isQueueFull():
		global SIZE, queue, front, rear
        
        if (rear == SIZE - 1):
        	return True
        else:
        	return False

📍 데이터넣는 enQueue 함수
>>> def enQueue(data):
		global SIZE, queue, front, rear
        
        if (isQueueFull()):
        	print("큐가 꽉 찼습니다.")
            return
        
        rear += 1
        queue[rear] = data

2️⃣ deQueue

📍 큐가 비었는지 확인하는 함수
>>> def isQueueEmpty():
		global SIZE, queue, front, rear
        
        if (front == rear):
        	return True
        else:
        	return False

📍 데이터빼는 deQueue 함수
>>> def deQueue():
		global SIZE, queue, front, rear
        
        if (isQueueEmpty()):
        	print("큐가 비었습니다.")
            return None
        
        front += 1
        data = queue[front]
        
        queue[front] = None
        return data

📍 큐 데이터 출력하는 함수
>>> def checkQueue():
		for i in range(0, len(queue), 1):
        	print(queue[i], end = ' ')

3️⃣ Peek 함수

📍 peek 함수
>>> def peek():
		global SIZE, queue, front, rear
        if (isQueueEmpty()):
        	print("큐가 비었습니다.")
            return None
        return queue[(front + 1) % SIZE] # front 위치 +1칸

---

7 원형큐 함수구현

📍 원형큐 다 찼는지 확인하는 함수
>>> def isQueueFull():
		global SIZE, queue, front, rear

    	if ((rear + 1) % SIZE == front): # rear가 마지막칸에 있는상태
        	return True
    	else:
        	return False

📍 원형큐 데이터넣는 enQueue 함수
>>> def enQueue(data):
    	global SIZE, queue, front, rear
    
    	if (isQueueFull()):
        	print("큐가 꽉 찼습니다.")
        	return
    
    	rear = (rear + 1) % SIZE # rear 한칸 옮긴 후
    	queue[rear] = data

📍 원형큐 데이터빼는 deQueue 함수
>>> def deQueue():
    	global SIZE, queue, front, rear

    	if (isQueueEmpty()):
        	print("큐가 비었습니다.")
        	return None
    
    	front = (front + 1) % SIZE
    	data = queue[front]

    	queue[front] = None
    	return data

---

8 시간복잡도

항목	조회	삽입	삭제
큐(Queue)	O(n)	O(1)	O(1)

• 큐 데이터 검색 시, → 데이터가 저장된 모든 지점을 차례로 순환해야하므로 데이터의 개수만큼 O(n) 시간복잡도가 걸림