[자료 및 알고리즘] 5. 큐와 덱, 우선순위 큐 (파이썬)

큐란?

 

선입선출의 자료구조

- 먼저 들어온 데이터가 먼저 처리된다.

 

 

전단과 후단이 있다.

전단 : 삭제 통로

후단 : 삽입 통로

 

큐의 추상 자료형

 

데이터 : 선입선출의 접근 방법을 유지하는 요소들의 모음

 

연산

- enqueue(e) : 요소 e를 큐의 맨 뒤에 추가한다.

- dequeue() : 큐의 맨 앞에 잇는 요소를 꺼내 반환한다.

- isEmpty() : 큐가 비어있으면 True를 아니면 False를 반환한다.

- isFull() : 큐 가득 차 있으면 True를 아니면 False를 반환한다.

- peek() : 큐의 맨 앞에 있는 항목을 삭제하지 않고 반환한다.

 

큐의 오류 상황

 

오버플로우 (OverFlow) :

큐가 꽉 차있는 경우, enqueue()가 수행되면 더 이상 들어갈 수 없게 되는 상황이다.

 

언더플로우 (UnderFlow) :

큐가 비어있는 경우, dequeue()이나 peek() 연산이 수행되면, 삭제나 참조가 불가능하기 때문에,

오류가 나는 상황이다.

 

원형 큐

선형 큐(원래 큐 형태)의 단점을 보완하기 나온 형태이다.

선형 큐를 구현하면 문제점이 나오게 될 것이다.

선형 큐

그것은 바로 빈 공간이다. 데이터를 들여보내는 Enequeue와 내보내는 Dequeue를 하면,

어떤 데이터 안에 빈 공간이 있을 수 있다. 그러나 이것을 차 있다고 생각할 것이다.

그러면 이를 해결하기 위하여 두 가지 방법이 존재한다.

 

1. 예시의 3의 데이터를 앞으로 두칸 땡기면 된다

=> 데이터가 3뿐만 아니라 여러 개 있다면 구현하기 힘들며, 비효율적이다.

 

2. 원형 큐를 사용하면 된다.

=> 사용하기 편함. 효율적임

 

원형 큐 사용시 함수의 상태

- isEmpty() : front == rear 면 공백 상태

- isFull() : front == rear은 하면 논리상으로는 맞으나 isEmpty()와 구분이 가지 않으므로,

front == rear + 1을 선택한다.

 

배열을 이용한 큐의 클래스 구현

 

class CircularQueue : 
	def __init__( self, capacity = 8 ) :
    	self.capacity = capacity
        self.array = [None] * capactiy
        self.front = 0
        self.rear = 0
        
    def isEmpty(self) :
    	return self.front == self.rear
        
    def isFull(self) :
        return self.front == (self.rear+1) % self.capacity
        
    def enqueue(self, item):
    	if not self.isFull():
        	self.rear = (self.rear + 1) % self.capacity
            self.array[self.rear] = item
        else : pass
        
    def dequeue (self) :
    	if not self.isEmpty() :
        	self.front = (self.front + 1) % self.capacity
            return self.array[self.front]
        else: pass
            
    def peek(self) :
        if not self.isEmpty():
            return self.array[(self.front + 1) % self.capacity]
        else : pass

 

덱이란?

 

전단(front)과 후단(rear) 양쪽에서 모두 삽입과 삭제가 가능한 자료구조

 

 

덱의 추상 자료형

 

데이터 : 전단과 후단을 통한 접근을 허용하는 요소들의 모음

 

연산

- isEmpty() : 덱이 비어있으면 True를 아니면 False를 반환한다.

- isFull() : 덱이 가득 차 있으면 True를 아니면 False를 반환한다.

- addFront(e) : 맨 앞(전단)에 새로운 요소 e를 추가한다.

- deleteFront() : 맨 앞(전단)의 요소를 꺼내서 반환한다.

- getFront() : 맨 앞(전단)의 요소를 꺼내지 않고 반환한다.

- addRear(e) : 맨 뒤(후단)에 새로운 요소 e를 추가한다.

- deleteRear() : 맨 뒤(후단)의 요소를 꺼내서 반환한다.

- getRear() : 맨 뒤(후단)의 요소를 꺼내지 않고 반환한다.

 

원형 큐를 상속한 원형 덱 클래스

 

from CircularQueue import *

class CircularDeque(CircularQueue) :
    def __init__(self, capacity - 10) :
        super().__init__(capacity)
        
        # isEmpty(), isFull()
        
    def addRear(self, item):
        self.enqueue(item)
        
    def deleteFront(self):
        return self.dequeue()
        
    def getFront(self):
        return self.peek()
        
    def addFront(self, item):
        if not self.isFull():
            self.array[self.front]=item
            self.front=(self.front - 1 + self.capactiy) % self.capacity
            
    def deleteRear(self):
        if not self.isEmpty():
            item = self.array[self.rear];
            self.rear = (self.rear - 1 + self.capacity) % self.capacity
            return item
        else: pass
        
    def getRear(self):
        if not self.isEmpty():
            return self.array[self.rear]
        else: pass

 

우선 순위 큐란? (트리 자료구조 이용 x)

 

큐에서 우선순위의 개념을 추가한 자료구조이다.

모든 데이터가 우선순위를 가지고, 입력 순서와 상관없이 높은 데이터가 먼저 출력된다.

 

우선 순위 큐의 추상 자료형

 

데이터 : 우선순위를 가진 요소들의 모음

 

연산

- isEmpty() : 우선순위 큐가 비어있으면 True를 아니면 False를 반환한다.

- isFull() : 우선순위 큐가 가득 차 있으면 True를 아니면 False를 반환한다.

- enqueue(e) : 우선순위를 가진 e를 삽입한다.

- dequeue() : 가장 우선순위가 높은 요소를 꺼내서 반환한다.

- peek() : 가장 우선순위가 높은 요소를 삭제하지 않고 반환한다.

 

정렬되지 않은 배열을 이용한 우선순위 큐 클래스

 

class PriorityQueue :
	def __init__(self, capacity = 10 ):
        self.capacity = capacity
        self.array = [None] * capacity
        self.size = 0
        
    def isEmpty(self) : return self.size == 0
    
    def isFull(self) : return self.size == self.capacity
    
    def enqueue(self, e):
        if not self.isFull():
            self.array[self.size] = e
            self.size += 1
            
    def findMaxIndex(self):
        if self.isEmpty(): return -1
        highest = 0
        for i in range(1, self.size) :
            if self.array[i] > self.array[highest] :
                highest = 1
        return highest
        
    def dequeue(self): 
        highest = self.findMaxIndex()
        if highest != -1:
            self.size -= 1
            self.array[highest], self.array[self.size] = \
                self.array[self.size], self.array[highest]
            return self.array[self.size]
            
    def peek(self):
        highest = self.findMaxIndex()
        if highest != -1:
            return self.array[height]
            
    def __str__(self):
        return str(self.array[0:self.size])