일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- C
- web
- LoB
- 두근두근 자료구조
- 정렬 알고리즘
- Java
- War Game
- ftz
- 파일 시스템
- Stack
- windosws wbcs
- SWiFT
- pwnable.kr
- 자료구조
- 백준
- OSI
- 큐
- 재귀
- System
- c언어
- 스택
- HTML
- 암호수학
- level13
- 미로 탐색 알고리즘
- 시간복잡도
- 파이썬
- ftz level13
- windosw 문자열
- PHP
Archives
- Today
- Total
나의 기록, 현진록
[Swift] Data Structure Circle Deque 자료구조 원형 덱 본문
Programming/Algorithm & Data Structure
[Swift] Data Structure Circle Deque 자료구조 원형 덱
guswlsdk 2021. 6. 30. 10:41반응형
원형 덱의 예
덱은 큐를 응용하여 전단(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)
반응형
'Programming > Algorithm & Data Structure' 카테고리의 다른 글
[Swift] Data Structure/maze search/BFS/queue/미로 탐색/너비우선탐색/큐 (0) | 2021.06.30 |
---|---|
[Swift] Data Structure/maze search/DFS/stack/미로 탐색/깊이우선탐색/스택 (0) | 2021.06.30 |
[Swift] Data Structure Linear Deque 자료구조 선형 덱 (0) | 2021.06.24 |
[python] Data Structure Circle Queue 자료구조 원형 큐 (0) | 2021.06.24 |
[python] Data Structure Linear Queue 자료구조 선형 큐 (0) | 2021.06.23 |