1. 스택

• LIFO(Last In First Out)이라는 개념을 가진 선형 자료구조
• 나중에 들어간 것이 먼저 나온다.
• 바닥이 막힌 상자를 생각하면 편하다.
  • e.g.) 프링글스 통

• 한쪽 끝에서 삽입, 삭제가 이루어지는 후입선출(LIFO, Last in First Out) 구조를 가진다.
• 스택에 데이터가 삽입될 위치를 Top이라고 한다.

---

1.1 스택의 기본 연산

• push(data) : 스택의 top에 데이터를 삽입
• pop : 스택의 top에 위치한 요소를 제거
• isEmpty : 스택이 비어있는지 확인
• isFull : 스택이 꽉 찼는지 확인
• peek or top: 스택의 top에 위치한 요소를 반환

---

1.1 스택 메모리

function sum(a, b) {
  return a + b;
}
function print(value) {
  console.log(value);
}
print(sum(5, 10));

1. 스택 메모리는 함수가 호출되면, 생성되는 지역변수, 변환 주소값, 매개변수가 저장되는 메모리 영역입니다.
2. 가장 안쪽에 위치한 sum(5, 10)함수가 실행됨
3. sum()함수 실행이 종료되어, 스택 메모리에서 pop이 수행되며 제거가 됩니다.
4. print(15)가 실행됩니다.
5. print() 내부에는 console.log()가 있어, 스택 메모리에 다시 쌓이게 됩니다.
6. console.log() 출력을 마쳤다면, 스택 메모리에서 제거가 됩니다.
7. print()도 함수 호출이 완료되면서, 스택 메모리에서 제거가 됩니다.

---

1.2 Array로 표현하기

Stack을 Array로 표현할 수 있다.

---

1.3 Linked List로 표현하기

Stack을 Linked List로 표현할 수 있다.

---

2. 구현

2.1 Array로 구현

const stack = [];

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

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

console.log(stack[stack.length - 1]); // 2

---

2.2 Linked List로 구현

class Node {
  // 생성자: new 키워드로 객체를 생성할때 호출되는 함수
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  // 생성자: new 키워드로 객체를 생성할때 호출되는 함수
  constructor() {
    this.top = null;
    this.size = 0;
  }
  // 추가
  push(value) {
    const node = new Node(value); // 입력받은 값으로 새 노드 생성
    node.next = this.top; // 새로 생성한 노드의 다음은 실행노드의 top을 가르킴 
    this.top = node; // 실행노드의 top은 노드를 가르킴
    this.size += 1;
  }
  // 삭제
  pop() {
    const value = this.top.value; // 실행노드의 top의 value를 변수로
    this.top = this.top.next; // 실행노드의 top의 next를 top으로
    this.size -= 1;
    return value;
  }
  size() {
    return this.size;
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3
stack.push(4);
console.log(stack.pop()); // 4
console.log(stack.pop()); // 2

---

3. 스택 실습 : 올바른 괄호

3.1 문제

• https://school.programmers.co.kr/learn/courses/30/lessons/12909

---

3.2 풀이

• push '('와 pop ')'을 한 번씩 해서 빈 배열이 되어야 함
• 올바른 괄호 : (())()
• 올바르지 않은 괄호 : (()(

3.2.1 stack 이용

function solution(s) {
  const stack = [];
  
  // for of : 배열 순회
  for (const c of s) {
    // 여는 괄호일 경우
    if (c === '(') {
      stack.push(c);
    } else {
      // 스택이 비어있는 경우
      if (stack.length === 0) {
        return false;
      }
      // 닫는 괄호일 경우
      stack.pop();
    }
  }
  // 빈 배열이라면 true, 아니라면 false
  return stack.length === 0;
}

3.2.2 stack을 이용하지 않는 방법

stack보다 메모리를 적게 사용 가능

function solution(s) {
  let opened = 0;
  for (const bracket of s) {
    if (bracket === "(") opened += 1;
    if (bracket === ")") opened -= 1;
    if (opened < 0) return false;
  }
  return opened === 0;
}

---

[참고]

• https://laboputer.github.io/ps/2017/09/09/stack/