큐 (Queue)

큐 (Queue)

• 한쪽 긑에서 삽입이 일어나고 그 반대쪽 끝에서 삭제가 일어나는 순서 리스트
  • 새로운 원소가 삽입되는 끝 - 리어 (rear)
  • 원소가 삭제되는 끝 - 프런트 (front)
• 선입선출 (FIFO, First-In-First-Out) 리스트

1차원 배열 queue[] 이용

• 삭제 (pop) : queue[0]에 있는 원소 제거
  • 삭제할 때마다 나머지 원소들을 왼쪽으로 이동해야함
  • 큐가 n개의 원소를 가질 때, 삭제 시 O(n) 시간이 걸림
• 삽입 (push) : 배열 크기 조절 시간을 제외하면 O(1) 시간이 걸림

class Queue:
    # queue 변수
    queue = []
    front  = 0
    rear = 0
    capacity = 10

    # queue 함수
    def __init__(self, queueCapacity = 10):
        self.capacity = queueCapacity
        self.front = self.rear = 0

    def isEmpty(self):
        if len(self.queue) == 0:
            return True
        else:
            return False

    def Front(self):
        return self.queue[0]

    def Push(self, item):
        if(self.capacity > self.rear + 1):
            self.queue.append(item)
            self.rear += 1
        else:
            self.capacity += 10
            self.queue.append(item)
            self.rear += 1

    def Pop(self):
        if(self.isEmpty() == False):
            self.queue.pop(self.front)

큐의 첫번째 원소를 queue[front]로 표현한 큐

• 변수 front를 사용하여 큐의 첫번째 위치를 항상 유지
• 원소의 삭제를 O(1) 시간에 수행하기 위한 방법
• 큐의 원소 : queue[front], ... , queue[rear]

# 변수 front를 사용하여 큐의 첫번째 위치를 항상 유지
# pop : queue[front]에 있는 원소 제거

class Queue:

    # queue 변수
    queue = []
    front  = 0
    rear = 0
    capacity = 10
    
    # queue 함수
    def __init__(self, queueCapacity = 10):
        self.capacity = queueCapacity
        self.front = self.rear = 0

    def isEmpty(self):
        if len(self.queue) == 0:
            return True
        else:
            return False

    def Front(self):
        if(self.isEmpty() == False):
            return (self.queue[(self.front + 1)] % self.capacity)

    def Rear(self):
        if(self.isEmpty() == False):
            return self.queue[self.rear]

    def Push(self, item):
        if(self.capacity > self.rear + 1):
            self.queue.append(item)
            self.rear += 1
        else:
            self.capacity += 10
            self.queue.append(item)
            self.rear += 1

    def Pop(self):
        if(self.isEmpty() == False):
            self.front += 1

원형 큐 (queue)

• 변수 front는 큐에서 첫 원소의 위치보다 시계반대방향으로 하나 앞 위치를 가리킴
• 변수 rear는 큐에서 마지막 원소의 위치를 가리킴

class Queue:

    # queue 변수
    queue = []
    front  = 0
    rear = 0
    capacity = 10

    # queue 함수
    def __init__(self, queueCapacity = 10):
        self.capacity = queueCapacity
        self.front = self.rear = 0
        self.queue.append(0)

    def isEmpty(self):
        return self.front == self.rear

    def Front(self):
        if(self.isEmpty() == False):
            return (self.queue[(self.front + 1)] % self.capacity)

    def Rear(self):
        if(self.isEmpty() == False):
            return self.queue[self.rear]

    def Push(self, item):
        if(self.rear == self.capacity - 1):
            self.rear = 0
        self.queue.append(item)
        self.rear += 1

    def Pop(self):
        if(self.isEmpty() == False):
            self.front += 1