[선형] 13. 데크

in 자료구조 on 선형




1. 데크 (Deque)

데크

  • Double-Ended Queue 의 약자로, 삽입과 삭제가 양쪽 끝에서 모두 발생할 수 있는 선형 자료 구조
  • 데이터 전체 획득 / 비어있는지 확인 : Deque.getBuffer(), Deque.isEmpty()
  • 데이터 추가 / 삭제 : Deque.pushFront(), Deque.popFront(), Deque.pushBack(), Deque.popBack()
  • 젓번째 & 끝 데이터 반환 / 사이즈 / 전체 삭제 : Deque.front(), Deque.back(), Deque.size(), Deque.clear()



2. 구현하기

생성자, getBuffer(), isEmpty()

// Deque() : 초기 속성값 설정을 위한 생성자 함수
function Deque(array = []){
    this.array = array
}

// getBuffer() : 객체 내 데이터 셋 반환
Deque.prototype.getBuffer = function(){
    return this.array.slice()
}

// isEmpty(): 데이터 비어 있는지 확인
Deque.prototype.isEmpty = function(){
    return this.array.length === 0
}

let dq = new Deque([1,2,3])
console.log(dq) //Deque { array: [ 1, 2, 3 ] }

let data = dq.getBuffer()
console.log(data === dq.array) //false
console.log(data) //[ 1, 2, 3 ]

console.log(dq.isEmpty()) //false
console.log(Object.getOwnPropertyDescriptors(Deque.prototype))



pushFront(), popFront(), pushBack(), popBack()

// pushFront(): 앞쪽 데이터 추가
Deque.prototype.pushFront = function(element){
    return this.array.unshift(element)
}

// popFront(): 앞쪽 데이터 삭제
Deque.prototype.popFront = function(){
    return this.array.shift()
}

// pushBack(): 뒤쪽 데이터 추가
Deque.prototype.pushBack = function(element){
    return this.array.push(element)
}

// popBack(): 뒤쪽 데이터 삭제
Deque.prototype.popBack = function(){
    return this.array.pop()
}
let dq = new Deque([1,2,3])
console.log(dq) //Deque { array: [ 1, 2, 3 ] }

dq.pushFront(0)
dq.pushBack(4)
console.log(dq) //Deque { array: [ 0, 1, 2, 3, 4 ] }

console.log(dq.popFront()) //0
dq.popBack()

console.log(dq) //Deque { array: [ 1, 2, 3 ] }



front(), back(), size()

// front(): 가장 첫 데이터 반환
Deque.prototype.front = function () {
  return this.array.length === 0 ? undefined : this.array[0];
};

// back(): 가장 끝 데이터 반환
Deque.prototype.back = function (elment) {
  return this.array.length === 0
    ? undefined
    : this.array[this.array.length - 1];
};

// size() : 큐 내 데이터 개수 확인
Deque.prototype.size = function () {
  return this.array.length;
};

let dq = new Deque([1, 2, 3]);
console.log(dq); //Deque { array: [ 1, 2, 3 ] }

console.log(dq.front()); //1
console.log(dq.back()); //3
console.log(dq.size()); //3



3. 문제 - 데트 만들기

자연수를 저장하는 데크를 만들고자 한다. 입력으로 주어진 명령어를 처리할 수 있는 프로그램을 작성하시오.
명령어의 종류는 총 8가지로 아래와 같으며, 명령에 따라 반환된 값을 result 배열에 넣도록 한다.

  • push_front X : 자연수 X를 앞쪽에 넣는다.
  • push_back X : 자연수 X를 뒤쪽에 넣는다.
  • pop_front : 앞쪽에 있는 값을 제거하고 그 값을 반환한다. 만약 값이 없다면 -1을 반환한다.
  • pop_back : 뒤쪽에 있는 값을 제거하고 그 값을 반환한다. 만약 값이 없다면 -1을 반환한다.
  • empty : 큐가 비어 있다면 1, 아니면 0을 반환한다.
  • size : 큐에 들어있는 자연수 개수를 반환한다.
  • front : 앞쪽에 값이 있다면 값을, 없다면 -1을 반환
  • back : 큐 뒤쪽에 값이 있다면 값을, 없다면 -1을 반환


function Deque(array = []) {
  this.array = array;
}

Deque.prototype.pushFront = function (element) {
  return this.array.unshift(element);
};

Deque.prototype.pushBack = function (element) {
  return this.array.push(element);
};

Deque.prototype.popFront = function () {
  let ret = this.array.shift()
  return ret === undefined ? -1 : ret
};

Deque.prototype.popBack = function () {
  let ret = this.array.pop()
  return ret === undefined ? -1 : ret
};

Deque.prototype.empty = function () {
  return this.array.length === 0 ? 1 : 0;
};

Deque.prototype.size = function () {
  return this.array.length;
};

Deque.prototype.front = function () {
  return this.array.length == 0 ? -1 : this.array[0]
};

Deque.prototype.back = function () {
  return this.array.length == 0 ? -1 : this.array[this.array.length-1]
};

function answer(cmds) {
  let result = [];
  let deque = new Deque();
  for (let i = 0; i < cmds.length; i++) {
    let cmd = cmds[i].split(" ")[0]
    switch (cmd) {
      case "pop_front":
        result.push(deque.popFront());
        break;
      case "pop_back":
        result.push(deque.popBack());
        break;
      case "push_front":
        deque.pushFront(Number(cmds[i].split(" ")[1]));
        break;
      case "push_back":
        deque.pushBack(Number(cmds[i].split(" ")[1]));
        break;
      case "empty":
        result.push(deque.empty());
        break;
      case "size":
        result.push(deque.size());
        break;
      case "front":
        result.push(deque.front());
        break;
      case "back":
        result.push(deque.back());
        break;
    }
  }

  // 코드 구현 종료 영역
  return result;
}

let input = [
  ["push_back 1", "push_front 2", "pop_front", "pop_back", "pop_front"],
  [
    "push_back 3",
    "push_front 4",
    "push_back 5",
    "push_front 6",
    "front",
    "back",
    "pop_front",
    "size",
    "empty",
  ],
  [
    "push_back 7",
    "push_front 8",
    "front",
    "back",
    "size",
    "empty",
    "pop_front",
    "pop_back",
    "pop_front",
    "size",
    "empty",
    "pop_back",
    "push_front 9",
    "empty",
    "front",
  ],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1}`);
  console.log(answer(input[i]));
}

// LinkedList.prototype.printNode = function () {
//   process.stdout.write("head -> ");

//   if (this.length != 0) {
//     process.stdout.write(`${this.head.data} -> `);
//     for (let node = this.head.next; node != this.head; node = node.next) {
//       process.stdout.write(`${node.data} -> `);
//     }
//   }

//   console.log(null);
// };