큐

FIFO: First in, First out
식당에서 줄서기 -> 먼저 온 사람부터 들어감

• 스택과 달리 삽입/삭제가 다른 쪽에서 일어남.
• 삭제는 front에서, 삽입은 rear에서 일어남.

enqueue(e) 새로운 자료 e를 큐 맨 뒤에 추가
dequeue() 가장 앞에 있는 요소를 꺼내기

큐의 활용
순서대로 처리되어야 하는 곳에 많이 쓰임. 예) 컴퓨터와 프린터 사이 시간이나 속도 차이를 극복하기 위한 임시 기억 장치

원형 큐 Circular Queue

아직도 헷갈려!!! 🤯

큐를 선형으로 구현하게 되면 큐 앞 부분에 공간이 있어도 rear를 더 증가시킬 수 없기 때문에 모든 요소들을 최대한 앞으로 옮겨야 함. -> 원형 큐로 극복!

원형 큐: 처음과 끝이 연결된 구조. 고정된 공간에 자료를 순환시켜 사용하는 원리.
실제로 원형은 아니고 인덱스를 계속 증가시키다가 큐의 사이즈와 같아지면 회전시켜주면 됨.

front = (front+1) % queue_size
rear = (rear+1) % queue_size

• front에는 값을 채우지 않음.‼️
  큐가 공백인 상태와 포화인 상태를 구분하기 위해 필요함.
• 공백이면 front==rear, 포화면 front가 rear 바로 다음 요소를 가리킴.

코드

class CircularQueue:
    def __init__(self):
        self.front = 0
        self.rear = 0
        self.q_list = [None] * QSIZE
        
    def enqueue(self, data):
        if not self.isFull():
            self.rear = (self.rear + 1) % QSIZE
            self.q_list[self.rear] = data
        else:
            print("Queue is full! Cannot enqueue data.")
           
    def dequeue(self):
        if not self.isEmpty():
            self.front = (self.front + 1) % QSIZE
            data = self.q_list[self.front]
            self.q_list[self.front] = None  # 초기화
            return data
        else:
            print("Queue is empty! Cannot dequeue data.")
            return None
        
    def isEmpty(self):
        return self.front == self.rear				 # 공백상태면 front와 rear가 같은 곳을 가키림
    
    def isFull(self):
        return self.front == (self.rear + 1) % QSIZE # 포화상태면 front가 rear보다 한 칸 앞에 있음
    
    def clear(self):
        self.front = self.rear

    def display(self):
        print("Queue state:", self.q_list)

파이썬에서는 queue 모듈로 불러올 수 있음.

import queue
q = queue.Queue(maxsize=20)

if not q.full():   # 포화 여부 
	q.put(3)       # enqueue

if not q.empty():  # 공백 여부
	q.get()        # dequeue

덱 deque

double-ended queue의 준말로 전단과 후단에서 모두 삽입/삭제가 가능한 큐.

파이썬에서는 collections 모듈에서 deque 클래스를 제공하고 있음.

import collections
dq = collections.deque()

# 후단에서 삽입/삭제
dq.append(1)     
dq.pop()

# 전단에서 삽입/삭제
dq.appendleft(2)
dq.popleft()

deque의 활용에 대해서는 아직 모르겠다

---

BFS

스택으로 구현했던 DFS와 달리