[자료구조/Swift] 덱(Dequeue)

Swift로 직접 자료구조 구현하기 - 덱

✅ 간단하게 알아보는 덱

- 스택과 큐의 연산을 모두 가지고 있는 자료구조이다.

- 앞, 뒤에서 삽입, 삭제 모두 가능한 자료구조

 

1) 뼈대 잡기 (더블 스택을 사용한 큐와 동일)

struct Dequeue<T> {
  var input = [T]()
  var output = [T]()
  
  var isEmpty : Bool {
      return input.isEmpty && output.isEmpty
  }
  var size: Int {
      return input.count + output.count
  }
  
  var first: T? {
    if isEmpty {
      return nil
    }
    return output.isEmpty ? input.first! : output.last!
  }
  
  var last: T? {
    if isEmpty {
      return nil
    }
    return input.isEmpty ? output.first! : input.last!
  }

 

2) 메소드 추가

- appendLeft() : 왼쪽으로 삽입 (기존의 큐의 enqueue 연산)

- popRight() : 오른쪽 삭제 (기존의 큐의 dequeue 연산)

---- 여기까지는 기존 더블스택 큐와 동일하다. (참고)

- appendRight() : 오른쪽 삽입

- popLeft() : 왼쪽 삭제

  mutating func appendLeft(_ element: T) { //기존 큐의 enqueue
    input.append(element)
  }
  
  mutating func popRight() -> T? { //기존 큐의 dequeue
    if output.isEmpty {
        output = input.reversed() //output에 reverse한 배열 넣고 input 비우기
        input.removeAll()
    }
    return output.popLast() //없으면 nil 반환
  }

  mutating func appendRight(_ element: T) {
    output.append(element) //output에 추가해줌
  }

  mutating func popLeft() -> T? {
    if input.isEmpty {
        input = output.reversed()
        output.removeAll()
    }
    return input.popLast() //없으면 nil 반환
  }

 

 

 

전체코드 : https://github.com/yurrrri/Swift_DataStructure/blob/main/dequeue.swift

GitHub - yurrrri/Swift_DataStructure: Swift 알고리즘을 공부하다가 STL이 없어 직접 구현한다,,