[JavaScript 알고리즘] 스택

📕Algorithm/JavaScript

[JavaScript 알고리즘] 스택

_Hazel_ 2024. 10. 26. 17:09

- 목표

스택의 정의에 대해 알아보기
스택의 사용 사례를 이해하기
스택의 연산 구현 살펴보기

1. 스택

- LIFO(후입선출 구조)

- 스택에 마지막으로 추가된 요소가 스택에서 가장 먼저 제거되는 구조

2. 스택 사용사례

- 스택의 사용처

함수 호출 관리
실행 취소(Undo) / 다시 실행(Redo)
라우팅 (history 객체가 스택처럼 사용됨)

- 스택 만드는 방식

배열 사용하기
연결 리스트 사용하기

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.first = null;  // 스택의 맨 위 노드
    this.last = null;   // 스택의 맨 아래 노드
    this.size = 0;      // 스택의 크기
  }
}

3. 스택 연산 구현

(1) push

- 의사 코드

값을 입력받기: 함수는 입력으로 값 하나를 받습니다. 이 값은 새 노드에 저장됩니다.
새 노드 생성: 입력받은 값으로 새 노드를 만듭니다.
스택이 비어 있는지 확인:
1. 만약 스택이 비어 있다면(즉, 노드가 하나도 없다면), 새로 만든 노드를 first와 last 프로퍼티로 설정합니다. 이는 스택의 첫 번째이자 마지막 노드로 새 노드를 지정하는 작업입니다.
2. 만약 스택에 노드가 이미 하나 이상 있다면, 다음 작업을 진행합니다.
현재 첫 번째 노드 저장 : 스택에 노드가 있다면, 현재의 첫 번째 노드를 변수에 저장합니다. 이 변수는 이전 첫 번째 노드를 가리키게 됩니다.
첫 번째 노드를 새로 만든 노드로 변경 : 스택의 first 프로퍼티를 새로 만든 노드로 설정하여 새 노드를 스택의 첫 번째 노드로 만듭니다.
새 노드의 next 프로퍼티 설정 : 새 노드의 next 프로퍼티를 이전 첫 번째 노드(저장했던 변수)로 설정하여 연결을 유지합니다.
스택 크기 증가 : 스택의 크기(size 변수)를 1 증가시켜, 새 노드가 추가되었음을 반영합니다.

- 구현

  // 값 추가 메소드 (Push)
  push(value) {
    const newNode = new Node(value);
    if (this.size === 0) {
      this.first = newNode;
      this.last = newNode;
    } else {
      const temp = this.first;
      this.first = newNode;
      this.first.next = temp;
    }
    this.size++;
    return this.size;
  }

console.log(stack.pop()); // 10 제거 및 출력
console.log(stack.pop()); // 스택이 비었으므로 null 반환

- 과정

1. 초기 상태 (빈 스택)

Stack
┌───────────┐
│  first    │ → null
│  last     │ → null
│  size     │ = 0
└───────────┘

- 스택이 비어 있고, first, last는 null이며 size는 0입니다.

2. push(10)

값 10을 스택에 추가합니다.

Stack
┌───────────┐
│  first    │ → [10] → null
│  last     │ → [10] → null
│  size     │ = 1
└───────────┘

스택이 비어 있었기 때문에, 새로 추가된 노드 [10]이 first와 last가 됩니다.
size가 1이 됩니다.

3. push(20)

값 20을 스택에 추가합니다.

Stack
┌───────────┐
│  first    │ → [20] → [10] → null
│  last     │ → [10] → null
│  size     │ = 2
└───────────┘

새 노드 [20]이 스택의 맨 위(first)에 추가됩니다.
이전 first였던 [10]은 [20]의 next가 되어, 연결이 유지됩니다.
size가 2가 됩니다.

4. push(30)

값 30을 스택에 추가합니다.

Stack
┌───────────┐
│  first    │ → [30] → [20] → [10] → null
│  last     │ → [10] → null
│  size     │ = 3
└───────────┘

새 노드 [30]이 first로 추가되고, 이전 first였던 [20]은 [30]의 next가 됩니다.
size가 3이 됩니다.

(2) pop

- 의사 코드

스택이 비어 있는지 확인 : 만약 스택에 노드가 없다면, null을 반환합니다. (제거할 노드가 없음을 의미)
현재 첫 번째 노드 저장 : 첫 번째 노드를 제거하기 전에, 현재 first 프로퍼티를 임시 변수에 저장합니다. 이 변수는 제거할 노드를 임시로 가리키게 됩니다.
노드가 하나만 있는지 확인 : 만약 스택에 노드가 하나만 있다면, first와 last 프로퍼티를 모두 null로 설정합니다. 이는 스택이 비게 됨을 의미합니다.
스택에 노드가 두 개 이상 있을 경우 : 만약 스택에 노드가 두 개 이상 있다면, first 프로퍼티를 현재 첫 번째 노드의 next 프로퍼티로 설정하여, 첫 번째 노드를 제거하고 두 번째 노드를 새 첫 번째 노드로 지정합니다.
스택 크기 감소 : 스택의 크기(size 변수)를 1 감소시켜, 노드가 제거되었음을 반영합니다.
제거된 노드의 값 반환 : 저장했던 임시 변수에 있는 제거된 노드의 값을 반환합니다.

- 구현

// 값 제거 메소드 (Pop)
  pop() {
    if (this.size === 0) return null;  // 스택이 비어 있으면 null 반환

    const temp = this.first;
    if (this.size === 1) {
      this.first = null;
      this.last = null;
    } else {
      this.first = this.first.next;
    }
    this.size--;
    return temp.value;  // 제거된 노드의 값 반환
  }

- 과정

1. pop() (값 제거)

스택에서 가장 위의 값을 제거합니다.

Stack
┌───────────┐
│  first    │ → [20] → [10] → null
│  last     │ → [10] → null
│  size     │ = 2
└───────────┘

first 노드 [30]이 제거됩니다.
새로운 first는 [20]이 되며, 스택 크기(size)는 2가 됩니다.
제거된 값 30이 반환됩니다.

2. pop() (또 다른 값 제거)

다시 pop을 호출하여 값을 하나 더 제거합니다.

Stack
┌───────────┐
│  first    │ → [10] → null
│  last     │ → [10] → null
│  size     │ = 1
└───────────┘

현재 first 노드 [20]이 제거됩니다.
새로운 first는 [10]이 되며, 스택 크기(size)는 1이 됩니다.
제거된 값 20이 반환됩니다.

3. pop() (스택에 마지막 값 제거)

스택에 마지막 값을 제거합니다.

Stack
┌───────────┐
│  first    │ → null
│  last     │ → null
│  size     │ = 0
└───────────┘

현재 first 노드 [10]이 제거됩니다.
스택이 비어 있게 되어 first와 last는 null이 되고, size는 0이 됩니다.
제거된 값 10이 반환됩니다.

4. 스택의 빅오

Insertion - O(1)

Removal - O(1)

Searching - O(N)

Access - O(N)

5. 전체 코드

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.first = null;  // 스택의 맨 위 노드
    this.last = null;   // 스택의 맨 아래 노드
    this.size = 0;      // 스택의 크기
  }

  // 값 추가 메소드 (Push)
  push(value) {
    const newNode = new Node(value);
    if (this.size === 0) {
      this.first = newNode;
      this.last = newNode;
    } else {
      const temp = this.first;
      this.first = newNode;
      this.first.next = temp;
    }
    this.size++;
    return this.size;
  }

  // 값 제거 메소드 (Pop)
  pop() {
    if (this.size === 0) return null;  // 스택이 비어 있으면 null 반환

    const temp = this.first;
    if (this.size === 1) {
      this.first = null;
      this.last = null;
    } else {
      this.first = this.first.next;
    }
    this.size--;
    return temp.value;  // 제거된 노드의 값 반환
  }
}

// 스택 사용 예시
const stack = new Stack();
stack.push(10);  // 스택에 10 추가
stack.push(20);  // 스택에 20 추가
stack.push(30);  // 스택에 30 추가

console.log(stack.pop()); // 30 제거 및 출력
console.log(stack.pop()); // 20 제거 및 출력
console.log(stack.pop()); // 10 제거 및 출력
console.log(stack.pop()); // 스택이 비었으므로 null 반환

6. 정리

스택(Stack)은 LIFO(Last In, First Out) 자료 구조로, 마지막에 들어온 값이 항상 첫 번째로 나가는 특성을 가집니다.

스택은 다음과 같은 상황에서 사용됩니다:

함수 호출 관리: 함수 호출 스택(예: 콜 스택)에서 사용됩니다.
실행 취소/재실행(undo/redo): 작업을 되돌리거나 다시 수행할 때 사용됩니다.
라우팅: 방문한 페이지를 기억하고 뒤로 가기나 앞으로 가기 기능을 구현할 때 사용됩니다.

스택은 자바스크립트에서 내장된 자료 구조는 아니지만, 구현이 비교적 간단합니다. 삽입(push)과 제거(pop) 연산 모두 **O(1)**의 시간 복잡도를 가지므로 빠르게 수행됩니다.

'📕Algorithm > JavaScript' 카테고리의 다른 글

[JavaScript 알고리즘] 이진 검색 트리 (0)	2024.10.27
[JavaScript 알고리즘] 큐 (0)	2024.10.27
[JavaScript 알고리즘] 다중 연결 리스트 (1)	2024.10.24
[JavaScript 알고리즘] 단일 연결 리스트 (2)	2024.10.22
[JavaScript 알고리즘]자료 구조 (0)	2024.10.21

현재글[JavaScript 알고리즘] 스택

Hazel's 기술 블로그

선택정렬, 빅오표기법, 자료구조, 삽인정렬, 자바스크립트알고리즘, 알고리즘, 버블정렬, 재귀, 시간복잡도, 합병정렬, 자바스크립트,

Today :
Yesterday :

일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30

Hazel's 기술 블로그