Algorithm & Data Structure - Queue(1)

Queue

큐는 스택과 마찬가지로 자료구조에 대해 얘기하면 빠지지 않는 대표적인 자료구조로 선형 구조의 자료구조이다. 그러나 스택과 반대로 FIFO(First In First Out)의 선입선출의 특징을 가지고 있다. 선입선출이라는 것은 편의점 등에서 알바를 해보았으면 알 수 있겠지만 먼저 들어온 것이 먼저 나간다는 뜻으로 놀이기구 줄을 생각하면 쉽다. 놀이기구 줄은(싱글 라인이나 예약은 제외하고..) 먼저 온 사람이 먼저 들어가서 놀이기구를 타고 나오는 구조이므로 FIFO라고 할 수 있다.

큐의 기본 연산

큐는 enqueue / dequeue를 기본적으로 수행하며 enqueue는 스택의 가장 마지막에 데이터 원소를 추가하는 것, dequeue는 스택의 가장 앞에서 데이터 원소를 제거하며 반환하는 것이다.

Q.enqueue(A) # A
Q.enqueue(B) # A -> B
r1 = Q.dequeue() # return A / B
Q.enqueue(C) # B -> C

위의 코드와 같이 데이터 입출력을 할 수 있다.

큐의 구현

큐의 추상적 자료구조를 구현하기 위한 방법으로는 두가지 방법이 있는데

• 배열을 이용한 구현
• 연결 리스트(양방향)를 이용한 구현

있다. 우선 스택에서와 마찬가지로 큐의 연산들을 정의하고 구현해보도록 하겠다.

큐의 연산

• size(): 현재 큐에 들어있는 데이터 원소의 수
• isEmpty(): 현재 큐가 비어있는지 여부
• enqueue(x): 데이터 원소 x를 큐의 가장 마지막에 추가
• dequeue(): 큐의 가장 앞 데이터 원소를 제거하면서 반환
• peek(): 큐의 가장 앞 데이터 원소를 제거하지 않으면서 반환

의 연산이 있다.

배열로 구현한 큐

class ArrayQueue:
    def __init__(self):
    	self.data = []
        
    def size(self):
    	return len(self.data)
        
    def isEmpty(self):
    	return self.size() == 0
        
    def enqueue(self, item):
    	self.data.append(item)
        
    def dequeue(self):
    	return self.data.pop(0)
    
    def peek(self):
    	return self.data[0]

과 같이 구현할 수 있고, pop으로 dequeue시에 계속 0번 인덱스의 값을 제거해주므로 비교적 간단하게 구현할 수 있었다.

배열로 구현한 큐의 연산 복잡도는 다음과 같다.

양방향 연결 리스트로 구현한 큐

class Node:
    def __init__(self, item):
    	self.data = item
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
    	self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.tail.next = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.nodeCount = 0
    
    def getLength(self):
    	return self.nodeCount
    
    def getAt(self, pos):
    	if pos < 1 or pos > self.nodeCount:
        	return None
        if pos > self.nodeCount // 2:
            i = self.nodeCount + 1
            curr = self.tail
            while i > pos:
            	curr = curr.prev
                i -= 1
        else:
            i = 0
            curr = self.head
            while i < pos:
            	curr = curr.next
                i += 1
        return curr
    
    def insertAfter(self, prev, newNode):
    	next = prev.next
        next.prev = newNode
        prev.next = newNode
        newNode.next = next
        newNode.prev = prev
        self.nodeCount += 1
    
    def insertAt(self, pos, newNode):
    	if pos < 1 or pos > self.nodeCount+1:
        	return False
        prev = self.getAt(pos-1)
        return self.insertAfter(prev, newNode)
    
    def popAfter(self, prev):
    	curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data
    
    def popAt(self, pos):
    	if pos < 1 or pos > self.nodeCount:
        	raise IndexError()
        prev = self.getAt(pos-1)
        return popAfter(prev)


class LinkedListQueue:
	def __init__(self):
        self.data = DoublyLinkedList()
    
    def size(self):
    	return self.data.nodeCount
    
    def isEmpty(self):
    	return self.size() == 0
    
    def enqueue(self, item):
    	node = Node(item)
        self.data.insertAt(self.size()+1, node)
    
    def dequeue(self):
    	return self.data.popAt(1)
    
    def peek(self):
    	return self.getAt(1).data

와 같이 구현할 수 있다. 양방향 연결 리스트에 대한 간단한 복습 차원에서 모두 작성하긴 했으나 자세한 내용은 전 포스트를 참고하도록 하자.

연결 리스트로 구현한 큐의 연산 복잡도 같은 경우엔 배열로 구현한 것과 거의 동일하나 dequeue 부분을 O(1)로 개선할 수 있는데, popAt(1)로 항상 고정이므로 큐 구현을 위해 연결 리스트의 popAt 부분에서 popAfter를 사용하지 않고 바로 prev를 head로 생각하고 접근한다면 가능할 것이다.

from pythonds.basic.queue import Queue

역시나 파이썬이 기본적으로 큐를 제공하므로 그냥 임포트해서 사용할 수 있다.

정리

이번에는 그냥 큐에 대해 알아보았으나 다음에는 큐를 활용하는 환형 큐에 대해 이야기해보겠다. 가능하다면 관련된 최대한 간단한 예제 알고리즘 문제를 가져와서 풀어보도록 하겠다.