[자료구조] 큐 - 선형 큐, 원형 큐, 덱

728x90

 

 

 

🙆‍♂️선형 큐

---

"""
선형큐
"""
MAX_LQSIZE = 10
class LQueue:
    def __init__(self):
        self.items=[]
    def display(self):
        for item in self.items:
            print(f'{item} =>',end = " ")
        print()
    def full(self):
        return len(self.items)==MAX_LQSIZE
    def emt(self):
        return len(self.items)==0
    def enqueue(self,item):
        if self.full():
            print("It is Full!")
        else:
            self.items.append(item)
    def dequeue(self):
        if not self.emt():
            return self.items.pop(0)
        else:
            print("It is Empty!")

 

🙋‍♂️원형 큐

---

"""
원형 큐 클래스 CQueue
def emt : 큐에 값이 없다면 True를 반환 있다면 False를 반환
def full : 큐가 포화상태라면 True를 반환 아니라면 False를 반환
def clear : 큐 초기화
def enqueue : 포화상태가 아니면서 알파벳 값(ch)만 추가
def dequeue : 공백상태가 아니라면 최전단값 반환하고 제거
def peek : 큐의 최전단값 반환
def size : 큐의 길이 반환
def display : 현재 큐 상태 출력
"""
MAX_SIZE = 100
class CQueue:
    def __init__(self):
        self.front=0
        self.rear=0
        self.items=[None] * MAX_SIZE
    def emt(self):
        return self.front==self.rear
    def full(self):
        return self.front == (self.rear+1)%MAX_SIZE
    def clear(self):
        self.front = self.rear
        
    """
    enqueue(self,ch) : 입력
    1. 포화상태 검사
    2. rear 한칸 뒤로 이동
    3. rear 맨뒤에 값 입력
    """
    def enqueue(self,ch):
        if not self.full():
            self.rear = (self.rear+1)%MAX_SIZE
            self.items[self.rear] = ch
            
    """
    dequeue(self) : 출력
    1. 공백상태인지 검사
    2. front 한 칸 앞으로 이동
    3. 삭제된 값 반환
    """
    def dequeue(self):
        if not self.emt():
            self.front = (self.front+1)%MAX_SIZE
            return self.items[self.front]
    def peek(self):
        if not self.emt():
            return self.items[(self.front+1)%MAX_SIZE]
    def size(self):
        return abs(self.rear - self.front)
    def display(self):
        output = []
        if self.front < self.rear:
            output = self.items[self.front+1 : self.rear+1]
        else:
            output = self.items[self.front+1 : MAX_SIZE] + self.items[0:self.rear+1]            
        print(output)

 

 

🙋‍♂️원형 덱

---

"""
원형 덱 클래스 CDeque
"""

#원형 큐를 상속
class CDeque(CQueue):
    def __init__(self):
        super().__init__()
    
    #CQueue의 enqueue와 같음
    def addRear(self,item):
        self.enqueue(item)
        
    #CQueue의 dequeue와 같음
    def deleteFront(self):
        return self.dequeue()
    
    #CQueue의 peek과 같음.
    def getFront(self):
        return self.peek()
    
    """
    addFront(self,item) : 전단에서 입력
    1. 포화상태 확인
    2. front가 가리키는 곳에 값 입력
    3. front - 1을 해주는데
    만약 음수가되면 MAX_SIZE - 1로 변경
    """
    def addFront(self,item):
        if not self.full():
            self.items[self.front]=item
            self.front=self.front-1
            if self.front<0:
                self.front=MAX_SIZE - 1
                
    """
    deleteRear(self) : 후단에서 출력
    1. 공백상태 확인
    2. rear가 가리키고 있는 값 출력
    3. rear - 1을 해주는데
    만약 음수가 된다면 MAX_SIZE - 1로 변경
    4. 삭제 값 반환
    """
    def deleteRear(self):
        if not self.emt():
            item = self.items[self.rear]
            self.rear=self.rear-1
            if self.raer < 0 :
                self.rear = MAX_SIZE - 1
            return item
    def getRear(self):
        return self.items[self.rear]

위의 원형 큐 코드를 상속받아 만든 원형 덱이다.

 

🙋‍♂️ 우선순위 큐

---

"""
우선순위 큐
"""

class PQueue:
    def __init__(self):
        self.items = []
    def emt(self):
        return len(self.items)==0
    def size(self):
        return len(self.items)
    def enqueue(self, item):
        self.items.append(item)
    def dequeue(self):
        if not self.emt():
            maxV = max(self.items)
            return self.items.pop(self.items.index(maxV))

간단한 우선순위 큐 모델

(값을 우선순위라 생각하고 접근한 것)