[Swift] Data Structure Circle Deque 자료구조 원형 덱

dbguswls030/Argorithm

---

원형 덱의 예

덱은 큐를 응용하여 전단(front)과 후단(rear)에서 삽입(add), 삭제(delete)가 모두 이루어진다. 선형 덱에서 배열을 원형으로 생각하면 원형 덱으로 구현할 수 있다. 원형 덱의 경우에는 front와 rear의 값이 배열의 끝인 MAX_DEQUE_SIZE-1에 도달하면 다음 증가되는 값이 0으로 되도록 한다.

---

구현에 필요한 요소

initDeque() : 덱을 초기화 함

add_front(e) : 주어진 요소 e를 덱의 맨 앞에 추가한다.

delete_front() : 전단 요소를 삭제하고 반환한다.

add_rear(e) : 주어진 요소 e를 덱의 맨 뒤에 추가한다.

delete_rear() : 전단 요소를 삭제하지 않고 반환한다.

get_front() : 전단 욯소를 삭제하지 않고 반환한다.

get_rear() : 후단 요소를 삭제하지 않고 반환한다.

is_empty() : 공백 상태이면 True를 아니면 False 반환

is_full() : 덱이 가득 차 있으면 True를 아니면 False를 반환

size() : 덱의 모든 요소들의 개수를 반환

 

---

import Foundation



func initDeque(){
    front = -1
    rear = -1
    circleDeque.removeAll()
}
func addFront(_ x: Int){
    if isFull()==false{
        if isEmpty()==true{
            circleDeque.append(x)
            front = (front+1) % MAX_DEQUE_SIZE
            rear = (rear+1) % MAX_DEQUE_SIZE
        }
        else{
            front = (front-1+MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE
            circleDeque.insert(x, at: front)
            rear = (rear+1) % MAX_DEQUE_SIZE
        }
    }
}
func addRear(_ x: Int){
    if isFull() == false{
        rear=(rear+1) % MAX_DEQUE_SIZE
        circleDeque.append(x)
    }
    
}
func getFront() -> Int{
    if isEmpty() == false{
        return circleDeque[front]
    }else {
        return -1
    }
}
func getRear() -> Int{
    if isEmpty() == false{
        return circleDeque[rear]
    }else{
        return -1
    }
}
func deleteFront() -> Int{
    if isEmpty() == false{
        front = (front-1+circleDeque.count-1) % circleDeque.count
        return circleDeque.remove(at: front)
    }
    else{
        return -1
    }
}
func deleteRear()->Int{
    if isEmpty() == false{
        rear = (rear-1) % MAX_DEQUE_SIZE
        return circleDeque.remove(at: rear)
    }else{
        return -1
    }
}
func isEmpty() -> Bool{
    if circleDeque.isEmpty{
        print("deque is empty")
        return true
    }else{
        return false
    }
}
func isFull() -> Bool{
    if front == (rear+1)%MAX_DEQUE_SIZE{
        print("deque is full")
        return true
    }else{
        return false
    }
}
func size() -> Int{
    return circleDeque.count
}

let MAX_DEQUE_SIZE = 10
var circleDeque:Array<Int> = []
var front = 0
var rear = 0




addFront(1)
print(circleDeque)
addRear(9)
print(circleDeque)
addFront(2)
print(circleDeque)
addRear(10)
print(circleDeque)
print(deleteRear())
print(circleDeque)
print(deleteRear())
print(circleDeque)
print(deleteFront())
print(circleDeque)
addRear(20)
print(circleDeque)
print(deleteFront())
print(circleDeque)

4