[Swift] Deque(덱) 구현 && BOJ 10866 -더블 스택(Double Stack)

덱 구현

import Foundation

struct Deque<T> {
  private var dequeueStack: [T] = []
  private var enqueueStack: [T] = []
  
  var isempty: Bool {
    return dequeueStack.isEmpty && enqueueStack.isEmpty
  }
  
  var peek: T? {
    return !dequeueStack.isEmpty ? dequeueStack.last : enqueueStack.first
  }
  
  @discardableResult
  mutating func push_back(_ element: T) {
  enqueueStack.append(element)  
  }

  @discardableResult
  mutating func push_front(_ element: T) {
  dequeueStack.append(element)    
  }

  

  mutating func pop_back() -> T? {
    if enqueueStack.isEmpty {
      enqueueStack = dequeueStack.reversed()
      dequeueStack.removeAll()
    }
    return enqueueStack.popLast()
  }

  
  mutating func pop_front() -> T? {
    if dequeueStack.isEmpty {
      dequeueStack = enqueueStack.reversed()
      enqueueStack.removeAll()
    }
    return dequeueStack.popLast()
  }

  var count: Int {
        return enqueueStack.count + dequeueStack.count
    }
    
    var isEmpty: Bool {
        return enqueueStack.isEmpty && dequeueStack.isEmpty
    }

  var front:T? {
    if(self.isempty) {
      return nil
    }
    else if(dequeueStack.isEmpty) {
      return enqueueStack.first
    }
    else {
      return dequeueStack.last
    }
  }

  var back:T? {
    if(self.isempty) {
      return nil
    }
    else if(enqueueStack.isEmpty) {
      return dequeueStack.first
    }
    else {
      return enqueueStack.last
    }
  }
  
}

var example:Deque<Int> = Deque()
example.push_back(1)
example.push_back(2)
example.push_back(3)
example.push_back(4)
example.push_back(5)

print(example.pop_front())
print(example.pop_back())
print(example.back)
print(example.front)

구현한 방식은 Queue를 구현할 때 썼던 더블 스택을 활용하였다.

만약 pop_back을 하게된다면 위 사진과 반대로 dequeue 스택에만 값이 있을 시 enqueue 스택으로 뒤집어서 넘겨주고 enqueue 스택의 마지막 값을 pop해준다.
즉, 위사진과 정반대로 진행되는 것이다.

BOJ 10866

import Foundation

struct Deque<T> {
  private var dequeueStack: [T] = []
  private var enqueueStack: [T] = []
  
  var isempty: Bool {
    return dequeueStack.isEmpty && enqueueStack.isEmpty
  }
  
  var peek: T? {
    return !dequeueStack.isEmpty ? dequeueStack.last : enqueueStack.first
  }
  
  @discardableResult
  mutating func push_back(_ element: T) {
  enqueueStack.append(element)  
  }

  @discardableResult
  mutating func push_front(_ element: T) {
  dequeueStack.append(element)    
  }

  

  mutating func pop_back() -> T? {
    if enqueueStack.isEmpty {
      enqueueStack = dequeueStack.reversed()
      dequeueStack.removeAll()
    }
    return enqueueStack.popLast()
  }

  
  mutating func pop_front() -> T? {
    if dequeueStack.isEmpty {
      dequeueStack = enqueueStack.reversed()
      enqueueStack.removeAll()
    }
    return dequeueStack.popLast()
  }

  var count: Int {
        return enqueueStack.count + dequeueStack.count
    }
    
    var isEmpty: Bool {
        return enqueueStack.isEmpty && dequeueStack.isEmpty
    }

  var front:T? {
    if(self.isempty) {
      return nil
    }
    else if(dequeueStack.isEmpty) {
      return enqueueStack.first
    }
    else {
      return dequeueStack.last
    }
  }

  var back:T? {
    if(self.isempty) {
      return nil
    }
    else if(enqueueStack.isEmpty) {
      return dequeueStack.first
    }
    else {
      return enqueueStack.last
    }
  }
  
}

var example:Deque<Int> = Deque()
var n:Int = Int(readLine()!)!

for _ in 1...n {
  var input = readLine()!.split(separator:" ").map {String($0)}
  switch input[0] {
      case "push_front":
          example.push_front(Int(input[1])!)
      case "push_back":
          example.push_back(Int(input[1])!)
      case "pop_front":
          if example.isempty {
              print(-1)
          }else{
              print(example.pop_front()!)
          }
      case "pop_back":
          if example.isempty {
              print(-1)
          } else {
              print(example.pop_back()!)   
          }
      case "size":
          print(example.count)
      case "empty" :
          if example.isempty {
              print(1)
          }else {
              print(0)
          }
      case "front" :
          if example.isempty {
              print(-1)
          } else {
              print((example.front)!)
          }
      default:
          if example.isempty {
              print(-1)
          } else{
              print((example.back)!)
          }
  }
}