JavaScript 스택

스택(Stack)

 자바스크립트에서 스택을 사용하는 방법은 2가지가 있다. 첫 번째로 배열을 사용하는 것이고 두 번째로 연결 리스트로 구현하는 방법이 있다. 자바스크립트 배열은 동적으로 추가가 가능하고 이미 push, pop 기능이 구현되어 있기 때문에 그대로 사용하면 된다. 따라서 연결 리스트로 스택을 구현해 본다.

  연결 리스트로 구현하면서 헷갈렸던 점은 노드의 추가 방향이 그림으로 나타냈을 때 오른쪽으로 추가되는 것이 아니라 왼쪽으로 추가되는 것이라는 점이다.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

 연결 리스트를 사용해야하기 때문에 노드 클래스가 필요하다. 매개변수로 전달받은 값을 사용해서 노드를 생성한다. 다음을 가리키는 포인터는 null로 초기화한다.

class Stack {
  constructor() {
    this.top = null;
    this.stackSize = 0;
  }
}

  Stack 클래스를 만들고 연결 리스트에서 tail에 해당하는 top 포인터를 사용한다. 또한 스택의 사이즈를 구하기 위해 stackSize 변수를 추가한다.

push(targetValue)

Stack.prototype.push = function (newValue) {
  const newNode = new Node(newValue);
  newNode.next = this.top;
  this.top = newNode;
  this.stackSize += 1;
}

Stack.prototype.push2 = (newValue) => {
  const newNode = new Node(newValue);
  newNode.next = this.top;
  this.top = newNode;
  this.stackSize += 1;
}

 push함수는 newValue값을 갖는 새로운 노드를 생성한다. 새로운 노드의 다음은 현재 this.top이 된다. 그리고 스택 사이즈를 하나 증가시킨다. (왼쪽으로 추가시킨다고 생가가현 이해가 빠르다.)

 push2함수는 arrow function을 사용해서 구현했었다. 하지만 내부에서 stackSize 값을 NaN으로 얻어오는 문제와 next가 undefined로 출력되는 에러가 있었다.
arrow function을 사용할 때 this에 주의해야 한다고 배웠었는데 부주의하게 생각하고 만들었다가 발견한 버그였다.

arrow function 내부에서 this가 어떻게 동작하는지 더 찾아봐야 한다.

pop()

Stack.prototype.pop = function() {
  const value = this.top.value;
  this.top = this.top.next;
  this.stackSize -= 1;
  return value;
}

 pop함수는 현재 top노드의 값을 리턴한다. top.value 값을 value에 저장하고 top을 현재 top의 다음 노드로 이동시킨다.(오른쪽으로 이동) stackSize는 1감소시킨다.

size()

Stack.prototype.size = function() {
  return this.stackSize;
}

 size 함수는 간단하게 stackSize값을 리턴한다.

완성본

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.top = null;
    this.stackSize = 0;
  }
}

Stack.prototype.push = function (newValue) {
  const newNode = new Node(newValue);
  newNode.next = this.top;
  this.top = newNode;
  this.stackSize += 1;
};

Stack.prototype.push2 = (value) => {
  const newNode = new Node(value);
  newNode.next = this.top;
  this.top = newNode;
  this.stackSize += 1;
  console.log(this);
};

Stack.prototype.pop = function () {
  const value = this.top.value;
  this.top = this.top.next;
  this.stackSize -= 1;
  return value;
};

Stack.prototype.size = function () {
  return this.stackSize;
};

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.pop();
stack.push(3);
stack.push(4);
console.log(stack.size());