[자료구조/Data Structure] 파이썬으로 큐(Queue) 자료구조 알아보기

큐의 개념

먼저 들어온 요소가 먼저 나가는 FIFO (First In First Out) 형태의 자료구조

 

큐의 동작구조

왼쪽부터 1 -> 2 -> 3

왼쪽부터 4 -> 5 -> 6

이렇듯 먼저 들어온 요소가 제일 먼저 나가게 된다. 사람들이 영화관에 입장하기 위해 줄을 서는 것을 생각하면 편하다.

 

큐의 함수

• enqueue(item) : item을 큐에 삽입
• dequeue() : item을 큐에서 삭제하고 item을 리턴 
• isEmpty() : 큐가 비어있으면 True 리턴 비어있지 않으면 False 리턴

 

큐의 사용 예

• 너비 우선 탐색 (BFS, Breadth-First Search)
• 프린터의 출력
• 우선순위가 같은 작업 예약
• 프로세스 관리

 

파이썬을 활용한 큐 구현 (배열 활용)

class Queue():

    # 초기화
    def __init__(self):
        self.queue = []

    # 큐 개수 가져오기
    def getSize(self):
        return len(self.queue)

    # 데이터 삽입
    def enqueue(self, data):
        self.queue.append(data)

    # 데이터 삭제 및 리턴
    def dequeue(self):
        if self.isEmpty() == 0:
            return 'empty..'
        return self.queue.pop(0)

    # 큐가 비어있는지 확인
    def isEmpty(self):
        if len(self.queue) == 0:
            return True
        return False

    # 데이터 확인
    def printQ(self):
        print(self.queue)​

 

파이썬을 활용한 큐 구현 (노드를 활용한 연결 리스트 큐)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:

    def __init__(self):
        self.head = None
        self.tail = None

    def isEmpty(self):
        if not self.head:
            return True
        return False

    def enqueue(self, data):
        node = Node(data)

        if self.isEmpty():
            self.head = node
            self.tail = node
            return

        # 현재 tail의 next가 지금 들어온 node를 가르키고..
        self.tail.next = node

        # tail의 위치를 지금 현재 들어온 node를 가르키게 한다..
        self.tail = self.tail.next

    def dequeue(self):
        if self.isEmpty():
            return 'empty..'

        data = self.head.data
        self.head = self.head.next
        return data

    def peek(self):
        if self.isEmpty():
            return 'empty..'
        return self.head.data