원형 큐 (Circular Queue)

원형 큐는 선입선출(FIFO) 방식은 그대로 유지하되, 선형 큐의 공간 낭비 문제를 해결하기 위해 고안된 큐이다.
말 그대로 큐의 끝과 시작이 이어져 원형처럼 동작하는 구조

파이썬으로 구현한 코드는 아래와 같다

class CircularQueue:
    arr : list
    f : int
    r : int
    size : int
    def __init__(self,size):
        self.arr = [0]*size
        self.f = 0
        self.r = 0
        self.size = size
    def isFull(self):
        if (self.r + 1) % self.size == self.f: return True
        return False
    def isEmpty(self):
        return self.f == self.r
    def dequeue(self):
        if self.isEmpty():
            return "아무것도 없습니다."
        self.f = (self.f + 1) % self.size
        p = self.arr[self.f]
        self.arr[self.f] = None
        return p
    def enqueue(self, a):
        if not self.isFull():
            self.r = (self.r + 1) % self.size
            self.arr[self.r] = a
        else:
            print("자리가 없습니다.")

메서드 종류

• enqueue: 값을 집어넣는 메서드
• dequeue: 값을 빼내는 메서드
• isFull: 꽉 찼는지 확인하는 메서드
• isEmpty: 비었는지 확인하는 메서드

특징

• 선형 큐의 공간 낭비 문제 해결
• 다만, 식이 조금 복잡해짐

덱 (Deque)

덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조이다.

스택과 큐의 장점을 모두 가지고 있어 유연하게 사용 가능합니다.

특징

• 앞(front)에서도 삽입/삭제 가능
• 뒤(rear)에서도 삽입/삭제 가능
• 원형 큐에서 조금만 수정하면 구현 가능

파이썬으로 구현한 코드는 아래와 같다

class Deque:
    arr : list
    f : int
    r : int
    size : int
    def __init__(self,size):
        self.arr = [0]*size
        self.f = 0
        self.r = 0
        self.size = size
    def isFull(self):
        if (self.r + 1) % self.size == self.f: return True
        return False
    def isEmpty(self):
        return self.f == self.r
    def delete_front(self): #s
        if self.isEmpty():
            return "아무것도 없습니다."
        p = self.arr[self.f]
        self.arr[self.f] = None
        self.f = (self.f + 1) % self.size
        return p
    def delete_rear(self):
        if self.isEmpty():
            return "아무것도 없습니다."
        self.r = (self.r - 1 + self.size) % self.size
        p = self.arr[self.r]
        self.arr[self.r] = None
        return p
    def add_rear(self, a): #s
        if not self.isFull():
            self.arr[self.r] = a
            self.r = (self.r + 1) % self.size
        else:
            print("자리가 없습니다.")
    def add_front(self, a):
        if not self.isFull():
            self.f = (self.f - 1 + self.size) % self.size
            self.arr[self.f] = a
        else:
            print("자리가 없습니다.")

메서드 종류

• add_front(a) : 앞에서 a을 삽입
• add_rear(a) : 뒤에서 a을 삽입
• delete_front() : 앞에서 값을 삭제하고 반환
• delete_rear() : 뒤에서 값을 삭제하고 반환
• isFull() : 꽉 찼는지 확인
• isEmpty() : 비어있는지 확인

예시

• 웹 브라우저의 앞으로 가기/뒤로 가기