[JS] 선형 자료구조 스택(Stack) 구현하기

스택(Stack)이란?

가장 늦게 들어간 데이터가 가장 먼저 나오는 LIFO(Last In First Out) 기반의 선형 자료구조이다.

---

구현 메서드(method)

데이터 전체 획득

Stack.getBuffer()

비어 있는지 확인

Stack.isEmpty()

데이터 추가/삭제

Stack.push()/Stack.pop()

마지막 데이터 조회

Stack.peek()

사이즈 확인

Stack.size()

데이터 위치 확인

Stack.indexOf()

존재 여부 확인

Stack.includes()

---

Windows 단축키인 Ctrl + z 실행취소(undo) 기능도 스택(Stack) 기반으로 구현되었고

웹 브라우저에서 이전 페이지로 이동하는 원리도 스택(Stack)이라고 볼 수 있다

---

스택 구현 - getBuffer(), isEmpty()

// 생성자 함수
function Stack(array) {
  this.array = array ? array : [];
}

// getBuffer() 구현 함수
Stack.prototype.getBuffer = function () {
  return this.array.slice();
};

// isEmpty() 구현 함수
Stack.prototype.isEmpty = function () {
  return this.array.length === 0;
};

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

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

console.log(stack.isEmpty()); // false

 

스택 구현 - push(), pop(), peek(), size()

// push() 구현 함수
Stack.prototype.push = function (element) {
  return this.array.push(element);
};

// pop() 구현 함수
Stack.prototype.pop = function () {
  return this.array.pop();
};

// peek() 구현 함수
Stack.prototype.peek = function () {
  return this.array[this.array.length - 1];
};

// size() 구현 함수
Stack.prototype.size = function () {
  return this.array.length;
};

let stack = new Stack([1, 2]);
console.log(stack); // Stack { array: [ 1, 2 ] }

stack.push(3);
console.log(stack); // Stack { array: [ 1, 2, 3 ] }

console.log(stack.pop()); // 3
console.log(stack); // Stack { array: [ 1, 2 ] }

console.log(stack.peek()); // 2

console.log(stack.size()); // 2

 

스택 구현 - indexOf(), includes()

// indexOf() 구현 함수
Stack.prototype.indexOf = function (element, position = 0) {
  // return this.array.indexOf(element, position);
  for (let i = position; i < this.array.length; i++) {
    if (element === this.array[i]) return i;
  }
  return -1;
};

// includes() 구현 함수
Stack.prototype.includes = function (element, position = 0) {
  // return this.array.includes(element);
  for (let i = position; i < this.array.length; i++) {
    if (element === this.array[i]) return true;
  }
  return false;
};

let stack = new Stack([1, 2, 3]);

console.log(stack.indexOf(1)); // 0
console.log(stack.indexOf(2)); // 1
console.log(stack.indexOf(1, 2)); // -1

console.log(stack.includes(3)); // true
console.log(stack.includes(4)); // false