🎉 berenickt 블로그에 온 걸 환영합니다. 🎉
CS
자료구조&알고리즘-js
05-stack(스택)

1. 스택

  • LIFO(Last In First Out)이라는 개념을 가진 선형 자료구조
  • 나중에 들어간 것이 먼저 나온다.
  • 바닥이 막힌 상자를 생각하면 편하다.
    • e.g.) 프링글스 통
Data Structure_5_1
  • 한쪽 끝에서 삽입, 삭제가 이루어지는 후입선출(LIFO, Last in First Out) 구조를 가진다.
  • 스택에 데이터가 삽입될 위치를 Top이라고 한다.

1.1 스택의 기본 연산

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

1.1 스택 메모리

1
function sum(a, b) {

2
  return a + b

3
}

4
function print(value) {

5
  console.log(value)

6
}

7
print(sum(5, 10))

Data Structure_5_3

  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로 표현할 수 있다.

Data Structure_5_4

1.3 Linked List로 표현하기

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

Data Structure_5_5

2. 구현

2.1 Array로 구현

1
const stack = []

2


3
// push

4
stack.push(1)

5
stack.push(2)

6
stack.push(3)

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

8


9
// pop

10
stack.pop()

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

12


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

2.2 Linked List로 구현

1
class Node {

2
  // 생성자: new 키워드로 객체를 생성할때 호출되는 함수

3
  constructor(value) {

4
    this.value = value

5
    this.next = null

6
  }

7
}

8


9
class Stack {

10
  // 생성자: new 키워드로 객체를 생성할때 호출되는 함수

11
  constructor() {

12
    this.top = null

13
    this.size = 0

14
  }

15
  // 추가

16
  push(value) {

17
    const node = new Node(value) // 입력받은 값으로 새 노드 생성

18
    node.next = this.top // 새로 생성한 노드의 다음은 실행노드의 top을 가르킴

19
    this.top = node // 실행노드의 top은 노드를 가르킴

20
    this.size += 1

21
  }

22
  // 삭제

23
  pop() {

24
    const value = this.top.value // 실행노드의 top의 value를 변수로

25
    this.top = this.top.next // 실행노드의 top의 next를 top으로

26
    this.size -= 1

27
    return value

28
  }

29
  size() {

30
    return this.size

31
  }

32
}

33


34
const stack = new Stack()

35
stack.push(1)

36
stack.push(2)

37
stack.push(3)

38
console.log(stack.pop()) // 3

39
stack.push(4)

40
console.log(stack.pop()) // 4

41
console.log(stack.pop()) // 2

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

3.1 문제

3.2 풀이

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

3.2.1 stack 이용

1
function solution(s) {

2
  const stack = []

3


4
  // for of : 배열 순회

5
  for (const c of s) {

6
    // 여는 괄호일 경우

7
    if (c === '(') {

8
      stack.push(c)

9
    } else {

10
      // 스택이 비어있는 경우

11
      if (stack.length === 0) {

12
        return false

13
      }

14
      // 닫는 괄호일 경우

15
      stack.pop()

16
    }

17
  }

18
  // 빈 배열이라면 true, 아니라면 false

19
  return stack.length === 0

20
}

3.2.2 stack을 이용하지 않는 방법

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

1
function solution(s) {

2
  let opened = 0

3
  for (const bracket of s) {

4
    if (bracket === '(') opened += 1

5
    if (bracket === ')') opened -= 1

6
    if (opened < 0) return false

7
  }

8
  return opened === 0

9
}

[참고]

04-연결(linked)-list06-queue(큐)