큐 (Queue) in Python

선입 선출 (FIFO - First In First Out) 선형 자료구조.

한쪽 끝에서 밀어 넣고 다른 쪽 끝에서 뽑아서 씀.

 

[큐의 자료구조 구현 ]

 

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

 

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):
    	return self.data.pop(0) #데이터 원소를 삭제(리턴)
    def peek(self):
    	return self.data[0]

 

 다른 연산들과 달리 dequeue의 시간복잡도는 O(n)이다. 이는 맨 앞 원소를 삭제하면 뒤 원소들이 다 앞으로 당겨지기 때문이다. 나머지 연산들의 시간복잡도는 모두 O(1)이다.

 

 

2. 연결리스트 (linked list)를 이용하여 구현 - 양방형 연결 리스트 이용

 배열과 달리 dequeue연산을 해도 다른 원소들이 밀리지 않기 때문에 코드 구현이 간단하다.

-> 연산의 복잡도는? 메모리 사용량은?

 

class LinkedListQueue:
	def __init__(self):
    	self.data = DoublyLinkedList() 
    def size(self):
    	return self.data.getLength()
    def isEmpty(self):
    	return self.data.getLength()==0
    def enqueue(self,item):
    	node = Node(item)
        self.data.insertAt(self.data.getLength()+1,node)
    def dequeue(self):
    	return self.data.popAt(1)
    def peek(self):
    	return self.data.getAt(1).data
        

 

 

pythonds.basic.queue 라이브러리에서 Queue import해 연산들을 바로 사용할 수도 있다.

 

[큐의 활용]

- 자료 생성, 이용이 비동기적으로 일어나는 경우 (Producer & Consumer)

- 자료를 생성하는 작업이 여러 곳에서 일어나는 경우 (Producer1, Producer2)

- 자료를 이용하는 작업이 여러 곳에서 일어나는 경우 (Consumer1, Consumer2)

- 자료를 생성, 이용하는 작업이 모두 다 양쪽에서 일어나는 경우(Producer1,2, Consumer 1,2)

- 자료를 처리, 생성하고 같은 자료를 또 처리해야 하는 경우

=> 컴퓨터 시스템 or 운영체제에서 많이 사용

 

 

[환형 큐]

- dequeue의 시간 복잡도 문제 (O(n)) 해결.

- 정해진 개수의 저장 공간을 비 돌려가며 이용

- 큐가 가득 찼는지를 isFull()로 판단 -> 선형 큐와 달리 큐의 길이가 정해져 있으므로(append연산 x)

- front, rear 적절히 활용하여 구현

 

[환형 큐의 자료구조 구현]

 

 - 배열로 구현

 

class CircularQueue:
	def __init__(self,n):
    	self.maxCount = n #최대 큐 길이 설정 (maxCount를 n으로)
        self.data = [None] *n #인자로 주어진 최대 큐 길이 설정
        self.count = 0
        self.front = -1 #이 다음부터 큐 시작
        self.rear = -1 #여기까지 큐 진행
    
    def size(self):
    	return self.count #현재 큐 길이 반환
    def isEmpty(self):
    	return self.count==0 #큐가 비어있는가?
    def isFull(self):
    	return self.count==maxCount #큐가 꽉 찼는가?
        
    def enqueue(self,x) #큐에 데이터 원소 추가
    	if self.isFull():
        	raise IndexError
        self.rear = (self.rear+1)%self.maxCount
        self.data[self.rear] = x
        self.count +=1
        
    def dequeue(self): #큐에서 데이터 원소 뽑아내기
    	if self.isEmpty():
        	raise IndexError
        self.front = (self.front+1)%self.maxCount
        x = self.data[self.front]
        self.count-=1
        return x
        
    def peek(self): #큐의 맨 앞 원소 들여다보기
    	if self.isEmpty(): #볼 원소가 없음
        	raise IndexError
        return self.data[(self.front+1)%self.maxCount]

 

[ 우선순위 큐 ]

 

- 원소들의 우선순위에 따라 다르게 꺼내지는 큐.

- FIFO X

- 운영체제 CPU 스케줄러에서 사용

- Enqueue(원소를 추가)시 우선순위를 유지하도록 하거나(애초에 정렬된 상태로 유지), Dequeue할 때 우선순위가 높은 것을 선택하도록 하는(정렬되지 않은 것에서 찾기) 두 가지 방법이 있다.

=> 일일이 찾아볼 필요가 없는 전자 (우선순위 유지)가 유리.

- 선형 배열, 연결리스트를 이용할 수 있다. 

=>시간적으론 연결리스트, 공간적으론 선형 배열이 유리.

 

 

[우선순위 큐의 자료구조 구현]

 

- 양방향 리스트로 구현

 

from doublylinkedlist import Node, DoublyLinkedList

class PriorityQueue:
	def __init__(self,x):
    	self.queue = DoublyLinkedList()
    def enqueue(self,x):
    	newNode = Node(x)
        curr =self.queue.head
        while curr.next.next and x>=curr.next.data:
        	curr = curr.next #작은 숫자가 우선 순위가 높다고 가정
        self.queue.insertBefore(curr,newNode)

 

getAt()메서드를 이용하지 않는 이유?

 getAt(pos) 할때마다 그 위치까지 칸을 순회함. 한번에 순회하면서 우선순위를 따지기 위해 getAt(pos)로 선행 노드를 불러오지 않는다.