🔍 Stack

데이터를 순서대로 쌓는 자료구조로, 입출력이 하나의 방향으로 이루어지는 제한적 접근이 특징이다. 따라서 가장 먼저 들어간 데이터는 가장 나중에 나올 수 있고(FILO), 반대로 가장 나중에 들어간 데이터는 가장 먼저 나올 수 있다(LIFO).

이 때, Stack에 데이터를 넣는 것을 push, 꺼내는 것을 pop이라고 한다.

Stack의 특징을 정리하자면, 아래와 같다.

• LIFO(Last In First Out)

• 데이터가 아무리 많아도 하나씩 넣고 뺄 수 있다.
  (한꺼번에 여러개 X)

• 하나의 입출력 방향

• 저장되는 데이터는 유한하며 정적이다.

• 스택의 크기는 제한되어있다.(스택 오버플로 자주 발생)

✔ 기본 코드

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0; // Stack의 최상단을 가리키는 포인터 변수(0으로 초기화)
  }
  
  // stack의 size
  // this.top = Stack이 쌓일 때마다 ++,
  // this.top = Stack에 새롭게 추가될 요소의 index,(top의 값은 size와 동일)
  size() {
    return this.top;
  }


  // stack에 element(데이터)추가
  // key : 새롭게 추가될 element의 index를 나타내는 this.top
  // value : element
  // key와 value를 storage에 할당하고, this.top은 다음 인덱스를 가리키게 하여 새로운 element에 대비
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
	
	// 가장 나중에 추가된 데이터가 가장 먼저 나와야 한다.
  // stack에서 element를 제거한 뒤, 해당 element를 return.
  // 만약 size가 0이라면 아무것도 return 하지 않는다.
  // top-1(가장 나중에 추가된 데이터가 있는 index)로 최상단을 설정한 후 변수에 저장하고, Stack에서 제거.
  // 하나를 제거했으니 top-1.
  pop() {
    if (this.size() <= 0) {
      return;
    }

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

// 입출력
const stack = new Stack();

stack.size(); // 0
for(let i = 1; i < 10; i++) {
  	stack.push(i);
}
stack.pop(); // 9
stack.pop(); // 8
stack.size(); // 7
stack.push(8);
stack.size(); // 8
...

👀 실사용 예시

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

브라우저에서 Stack이 사용될 때, 아래의 순서를 거친다.

1. 새로운 페이지 접속 -> 현재 페이지를 prev Stack에 보관

2. 뒤로가기 버튼 -> 현재 페이지를 Next Stack에 보관, 현재 페이지로 Prev Stack에 가장 나중에 보관된 페이지를 가져옴

3. 앞으로 가기 버튼 -> Next Stack의 가장 마지막으로 보관된 페이지를 가져옴, 현재 페이지를 Prev Stack에 보관

구현 코드

function browserStack(actions, start) {
  
  // start가 string이 아니면 return false
  if(typeof start !== 'string'){
    return false;
  }
  
  // 뒤로 가기, 현재, 앞으로 가기 stack의 변수 설정
  let prev = [];
  let now = start;
  let next = [];

  // actions 배열을 전부 탐색
  for(let action of actions){
    // 만약 actions의 요소가 -1이고(뒤로가기), prevStack의 길이가 0이 아닐 때(이전으로 돌아가는 페이지가 있다면)
    if(action === -1 && prev[0]){
      // 지금 보고 있는 페이지를 next에 넣고
      next.push(now);
      // prev에서 가장 마지막 요소 꺼내와서 현재 페이지에 할당
      now = prev.pop()
      
      //만약 actions의 요소가 1이고(앞으로 가기), nextStack의 길이가 0이 아닐 때(다음으로 넘어가는 페이지가 있다면)
    }else if(action === 1 && next[0]){
      // 지금 보고 있는 페이지를 prev에 넣고
    	prev.push(now);
      // next에서 가장 마지막 요소 꺼내와서 현재 페이지에 할당
    	now = next.pop();
     
      // 만약 actions 배열의 요소가 string이라면 (새로운 페이지라면)
    }else if(typeof action === 'string'){
      // 내가 보고있던 페이지는 prev에 넣어주기
      prev.push(now);
      // action으로 들어온 페이지가 현재 페이지가 됨
      now = action
      // 새로운 페이지는 앞으로 갈 수 없으므로 next 스택을 비워야 함
      next = [];
    }
  }
  // 배열에 stack의 변수를 순서대로 담아서 return
  return [prev, now, next]
}

// 입출력
const actions = ["B", "C", -1, "D", "A", -1, 1, -1, -1];
const start = "A";
const output = browserStack(actions, start);

console.log(output); // [["A"], "B", ["A", "D"]]

const actions2 = ["B", -1, "B", "A", "C", -1, -1, "D", -1, 1, "E", -1, -1, 1];
const start2 = "A";
const output2 = browserStack(actions2, start2);

console.log(output2); // [["A", "B"], "D", ["E"]]

Reference: 코드스테이츠