[자료구조] 덱(Deque) | javascript
[자료구조] 덱(Deque) | javascript
📋 [ 자료구조 ] 시리즈 몰아보기 (4)
📚 덱(Deque)
Stack과 Queue를 합친 자료구조로 양방향에서 데이터의 입출력이 가능한 자료형이다. 실제 메모리에서 앞, 뒤를 구분하지는 않지만 편의상 deque의 앞, 뒤 모두 자료의 입출력이 가능하다고 표현한다. 구현해야할 기능은 다음과 같다.
push_head(item): deque의head에item을삽입한다.push_tail(item): deque의tail에item을삽입한다.pop_head():head의 원소를제거한다.pop_tail():tail의 원소를제거한다.print_head():head의 원소를출력한다.print_tail():tail의 원소를출력한다.rotate_left(n): deque을반시계방향으로n회 회전한다.rotate_right(n): deque을시계방향으로n회 회전한다.isEmpty(): deque이 비어있는지 조사한다.clear(): deque을 초기화한다.length(): deque의 크기를 출력한다.
js에서는 배열을 이용하여 간단히 구현 가능하다.
🖥️ 소스코드
| 1 | const Deque = () => { |
| 2 | let store = []; |
| 3 | |
| 4 | return { |
| 5 | // push |
| 6 | push_head(item) { |
| 7 | store = [item, ...store]; |
| 8 | }, |
| 9 | push_tail(item) { |
| 10 | store.push(item); |
| 11 | }, |
| 12 | // pop |
| 13 | pop_head() { |
| 14 | store.shift(); |
| 15 | }, |
| 16 | pop_tail() { |
| 17 | store.pop(); |
| 18 | }, |
| 19 | |
| 20 | print_head() { |
| 21 | return store[0]; |
| 22 | }, |
| 23 | print_tail() { |
| 24 | return store[store.length - 1]; |
| 25 | }, |
| 26 | // rotate |
| 27 | rotate_left(n) { |
| 28 | if (!this.isEmpty()) { |
| 29 | let temp = null; |
| 30 | for (let i=0; i<n; i++) { |
| 31 | temp = store[0]; |
| 32 | store.shift(); |
| 33 | store.push(temp); |
| 34 | } |
| 35 | } else { |
| 36 | console.log("deque is Empty"); |
| 37 | } |
| 38 | }, |
| 39 | rotate_right(n) { |
| 40 | if (!this.isEmpty()) { |
| 41 | let temp = null; |
| 42 | for (let i=0; i<n; i++) { |
| 43 | temp = store[store.length - 1]; |
| 44 | store.pop(); |
| 45 | store = [temp, ...store] |
| 46 | } |
| 47 | } else { |
| 48 | console.log("deque is Empty"); |
| 49 | } |
| 50 | }, |
| 51 | // else |
| 52 | isEmpty() { |
| 53 | return store.length === 0 ? true : false; |
| 54 | }, |
| 55 | clear() { |
| 56 | store.splice(0); |
| 57 | }, |
| 58 | length() { |
| 59 | return store.length; |
| 60 | } |
| 61 | }; |
| 62 | }; |
# 자료구조
# JS
# javascript
# 덱
# Deque
👨💻 관련 포스트
[자료구조] 스택(Stack) | javascript
[자료구조] 스택(Stack) | javascript
javascript로 이해하는 자료구조 [스택(stack)] : 스택(stack)은 데이터를 입력할 수 있는 선형 자료형으로 선입후출의 구조를 가지며 ctrl+z와 같은 기능에서 요구되는 자료형이다. javascript에서는 배열을 이용해 손쉽게 구현할 수 있다.
2023-04-20
[자료구조] 큐(Queue) | javascript
[자료구조] 큐(Queue) | javascript
javascript로 이해하는 자료구조 [큐(queue)] : 큐(queue)는 데이터를 입력할 수 있는 선형 자료형으로 선입선출의 구조를 가진다. 버퍼링과 같은 기능에서 요구되는 자료형이다. javascript에서는 배열을 이용해 손쉽게 구현할 수 있다.
2023-04-20
[자료구조] 연결리스트(linked_list) | javascript
[자료구조] 연결리스트(linked_list) | javascript
javascript로 이해하는 자료구조 [연결리스트(linked-list)] : 연결리스트(linked-list)는 리스트의 일종으로 노드(node)와 데이터가 포인터(pointer)를 가지고 한 줄로 이어져있는 형태를 띈다. 자료의 추가 및 삭제 시간복잡도가 O(1)이나 다른 자료형보다 저장공간을 많이 차지하는 단점이 있다.
2023-04-25
💡 로그인 하지 않아도 댓글을 등록할 수 있습니다!