[JS|자료구조] 자바스크립트(javascript)의 Stack(스택) 알아보기

 

 

- Stack이란?

LIFO (Last In First Out)
가장 나중에 들어온 데이터가 가장 먼저 나가는 형태.
즉, 한 방향으로만 데이터를 넣고 뺄 수 있다.

 

한 방향으로만 데이터를 삽입/삭제할 수 있기에 그 복잡도 또한 O(1)이다.

새로 삽입한 데이터의 주소를 top라는 변수에 넣고, 삭제할 때 top가 가리키는 주소에 저장되어있는 변수를 삭제하면 된다.

 

---

- Stack의 ADT 연산 정의

0. Stack의 기본 구조

function stack(array = new Array()) {
  this.arr = array
  this.top = 0
}

1. Stack의 데이터 삽입

stack.prototype.push = function (item) {
  return (this.arr[this.top++] = item)
}

2. Stack의 데이터 삭제

stack.prototype.pop = function () {
  if (this.top <= 0) return null
  return this.arr[--this.top]
}

3. Stack이 비어있는지 확인

stack.prototype.isEmpty = function () {
  return stack.length === 0
}

4. Stack 전체 코드 

function stack(array = new Array()) {
  this.arr = array
  this.top = 0
}

stack.prototype.push = function (item) {
  return (this.arr[this.top++] = item)
}

stack.prototype.pop = function () {
  if (this.top <= 0) return null
  return this.arr[--this.top]
}

stack.prototype.isEmpty = function () {
  return stack.length === 0
}

let stack = new stack()
stack.push(1)
stack.push(2)
console.log(stack.pop())
stack.push(3)
console.log(stack.pop())
console.log(stack.isEmpty())
console.log(stack.pop())
console.log(stack.isEmpty())