알고리즘 3주차 - 큐(Queue)

Keywords : FIFO, 추상 자료형, 선형 큐, 연결 큐

 

큐 (Queue)

• 삽입, 삭제 위치가 제한된 유한 순서 리스트
• FIFO : 선입선출
• 중간에서 삽입, 삭제 불가능
• 스택과의 차이 : 양 쪽에서 삽입, 삭제 이루어짐 (양 끝 front & rear 로 구성)
• 삽입 : enQueue
• 삭제 : deQueue

추상 자료형 큐 (ADT Queue) 예시

• 선형 큐
  • createQueue() : front = rear = -1 => 공백 큐 생성
  • enQueue(Q, A) : front = -1, rear = 0
  • enQueue(Q, B) : front = -1, rear = 1
  • deQueue(Q) : front = 0, rear = 1
  • enQueue(Q, C) : front = 0, rear = 2
  • deQueue(Q) : front = 1, rear = 2
  • deQueue(Q) : front = 2, rear = 2
• 연결 큐
  • createQueue() : front = rear = null
  • enQueue : new 노드 생성, 공백일 경우 front = rear = new / 나머지는 rear.link = new, rear = new
  • deQueue : old = front, item = front.data, front = front.link, return(delete) old

# 연결리스트를 이용한 큐 구현
class Node:
    def __init__(self, item, n):
        self.item = item
        self.next = n

def enqueue(item):
    global size
    global front
    global rear
    new_node = Node(item, None)
    if size == 0:
        front = new_node
    else:
        rear.next = new_node
    rear = new_node
    size += 1

def dequeue():
    global size
    global front
    global rear
    if size != 0:
        fitem = front.item
        front = front.next
        size -= 1
        if size == 0:
            rear = None
        return fitem

def print_q():
    p = front
    print('Front : ', end='')
    while p:
        if p.next != None:
            print(p.item, '-> ', end='')
        else:
            print(p.item, end='')
        p = p.next
    print(' : rear')

front = None
rear = None
size = 0

enqueue('apple')
enqueue('orange')
enqueue('cherry')
print('After Enqueue : ', end='')
print_q()
print('Dequeue : ', dequeue())
print('After Dequeue : ', end='')
print_q()

# 결과
After Enqueue : Front : apple -> orange -> cherry : rear
Dequeue :  apple
After Dequeue : Front : orange -> cherry : rear