자료구조 스택과 큐 (2)- 큐

"큐(Queue)"
“큐”(Queue)는 삽입-삭제 연산이 양 끝에서 각각 수행되는 자료구조이다.

큐(Queue)는,
앞서 다룬 스택(Stack)과 다르게
삽입-삭제 연산이 동일한 자리(Top)에서 일어나지 않는다.

각각 front 자리와 rear 자리가 존재하며,
삽입 연산은 rear에서,
삭제 연산은 front 자리에서 일어난다.

SLL로 구현하였을때
삽입 연산은 단순히 끝(rear)자리에서의 레퍼런스 연결-
삭제 연산은 앞(front)자리에서의 레퍼런스 갱신으로 연산이 일어난다.
(python list는 append(),pop(0)이용.)

따라서 큐 자료구조는
FIFO(First In First Out)구조에 따라 연산이 발생한다.
=가장 먼저 삽입한 항목이 가장 먼저 삭제된다.
간단하게 이해하려면,빨대 구조를 생각하면 된다.(스택은 주머니..?)

python에서 코드를 작성하였으며,
앞서 스택과 같이 python의 리스트나 SLL로 구현이 가능하다.

동일하게 python의 리스트를 사용하여 구현하였을땐,
add/remove 연산은 각각 O(1)시간이 소요된다.
그러나,
동적 크기 변화 때문에 시간복잡도가 O(N)으로 증가한다(리스트 전체복사)
반면,SLL을 이용하면 삽입 삭제 연산의 시간복잡도가 O(1)이다.
(순차적 방문이 필요없기에,front-rear 자리에서의 연산만 일어나면 된다.)

CODE:

우선,SLL로 구현한 큐이다.

#소스코드

class Node:
    def __init__(self,item,n): #노드 생성자
        self.item = item
        self.next = n

def add(item): #삽입 연산
    global size #전역변수 size,front,rear(Queue는 rear 삽입,front 삭제 연산)
    global front 
    global rear 
    new_node = Node(item,None) #새 노드 객체 생성(item을 가지고 있는)
    if size == 0: #빈 큐 일떄)
        front = new_node #새 노드 객체가 front(rear 삽입)
    else: #빈 큐가 아닐떄)
        rear.next = new_node #맨 마지막 rear 자리에 삽입
    rear = new_node #rear = 새로 추가한 노드(FIFO,First In First Out), "rear 재지정"
    size += 1

def remove(): #삭제 연산
    global size #전역변수 size,front,rear(Queue는 rear 삽입,front 삭제 연산)
    global front
    global rear
    if size != 0: #빈 큐가 아닐때)
        fitem = front.item #front 자리, 맨 앞에 있는 항목의 객체를 지정
        front = front.next #SLL 삭제처럼 레퍼런스 갱신 = 삭제
        size -= 1
        if size == 0: #삭제 연산 후 빈 큐가 되었을 때)
            rear = None #rear = None
        return fitem #삭제한 항목 리턴

def print_q(): #큐 출력
    p = front 
    print('front: ', end='')
    while p: #큐 끝까지 출력
        if p.next != None: #front의 다음 객체가 None이 아닐때)
            print(p.item,'->  ', end='')
        else: #다음 객체가 rear 일 때
            print(p.item, end = '')
        p = p.next #다음 객체 이동
    print(' : rear')

#실행코드

front = None #초기화 => front, rear 둘 다 초기화 필요
rear = None 
size = 0

add('apple')
add('orange')
add('cherry')
add('pear')
print('사과, 오렌지, 체리, 배 삽입 후: \t', end='') # rear => pear > cherry > orange > apple <= front
print_q()
remove()
print('remove한 후:\t\t', end='') #remove, front 부터 삭제(FIFO) / rear => pear > cherry > orange <= front
print_q()
remove()
print('remove한 후:\t\t', end='') # rear => pear > cherry <= front
print_q()
add('grape')
print('포도 삽입 후:\t\t', end='') #add, rear 에서 삽입(FIFO),스택과 다르게 삭제 삽입 연산하는 곳이 다름.
# rear => grape > pear > cherry <= front
print_q()

#실행결과

#사과, 오렌지, 체리, 배 삽입 후:         front: apple ->  orange ->  cherry ->  pear : rear
#remove한 후:            front: orange ->  cherry ->  pear : rear
#remove한 후:            front: cherry ->  pear : rear
#포도 삽입 후:           front: cherry ->  pear ->  grape : rear

다음으로,
python 리스트를 활용한 큐 자료구조이다.

#소스코드

def add(item):
    q.append (item)

def remove():
    if len(q) != 0:
        item = q.pop(0)
        return item

def print_q():
    print('front =>  ', end='')
    for i in range(len(q)):
        print('{!s:<8}'.format(q[i]), end='') #맨 앞부터 항목들을 차례로 출력
        #특이한건 .format의 이용인데,
        # {!s = String으로 형변환:conversion, :<8은 8칸을 사용하면서 왼쪽으로 정렬한다는 뜻.}
        #형식을 지정해주는 출력문...알아두자
    print(' <- rear')

#실행코드

q = []

add('apple')
add('orange')
add('cherry')
add('pear')
print('사과, 오렌지, 체리, 배 삽입 후: \t', end='') # rear => pear > cherry > orange > apple <= front
print_q()
remove()
print('remove한 후:\t\t', end='') #remove, front 부터 삭제(FIFO) / rear => pear > cherry > orange <= front
print_q()
remove()
print('remove한 후:\t\t', end='') # rear => pear > cherry <= front
print_q()
add('grape')
print('포도 삽입 후:\t\t', end='') #add, rear 에서 삽입(FIFO),스택과 다르게 삭제 삽입 연산하는 곳이 다름.
# rear => grape > pear > cherry <= front
print_q()

#실행결과는 SLL과 같다.

큐 자료구조는,
CPU의 Task Scheduling,
네트워크 프린터
실시간 시스템의 interrupt 처리,
다양한 이벤트 구동방식 컴퓨터 시뮬레이션,
콜 센터의 전화 서비스 처리에 사용되며,
BFS(Breath-First-Search),
이진트리의 레벨순회에 사용된다.
(다양하게 사용된다!)

스택 자료구조의 구조 차이점과,
시간복잡도의 동일성을 기억하자.

• 자료구조
• 이론