스택과 비슷한 자료구조 큐에 대해서 알아보겠습니다!

큐(Quesues)

• 자료 (data element)를 보관할 수 있는 (선형) 구조
• 단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 한다.
  • 인큐(enqueue) 연산
• 꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약 존재
  • 디큐(dequeue) 연산
• 선입선출 (FIFO-First-In First-Out) 특징을 가지는 선형 자료구조
• 비유: 대기열, 입장열 (줄 슬땐 뒤에서 부터, 들어갈 땐 앞에서 부터)

큐의 동작

• 초기 상태: 비어 있는 큐 (empty queue)
  • Q = Queue()
• 데이터 원소 A를 큐에 추가
  • Q.euqueue(A)
  • Q.enqueue(B)
• 데이터 원소 꺼내기
  • r1 = Q.dequeue() -> A 출력
  • r2 = Q.dequeue() -> B 출력

큐의 추상적 자료구조 구현

(1) 배열(array)을 이용하여 구현

• python 리스트와 메서드들을 이용

(2) 연결 리스트 (linked list)를 이용하여 구현

• 이전 강의에서 마련한 양방향 연결 리스트 이용

연산 정의

• size(): 현재 큐에 들어 있는 데이터 원소의 수를 구한다.
• isEmpty(): 현재 큐가 비어 있는지를 판단
• enqueue(x): 데이터 원소 x를 큐에 추가
• dequeue(): 큐의 맨 앞에 저장된 데이터 원소를 제거 (또한, 반환)
• peek(): 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거하지 않음)

배열로 구현한 큐

class ArrayQueue:
	
    def __init__(self):
    	self.data = []
    
    def size(self):
    	return len(self.data)
    
    def isEmpty(self):
    	return self.size() == 0
    
    def enqueue(self, item):
    	self.data.append(item)
    
    def dequeue(self):
    	retrun self.data.pop(0)
        
    def peek():
    	return self.data[0]

배열로 구현한 큐의 연산 복잡도

• size(), isEmpty(), enqueue(), peek(): O(1)
• dequeue(): O(n)
  • 맨 앞 원소를 꺼낼 경우 하나씩 원소들을 땡겨야하기 때문에

라이브러리를 활용한 큐

from pythonds.basic.queue import Queue
Q = Queue()
dirt(Q)