[ Data Structure ] 🥞 스택(Stack)

📚 스택(Stack)의 개념

스택(Stack)의 어원은 '쌓는다' 이다.
어원에서 짐작할 수 있듯이 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조이다.

주변에서 찾아볼 수 있는 예시로
티슈를 생각해보면
티슈를 만들 때 먼저 넣는 티슈가 가장 아래에 위치한다.

그래서 티슈를 사용할 때는 가장 위에 있는 티슈부터 사용할 수 있게된다.
이렇게 먼저 들어간 것이 마지막에 나오는 규칙을 후입선출 또는 LIFO(Last In First Out)라고한다.

이때 스택에 삽입하는 연산을 push, 꺼내는 연산을 pop이라고 한다.

 

⚙️ 스택(Stack)의 동작 원리

위에서 설명한 스택에 대한 개념을 그림으로 표현하자면 다음과 같다.

 

⚖️ 스택(Stack)의 정의, ADT

스택의 ADT라는 것을 정의해보자
ADT는 우리말로 추상 자료형(abstract data type)이다.

추상 자료형이랑 인터페이스만 있고 실제로 구현은 되지 않은 자료형을 말한다.
일종의 자료형의 설계도라고 생각하면 된다.

그렇다면 스택은 어떤 정의가 필요한 자료냐면

- 스택(Stack)의 ADT

우선 스택에 다음과 같은 연산들을 정의해보자

1. push , 스택에 데이터 삽입
2. pop , 스택에서 데이터 꺼내기
3. isFull , 스택이 가득 찼는지 확인
4. isEmpty , 스택이 비어 있는지 확인
5. top , 최근에 삽입한 데이터의 위치를 참조

 

✨ 스택(Stack)의 동작 구현하기

스택 ADT를 동작들을 구현하자면 다음과 같다.

class Stack {
  _stack = []; // 스택 초기화
  _maxSize = 10; // 스택 최대 크기

  constructor(maxSize) {
    this._maxSize = maxSize; // 스택 최대 크기 설정
  }

  // 스택이 가득 찼는지 확인
  isFull() {
    return this._stack.length === this._maxSize;
  }

  // 스택이 비어 있는지 확인
  isEmpty() {
    return this._stack.length === 0;
  }

  // 스택에 데이터를 추가
  push(item) {
    if (this.isFull()) {
      console.log('스택이 가득 찼다.');
      return;
    }
    this._stack.push(item);
    console.log('데이터가 추가되었다.');
  }

  // 스택에서 데이터를 꺼내기
  pop() {
    if (this.isEmpty()) {
      console.log('스택이 비어 있다.');
      return;
    }
    return this._stack.pop();
  }
}

그런데 JavaScript의 배열은 크기를 동적으로 관리하므로
this.maxSize() 나 this.isFull() 메서드는 사용하지 않고
this.isEmpty() 메서드는 stack.length === 0 으로 검사할 수 있다.

그리고 실질적으로 위에 this.push(), this.pop() 메서드를 구현한 부분을 보면
실제 해당 함수들이 하는 일은 Array.prototype.push(), pop() 메서드를 호출하는 것이 전부라서
굳이 위와 같이 메서드를 구현하지 않아도 되므로
다음과 같이 스택 동작을 구현할 수 있다.

const stack = []; // 스택 초기화

// 스택에 데이터 추가
stack.push(1);
stack.push(2);
stack.push(3);

// 스택에서 데이터 꺼냄
const topElement = stack.pop(); // 3
const nextElement = stack.pop(); // 2

// 스택의 크기를 구함
const stackSize = stack.length; // 1

// topElement : 3
// nextElement : 2

 

🤔 스택(Stack)은 언제 쓸까?

그렇다면 지금까지 위에서 알아본 스택(Stack) 은 언제 사용될까?

🔙 브라우저 뒤로가기

접속했던 웹 사이트의 히스토리들을 차곡 차곡 쌓아놓았다가( push 에 해당 )
뒤로가기를 눌렀을 때 스택에서 바로 이전에 쌓아둔 top인 히스토리를 제거해 가져가는 것이다( pop 에 해당 ).

⏰ Ctrl+Z 되돌리기

사용자의 동작을 스택에 쌓다가( push 에 해당 )
ctrl+z 를 눌러 되돌리기를 하는 순간
스택에서 바로 이전에 쌓아둔 top을 제거해( pop 에 해당 ) 되돌릴 수 있겠다.

 

📝 문제 풀이

그럼 지금까지 학습한 스택(Stack) 의 개념을 활용해서 해당 문제들을 풀어보고
풀이 과정을 각 코드 마다 주석으로 작성하겠다.

💯 : 풀어서 정답인 문제
👀 : 참고해서 풀은 문제
🧪 : 정답을 보고 분석한 문제
 

💯 [ 문제 08 ]. 괄호 짝 맞추기

문제 : 프로그래머스 - 괄호 짝 맞추기

function solution(s) {
  const stack = [];

  for (const c of s) {
    c === '(' && stack.push(c); // '('일 때 stack에 데이터를 push!

    if(c === ')'){ // ')'일 때 
      if(stack.length === 0) return false; // stack에 요소가 없을 경우 처리
      else stack.pop(); // ')'일 때 stack에 pop!
    }               
  }

  // 동작이 끝난 stack이 비어있는지
  return stack.length === 0;
}

console.log(solution('(())()')); // true
console.log(solution('((())()')); // false

 

💯 [ 문제 09 ]. 10진수를 2진수로 변환하기

문제 : 코딩 테스트 합격자 되기 - 자바스크립트 편

function solution(data){  
  const stack = [];

  while(data > 0){
    const num = data % 2; // 10진수를 2로 나눈 나머지 %2 연산값   
    stack.push(num); // stack에 저장
    data = Math.floor(data / 2) // 10진수를 나눈값을 재할당    
  }

  let answer = '';

  // stack에 요소가 있을 때
  while(stack.length) {
    // stack 위에서 부터 pop한 값을 answer에 복합 대입해서 문자열로 나열
    answer += stack.pop();
  }

  return answer;
}

console.log(solution(10)); // 1010
console.log(solution(27)); // 11011
console.log(solution(12345)) // 11000000111001

 

💯 [ 문제 10 ]. 괄호 회전하기

문제 : 프로그래머스 - 괄호 회전하기

function solution(data) {
  data = [...data];

  const score = {
    O: 0,
    X: 0,
  };
  const openBracket = ['[', '(', '{'];
  let stack = [];

  // 올바른 괼호인지 검사
  function isCorrect(bracket) {
    for (const s of bracket) {
      // 열린 괄호일 때
      if (openBracket.includes(s)) {
        // stack에 데이터를 push!
        stack.push(s);

        // 닫힌 괄호일 때
      } else {
        // 현재 순회 요소와 stack의 top과 짝이 맞는지 비교해서 맞을 경우 pop!
        const top = stack.at(-1);

        if (top === '[' && s === ']') stack.pop();
        else if (top === '{' && s === '}') stack.pop();
        else if (top === '(' && s === ')') stack.pop();
        else stack.push(s);
      }

    }
    // stack이 비어있으면 올바른 괄호, 괄호가 남아있으면 올바르지 않은 괄호
    return stack.length === 0;
  }

  // 괄호를 회전 시키면서 검사해 점수를 입력
  for (let i = 0; i < data.length; i++) {    
    // 현재 괄호가 올바르면 score['X']에 점수 추가 아니면 score['O']에 추가
    isCorrect(data) ? score['X']++ : score['O']++;    

    // 괄호 회전
    const first = data.shift();
    data.push(first);    

    // stack 초기화
    stack = [];
  }

  return score['X'];
}

console.log(solution('[](){}')); // 3
console.log(solution('}]()[{')); // 2
console.log(solution('[)(]')); // 0
console.log(solution('}}}')); // 0

 

💯 [ 문제 11 ]. 짝지어 제거하기

문제 : 프로그래머스 - 짝지어 제거하기

function solution(str) {
  let stack = [];

  // 비교를 위해 첫번째 요소를 stack에 넣는다.
  stack.push(str[0]);

  for (let i = 1; i < str.length; i++) {
    const top = stack.at(-1);

    // stack의 top과 같다면 stack에 pop! 그렇지 않다면 현재 요소를 stack에 push!
    top === str[i] ? stack.pop() : stack.push(str[i]);
  }

  // stack이 비어있으면 1, 그렇지 않으면 0
  return stack.length === 0 ? 1 : 0;
}

console.log(solution('baabaa')); // 1
console.log(solution('cdcd')); // 0

 

문제를 풀때 어떻게 접근해야 할지 몰랐으나
학습한 스택(Stack) 개념을 활용해서 접근하자 문제가 풀렸다. 👍

출처

• 코딩 테스트 합격자 되기 - 자바스크립트 편
• 프로그래머스