[자료구조] 스택 (Stack) - 정의, 특징, 그리고 자바스크립트로 구현하기

스택(Stack)

Stack의 정의

• 쌓다, 쌓이다, 포개지다
• 데이터(data)를 순서대로 쌓는 자료구조

Stack의 특징

• 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근
• LIFO (Last In First Out) = FILO (First In Last Out)
• 먼저 들어간 것이 가장 나중에 나오는 자료구조

일상생활의 예시

다섯 대의 자동차가 순서대로 좁은 골목을 지나고 있습니다. 좁은 골목에 진입한 차량은 곧 맞이할 미래를 모르고 있지만, 이 골목의 끝은 막혀 있습니다. 첫 번째 자동차는 이 골목을 통과하기 위해 직진했고, 나머지 자동차도 앞 자동차의 꽁무니를 따라 직진했습니다. 그러나 첫 번째 차량이 막다른 길을 맞이했습니다. 마지막으로 들어온 다섯번 째 자동차가 먼저 후진하여 나와야 하는 상황이 되어버린 겁니다.

• 골목: 자료구조 Stack
• 자동차: 데이터(data)

 

Stack의 실사용 예제

브라우저의 뒤로 가기, 앞으로 가기 기능 구현

브라우저에서 Stack이 사용될 때의 순서

1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관
2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때에는 ,현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져옴
3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때에는, Next Stack의 가장 마지막으로 보관된 페이지를 가져옴
4. 마지막으로 현재 페이지를 Prev Stack에 보관

 

 

---

 

1. class 로 사용자 정의 데이터 타입을 만들어 Stack 구현하기

 JavaScript로 사용자 정의 데이터 타입을 만들어 내는 여러 방법 중에서, ES6 문법 중 하나인 class 키워드로 사용자 정의 데이터 타입을 만들고, Stack과 Queue의 데이터 타입을 정의합니다. 이렇게 생성한 사용자 정의 데이터 타입은 Stack과 Queue를 Array와 object처럼 사용할 수 있습니다.

사용자 정의 데이터 타입으로 Stack과 Queue를 정의하면, new 키워드를 통해 새로운 객체(인스턴스)를 만들 수 있습니다. 그리고 생성한 인스턴스를 통해 다양한 메서드를 사용할 수 있습니다.

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화
  }

  // 스택의 사이즈(크기) 반환
  size() {
    return this.top;
  }

  // 스택에 데이터를 추가
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
	
  // 가장 나중에 추가된 데이터가 가장 먼저 추출
  pop() {
    // 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않도록
    if (this.size() <= 0) {
      return;
    }

    const result = this.storage[this.top - 1];
    delete this.storage[this.top - 1];
    this.top -= 1;
    
    return result;
  }
}

 

 

2. Javascript의 Array를 활용하여 Stack 사용하기

JavaScript에는 Array라는 훌륭한 자료형이 이미 있습니다. Array를 사용하면 사용자 정의 데이터 타입을 구현하는 시간을 절약할 수 있고, 몇 가지의 메서드로 Stack과 Queue처럼 동작하도록 사용할 수 있습니다.

자료구조로써 Stack과 Queue의 특성만 이해한다면, Array를 활용하여 Stack과 Queue로 사용할 수 있습니다.
다시 말해 자료구조는 자료(데이터)를 다루는 구조 그 자체를 뜻하며, 구현하는 방식에는 제약이 없습니다.

// const array = new Array() 미리 정의된 Array 객체를 사용합니다.
const stack = [];

stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.push(3); // [1, 2, 3]
stack.push(4); // [1, 2, 3, 4]
stack.push(5); // [1, 2, 3, 4, 5]

console.log(stack); // [1, 2, 3, 4, 5]

stack.pop(); // [1, 2, 3, 4]
stack.pop(); // [1, 2, 3]

console.log(stack); // [1, 2, 3]

 

 

질문

• Array.prototype에는 Stack, Queue 사용을 위해 어떤 메서드가 존재하나요?
  • Stack: push, pop
  • Queue: push, shift
• 배열로 Stack, Queue를 사용할 때 주의해야 할 사항은 어떤것들이 있나요?
  • Stack: push, pop, empty, size 메소드를 만든다
    • emty() : 저장소가 비어있는지 확인하는 메소드
    • size() : 현재 저장소에 저장되어있는 데이터의 수를 반환하는 메소드
  • Queue: push, shift, empty, size 메소드를 만든다
• 배열로 Stack을 사용할 때 push, pop 이외에 필요한 메서드를 어떻게 구현할 수 있나요?
  • Stack의 size() : Array.length
  • Stack의 empty() : Array.length === 0
• 배열로 Queue를 사용할 때 push, shift 이외에 필요한 메서드를 어떻게 구현할 수 있나요?
• JavaScript의 배열과 Stack, Queue는 어떤 차이가 있나요?
  • javascript의 배열: 배열의 요소를 순서에 상관없이 메소드(push, pop, shift, unshift)를 사용해서 넣었다가 뺐다 할 수 있음
  • Stack, Queue: 요소를 다룰 때 정해진 순서를 지켜야 함