[자료구조] Queue

Queue

• 가장 최근에 넣은 데이터를 가장 나중에 빼내는 데이터 구조
  • 선입 선출(FIFO(First In First Out))

코드

• push(val) : val를 가장 위의 리스트에 추가
• pop() : 가장 아래의 리스트를 제거
• peek() : 리스트의 가장 위에 있는 value 출력
• isEmpty() : 큐가 비어있는지 boolean 값으로 출력

class Queue:
    #리스트를 이용하여 큐 생성
    def __init__ (self):
        self.top = []
    
    #큐의 크기를 출력
    def __len__(self):
        return len(self.top)

    #큐 내부 자료를 string으로 변환하여 반환
    def __str__(self):
        return str(self.top[::1])
    
    #큐 초기화
    def clear(self):
        self.top=[]

    # 데이터 입력(push)
    def push (self, item):
        self.top.insert(0, item)

    # 데이터 입력(pop)
    def pop(self):
        #if Queue is not empty
        if not self.isEmpty():
            #pop and return 
            return self.top.pop(-1)
        else:
            print("Queue underflow")
            exit()
    
    #자료가 포함되어 있는지 여부 반환
    def isContain(self, item):
        return item in self.top
    
    #큐에서 top의 값을 읽어온다
    def peek(self):
        if not self.isEmpty():
            return self.top[-1]
        else:
            print("underflow")
            exit()

    #큐가 비어있는지 확인
    def isEmpty(self):
        return len(self.top)==0 # True or False
    
    #큐 크기 반환
    def size(self):
        return len(self.top)
    

Queue 사용사례

• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용
  • 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장
• 노드를 접근한 순서대로 처리
• 캐시(Cache) 구현
• 우선순위가 같은 작업 예약 (인쇄 대기열)
• 선입선출이 필요한 대기열 (티켓 카운터)
• 콜센터 고객 대기시간
• 프린터의 출력 처리
• 윈도 시스템의 메시지 처리기
• 프로세스 관리