큐(Queue)

큐

선입선출(FIFO) 방식으로 데이터를 처리하는 선형 자료구조이다. 가장 먼저 들어온 데이터가 가장 먼저 나가는 특징을 가지고 있다.

 

구조

 

장점

순차적 처리에 적합하다.

구현이 간단함.

deque으로 구현 시 메모리 관리 효율이 좋음

 

단점

중간 데이터 접근이 불가능함.

배열 기반 큐는 삽입,삭제 시 앞 공간이 낭비됨.

복잡한 자료 구조에는 부적합함.

 

큐의 주요 연산

 

연산	기능	시간복잡도
enqueue	삽입	O(1)
dequeue	삭제	O(1)
front	맨 앞 요소 조회	O(1)
size() / empty()	사이즈/ empty 확인	O(1)

 

리스트로 구현(python)

class Queue:
    def __init__(self):
        self.q = []

    def isEmpty(self):
        if len(self.q) == 0:
            return True
        else:
            return False

    def enqueue(self, elem):
        self.q.append(elem)

    def dequeue(self):
        if len(self.q) == 0:
            print("Can't dequeue")
            return None
        else:
            return self.q.pop(0)

    def front(self):
        if self.isEmpty():
            print("No Front Element")
            return None
        else:
            return self.q[0]

    def getSize(self):
        return len(self.q)

    def display(self):
        print("Current Queue: ",self.q)
        pass

q = Queue()

q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)

q.display()
print(q.getSize())
print(q.front())

q.dequeue()
q.dequeue()
q.dequeue()
print(q.front())
q.display()

 

리스트로 구현 시 enqueue의 시간복잡도는 O(1), dequeue의 시간복잡도는 O(n)이다. 맨 앞의 요소를 삭제하고, 그 뒤의 요소를 다시 이동시켜줘야 하기 때문이다.

 

큐의 변형 구조

• 원형 큐 : 앞 뒤를 연결해 앞 공간의 낭비를 최소화 시킴.
• 덱 : 양쪽 모두에서 삽입과 삭제가 가능한 큐
• 우선순위 큐 : 일반 큐는 순서대로 처리하지만, 우선순위가 높은 요소를 먼저 처리함.

큐의 활용 예시

• 프로세스 스케줄링 : OS는 프로세스를 큐에 저장하고, 순서대로 처리
• 버퍼 : 네트워크 전송 시 패킷을 임시 저장해 순서대로 전송
• BFS : 큐를 사용해 가까운 노드부터 탐색함.
• 멀티스레딩 작업 큐 : 여러 스레드 간 작업 전달에 큐를 사용해 안전하게 작업을 분산함