스택 (Stack)

Stack 🙂

스택(Stack)은 맨 처음 들어간 것이 가장 마지막에 나오는 자료구조를 말합니다. 이러한 구조를 Last In, First Out(LIFO) 또는 First In, Last Out(FILO) 구조라 부릅니다. 스택은 다음에 다뤄 볼 큐(Queue)와 함께 소프트웨어 분야에서 정말 중요한 구조입니다. 프로그램들이 이용하는 자동 메모리 영역도 스택 구조로 되어 있고, 대부분의 네트워크 프로토콜도 스택을 기반으로 구성되어 있습니다.

링크드 리스트를 만들 때는 노드를 추가하고 제거하는 과정에 별다른 이름이 없었지만, 스택과 큐는 명칭들이 정해져 있습니다. 데이터를 스택에 추가하는 작업을 push라 하며, 데이터를 제거하는 작업을 pop이라 합니다. 기본적으로 스택은 배열 또는 링크드 리스트를 이용해 구현할 수 있는데, 본문에서는 자바스크립트 배열을 통해 간단하게 구현하겠습니다.

스택 프로토타입

function Stack(size) {
  this.stack = [];
  this.size = size;
  this.top = -1;
}

const stack = new Stack(5);

자바스크립트는 배열 자체적으로 스택과 관련된 메소드(push, pop)를 이미 갖고 있습니다. 두 메소드를 사용하면 간단하게 스택을 만들 수 있지만, 본문에서는 자료구조 공부를 위해 포인터 역할을 하는 top 멤버 변수를 추가로 만들어 구현했습니다. 그리고 size는 초기 스택의 크기이며, 미리 지정한 크기만큼만 데이터를 추가할 수 있도록 했습니다.

데이터 추가

Stack.prototype.push = function (data) {
  if (this.isFull()) throw new Error('Stack is full!');

  this.stack[++this.top] = data;
};

Stack.prototype.isFull = function () {
  return this.size - 1 === this.top ? true : false;
};

초기의 top은 데이터가 아무 것도 없기에, -1 값을 가지고 있습니다. 그래서 데이터 추가를 할 때, 이 값을 먼저 증가시킨 다음에 넣는 식으로 구현할 수 있습니다. 그리고 스택이 꽉 차 있는지의 여부를 isFull이라는 유틸 메소드를 만들어 받아오게 했으며, 단순한 계산만 하므로 삼항 조건 연산(Ternary Operator)을 이용해 구현했습니다.

데이터 제거

Stack.prototype.pop = function () {
  if (this.isEmpty()) throw new Error('Stack is empty!');

  return this.stack[this.top--];
};

Stack.prototype.isEmpty = function () {
  return this.top === -1 ? true : false;
};

pop 메소드는 데이터를 스택의 위에서부터 제거하면서 호출한 쪽(Caller)으로 값을 반환해 줍니다. 데이터 추가와 동일하게 isEmpty라는 유틸 메소드를 추가 구현하여, 스택이 비어있는지 여부를 먼저 체크했습니다.

스택 비우기

Stack.prototype.clear = function () {
  while (this.top !== -1) {
    this.pop();
  }
};

스택을 비우는 방법은 top이 -1이 될 때까지, pop을 반복하면 됩니다.

References 📝

본문의 내용은 GeeksforGeeks의 자료구조 튜토리얼을 참고해 작성했습니다 ❤️