2.1 자료구조 큐(queue) - 선형 큐

큐(queue): 한쪽 방향으로 데이터가 삽입되고 반대 방향으로는 데이터가 삭제되는 구조. 큐는 가장 먼저 삽입된 데이터가 가장 먼저 삭제되므로 선입 선출(FIFO(First-in First-Out) 구조라고도 함.

 

1. 선형 큐(Linear Queue)

선형 큐는 가장 기본적인 큐로 선입 선출 구조를 가진다.

 

다음 그림은 선형 큐의 동작 과정이다.

 

 

큐는 위의 그림과 같이 동작을 한다.

다음 표는 큐의 연산이다.

연산	설명
enQueue	큐의 rear에 원소 삽입
deQueue	큐의 front에 원소 삭제
peek	큐의 front에 원소 확인
isEmpty	큐가 비어있는지 확인

파이썬으로 구현한 큐의 소스코드는 다음과 같다.

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

    def enQueue(self, value):
        self.data.append(value)

    def deQueue(self):
        if self.isEmpty():
            return #큐가 비어있을시 예외 처리
        else:
            self.data.pop(0)
    def peek(self):
        if self.isEmpty():
            return #큐가 비어있을시 예외 처리
        else:
            return self.data[0]

    def isEmpty(self):
        return not self.data

queue = Queue()             #큐 생성
print(queue.isEmpty())      #큐가 비어있는지 화인
queue.enQueue(1)            #큐에 1 삽입
queue.enQueue(2)            #큐에 2 삽입
queue.enQueue(3)            #큐에 3 삽입
print(queue.peek())         #front가 가르키는 곳 확인
print(queue.data)           #큐 확인
queue.deQueue()             #가장 먼저 삽입된 1 삭제
print(queue.data)           #큐 확인

다음은 파이썬의 모듈 queue를 활용한 구현한 예이다.

from queue import Queue

queue = Queue()     #큐 생성
queue.put(1)        #큐에 데이터 삽입
queue.put(2)        #큐에 데이터 삽입
queue.put(3)        #큐에 데이터 삽입
print(queue.get())  #큐에 데이터 삭제