[Data Structure / Algorithms] Dequeue

주제: Double-ended Queue

---

특징

• Dequeue(덱)은 양쪽에서 넣고 빼고가 가능한 특이한 큐를 의미합니다.
• 데이터를 앞뒤 양쪽에서 삽입하거나 제거할 수 있습니다.
• 덱은 주로 스케줄링 작업을 수행할 때 사용되며, 특히 우선순위를 조정해야 할 때 유용합니다.

  • 과거에 추가된 데이터의 우선순위를 높이기 위해서는 해당 데이터를 앞쪽에서 제거할 수 있어야 합니다. 이는 스택의 구조에서는 불가능합니다.
  • 최근에 추가된 데이터에 높은 우선순위를 부여하고 싶을 때도, 기존의 큐 구조에서는 이를 수행하기 어렵습니다.
  • 이러한 조건들을 만족시킬 수 있는 자료 구조는 덱 뿐입니다.

구현

enum Direction { 
	case front
	case back 
}

protocol Deque { 
	associatedtype Element
	var isEmpty: Bool { get }
	func peek(from direction: Direction ) -> Element?
	mutating func enqueue(_ element: Element, to direction: Direction) -> Bool 
	mutating func dequeue(from direction: Direction) -> Element?
}

class DequeDoubleLinkedList<Element>: Deque { 
	public var list = Array<Element>()
	
	public init() { } 
	
	var isEmpty: Bool { 
		list.isEmpty
	}
	
	func peek(from direction: Direction) -> Element? { 
		swtich direction { 
			case .front: 
				return list.first
			case .back: 
				return list.last
		}
	}
	
	func enqueue(_ element: Element, to direction: Direction) -> Bool { 
		switch { 
			case .front: 
				list.insert(element, at: 0)
			case .back: 
				list.append(element)
		}
		return true
	}
	
	func dequeue(from direction: Direction) -> Element? { 
		let element: Element?
		switch direction { 
			case .front: 
				guard list.first != nil else { return nil }
				element = list.removeFirst()
			case .back: 
				guard list.last != nil else { return nil }
				element = list.removeLast()
		}
		return element
	}
}

출처(참고문헌)

• https://www.kodeco.com/books/data-structures-algorithms-in-swift/v4.0/chapters/9-queue-challenges
• https://gusdnd852.tistory.com/242#recentComments

제가 학습한 내용을 요약하여 정리한 것입니다. 내용에 오류가 있을 수 있으며, 어떠한 피드백도 감사히 받겠습니다.

감사합니다.