Data Structure - Stack

 Stack 

• ‘쌓다, 올리다’라는 뜻으로
• LIFO, Last Input First Out 나중에 들어간 것이 먼저 나오는 후입선출의 자료구조다.
• Stack이 사용되는 곳
  • 함수가 다른 함수를 호출할 때의 메모리에 쌓이는 기능
  • 뒤로가기 버튼의 Undo기능으로 사용자가 수행한 작업을 되돌리는 기능.
• push : 맨 뒤의 데이터 추가, pop : 맨 뒤의 데이터 제거
• JavaScript의 arr - push와 pop메서드를 활용해 구현가능

스택 이미지 출처 https://velog.io/@soor/Data-structure-stack-queue

 

 JavaScript로 Stack구현하기 

스택 구현 정의

• 스택에 데이터가 가득 찼는지 / 비었는지 확인하는 연산이 필요하고,
• 데이터를 추가 / 삭제하는 연산도 필요하다.

알고리즘을 풀 때 Stack을 사용해 풀어라!!는 말은 없다. 그러니 스택을 적용하는 부분을 감으로 찾을 수 있도록 연습해야 한당!!! 데이터를 저장하고 순서와 상관 없이 임의 접근하는 것은 배열을 사용하면 되지만, 최근 삽입한 데이터를 대상으로 연산을 해야 하는 문제의 경우 스택을 떠올리는 것이 좋다.

 

const stack = []
const maxSize = 10;

function isFull(stack) {
  return stack.length === maxSize;
}

function isEmpty(stack) {
  return stack.length === 0;
}

function push(stack, item) {
  if(stack.length >= maxSize){
    console.log('스택이 가득 찼습니다. 데이터 추가를 못했습니다')
    return stack
  }else {
    return stack.push(item);
  }
}

function pop(stack, item) {
  if(stack.isEmpty(stack)){
    console.log('스택이 비어있습니다')
    return 
  }else {
    console.log('item을 제거했습니다')
    return stack.pop(item);
  }
}

 

 

 배열 정렬하기 

소괄호는 짝을 맞춘 열린 괄호’ ( ’ 와 닫힌 괄호’ ) ‘ 로 구성됩니다. 문제에서는 열린 괄호와 닫힌 괄호가 뒤섞인 문자열을 줍니다. 이때 소괄호가 정상적으로 열고 닫혔는지 판별하는 solution함수를 구현하세요.

// 제약 조건
- 열린괄호는 자신과 가장 가까운 닫힌 괄호를 만나면 상쇄됩니다
- 더 상쇄할 괄호가 없을 때까지 반복합니다.

// 입출력 예
s = ((())(  / 반환값 False 
s = (())()  / 반환값 True 

• s 변수에 들어있는 무작위의 괄호 중에서 열린 괄호를 stack에 push 한다
• 닫힌 괄호가 나오면 stack에 있는 열린 괄호를 pop 해서 상쇄시킨다.

// let s = "(())()";
let s = "(())()(";

function solution(s) {
  const stack = [];
  for (const c of s) {
    if (c === "(") {
      stack.push(c);
    } else if (c === ")") {
      if (stack.length === 0) {
        return false;
      } else {
        stack.pop();
      }
    }
  }
  console.log("남는것", stack);
  return stack.length === 0;
}

console.log(solution(s));