[Data Structure] Queue

"큐"(Queue)는 선형 자료구조로 2가지 Main Operation을 기본적으로 제공하는 ADT이다.

• enqueue(push) : 원소를 추가한다. 
• dequeue(pop) : 가장 처음에 추가된 원소를 제거한다.

 

지난 포스팅에서 다루었던 스택은 프링글스 통과 같이 LIFO로 동작했다. 

반면, 큐는 티켓팅을 위해 줄을 서는 것과 같이 가장 먼저 들어간 원소가 가장 먼저 제거되며, 이를 FIFO라 부른다.

큐 역시 위의 사진과 같이 원소의 삽입과 삭제되는 위치가 정해지기 때문에, Restricted Structure라고도 불린다. 

이렇게 원소가 삽입되는 곳을 tail, rear, back이라 부르며, 

원소가 삭제되는 곳을 head, front라 부른다. 

 

사용

Computer Science에서 큐는 굉장히 많은 곳에서 사용된다. 

대표적으로, CPU Scheduling에서 Task들을 저장하기 위해 사용되고, I/O Resource를 사용하기 위해 대기하는 Task들을 저장하기 위해 사용된다.

또한, 네트워크 분야에선 라우터에서 처리할 패킷을 저장하기 위해 사용된다.

 

iOS분야에선 다양한 이벤트를 Main Run Loop으로 전달하는 이벤트 큐가 있으며, 

GCD에서 DispatchQueue등 많은 곳에서 사용된다.

 

 

구현 

큐에서 제공하는 기능을 우선적으로 프로토콜로 명세해 보면 다음과 같다. 

public protocol Queue {
	associatedtype T
	
	var count: Int { get }
	var isEmpty: Bool { get }
	var top: T? { get }
	
	mutating func enqueue(_ element: T)
	mutating func dequeue() -> T?
}

 

많은 블로그에선 Sequence 혹은 Collection을 채택해 큐를 구현한다. 이를 채택하게 되면 front와 back에서만이 아닌 모든 원소에 접근이 가능하게 된다. 이는 Restricted Structure에 위반된다 생각해 채택하지 않았다. 

 

자세한 구현은 여기에서 확인해볼 수 있다. 

 

Array

이 역시 정적 배열과 동적 배열로 구분할 수 있다. 하지만 컴파일 타임에 큐의 사이즈가 결정 나냐 아니냐라는 차이점밖에 없기 때문에 동적 배열만 구현했다. 

만약 정적 배열 방식으로 구현하고 싶다면 Objective-C의 NSMutableArray를 사용하면 된다.

struct ArrayQueue<T>: Queue {
	private var elements: [T] = []
	
	var count: Int {
		return elements.count
	}
	
	var isEmpty: Bool {
		elements.isEmpty
	}
	
	var top: T? {
		return elements.last
	}
	
	init() { }
}

이후, enqueue와 dequeue를 다음과 같이 구현해주면 된다. 

mutating func enqueue(_ element: T) {
	elements.append(element)
}

@discardableResult
mutating func dequeue() -> T? {
	guard !isEmpty else { return nil }
	
	return elements.removeFirst()
}

하지만, 배열에서 첫번째 원소를 삽입하기 위해선 다음과 같이 빈 공간으로 나머지들을 당겨야 한다.

따라서, 위의 코드의 dequeue는 O(N)이 소요된다.

 

개선

dequeue가 O(1)에 소요될 수 있도록 구현해보자. 

다음과 같이 dequeue가 일어나면, head를 전진시켜서 삭제가 된 것처럼 구현하게 되면 O(1)으로 개선할 수 있다. 

 

이를 위해 추가적으로 head변수도 추가해주고, count, isEmpty 로직도 다음과 같이 수정해 준다. 

struct ArrayQueue<T>: Queue {
	private var elements: [T] = []
	private var head: Int = 0
	
	var count: Int {
		return elements.count - head
	}
	
	var isEmpty: Bool {
		head == elements.count
	}
	...
}

이후 dequeue의 경우에는 head위치의 원소를 리턴하고 head를 1 증가시킨다. 

@discardableResult
mutating func dequeue() -> T? {
	guard !isEmpty else { return nil }
	
	defer { head += 1 }
	return elements[head]
}

 

Circular Queue

위와 같이 구현하게 되면, dequeue가 많이 일어나면 날수록 버려지게 되는 공간이 많아지게 된다. 

따라서, 이를 원형으로 구현하는 방법이다. 

 

우선, 원형 큐를 구현하기 위해선 head와 tail을 가리키는 포인터(혹은 인덱스)가 필요하다. 

초기 상태는 다음과 같이 head와 tail이 같은 공간을 가리킨다. 

 

이후 enqueue는 다음과 같이 tail을 1증가 시켜 원소를 추가하고, 

dequeue는 1증가시켜 원소를 제거한다.

 

 

포화 상태 판별 

큐가 꽉찼다는 것을 어떻게 판별할까?

 

만약 원형 큐에 빈 공간이 없도록 삽입하기 위해선 다음과 같다.

우선, tail의 위치에서 삽입한 후에, tail을 증가시킨다. 

elements[tail] = element

tail = (tail + 1) % capacity

 

다음과 같이 구현하게 되면, 인덱스 11에서 원소를 삽입하고 tail을 증가시키기 때문에, tail과 head가 같아지는 시점에서 포화 상태가 된다. 

하지만, 이는 큐가 비었을 때와 조건이 같기 때문에 서로 구분할 수 없게 되는 문제점이 발생한다. 

 

따라서, 아래와 같이 우선 tail을 1 증가 시키고 원소를 삽입하게 된다. 

tail = (tail + 1) % capacity

elements[tail] = element

tail을 우선적으로 증가시키기 때문에 다음과 같이 하나의 공간을 무조건적으로 비우게 된다. 해당 방법에선 tail + 1이 head와 같은 경우, 포화상태를 가리키며, 비어있는 상태와 구분할 수 있게 된다. 

 

따라서, 원형 큐는 다음과 같이 하나의 head위치에서 처음 공간을 비우게 된다. 

 

Circular Queue 구현

우선적으로, 다음과 같이 원소를 추가해준다. Swift에선 동적 배열만 재공해 컴파일 타임에 원소 사이즈를 결정할 수 없다. 따라서, NSMutableArray를 사용했다. 

struct CircularQueue<T>: Queue {
	private let elements: NSMutableArray

	private let capacity: Int
	private var head: Int = 0
	private var tail: Int = 0
	...
}

 

또한, 앞서 하나의 공간을 비운다고 했기에, 공간을 1만큼 더 추가해 다음과 같이 할당했다. 

init(capacity: Int) {
	self.capacity = capacity + 1
	self.elements = NSMutableArray(capacity: capacity + 1)
}

 

앞서 말한 조건대로 isEmpty와 isFull상태를 정의해 주자. 

var isEmpty: Bool {
	head == tail
}

var isFull: Bool {
	head == (tail + 1) % capacity
}

 

해당 상태에서 원소의 갯수는 다음과 같이 정의할 수 있다. 

var count: Int {
	return (tail - head + capacity) % capacity
}

 

마지막으로 enqueue와 dequeue를 다음과 같이 구현해 주면 된다. 

mutating func enqueue(_ element: T) {
	guard !isFull else {
		print("queue is full")
		return
	}
	
	if isEmpty { elements[tail] = element }
	tail = (tail + 1) % capacity

	elements[tail] = element
}

@discardableResult
mutating func dequeue() -> T? {
	guard !isEmpty else { return nil }
	
	head = (head + 1) % capacity
	
	return elements[head] as? T
}

추가적으로 enqueue에선, 다음과 같은 코드를 볼 수 있는데, 

if isEmpty { elements[tail] = element }

NSMutableArray에서 0번째 인덱스에 어떠한 원소도 삽입하지 않은 경우,

subscript를 통해 접근하게 되면 빈 배열에 접근했다는 런타임 에러가 발생한다.

let arr = NSMutableArray(capacity: 100)
arr[1] // 런타임 에러 발생 

/* 에러 발생 X
arr[0] = 1
arr[1] 
*/

개인적인 생각으로는 메모리 최적화를 위해, 빈공간을 할당하고 있다가 

0번째 인덱스에서 값이 할당된 경우 capacity만큼 메모리 할당을 하는 방식으로 추측한다. 

 

Linked List

다음으로는 연결 리스트로 구현하는 방식이다.

큐에서는 연결 리스트의 마지막에선 삽입만 발생하고, 처음에서만 삭제가 발생한다.

따라서, 이중 연결 리스트가 아닌 간편하게 단순 연결 리스트로 구현이 가능하다. 

final class SimpleLinkedNode<T> {
	var data: T
	var next: SimpleLinkedNode<T>?
	
	// MARK: - Initalizers
	init(data: T, next: SimpleLinkedNode<T>? = nil) {
		self.data = data
		self.next = next
	}
}

 

이후, enqueue와 dequeue는 저번 연결 리스트 포스팅에서 구현했던 pop_front()와 append(_:)메서드를 호출해 주면 된다. 

mutating func enqueue(_ element: T) {
	count += 1
	append(element)
}

@discardableResult
mutating func dequeue() -> T? {
	count = count == 0 ? 0 : count - 1
	return pop_front()
}

 

해당 방법은 컴파일 타임에 사이즈가 결정 나지 않을뿐더러, dequeue로 인한 빈 공간이 발생하지 않는다. 

 

Stack

마지막으로는 스택을 사용해 큐를 구현하는 방법이다. 

다음과 같이 2개의 스택을 선언한다. 

struct DoubleStackQueue<T>: Queue {
	private var inbox = DynamicStack<T>()
	private var outbox = DynamicStack<T>()
	...
}

enqueue가 일어나는 경우는 inbox 스택에 채워넣고,

dequeue가 일어나는 경우는 inbox 스택의 원소를 outbox로 옮긴 후 스택의 pop을 수행하면 된다.

extension DoubleStackQueue {
	/// O(N)
	mutating func enqueue(_ element: T) {
		if inbox.isEmpty {
			while let element = outbox.pop() {
				inbox.push(element)
			}
		}
		
		inbox.push(element)
	}
	
	@discardableResult
	/// O(N)
	mutating func dequeue() -> T? {
		if outbox.isEmpty {
			while let element = inbox.pop() {
				outbox.push(element)
			}
		}
		
		return outbox.pop()
	}
	...
}

 

추가적으로 위 방법에선 dequeue와 enqueue 혹은 top 연산이 모두 O(N)으로 동작한다.

또한, top연산에선 두 스택을 조작해야 하기 때문에, protocol의 명세를 다음과 같이 변경해 주었다.

protocol Queue {
	...
	var top: T? { mutating get }
}

struct DoubleStackQueue<T>: Queue {
	...
	/// O(N)
	var top: T? {
		mutating get { return getTop() }
	}
	...
}

 

References

위키백과 

• Queue (abstract data type)