스택 자료구조(Stack) 간단 정리 - javascript

## 스택 

### 1. 스택이란? 

자료구조의 한 형태로, 후입선출(LIFO:Last In, First Out) 방식으로 동작한다. 

즉, 마지막에 삽입된 데이터가 가장 먼저 삭제되는 구조다. 

### 2. 스택 동작 이해하기 

기본적인 연산

1) `push`  : 스택의 맨 위에 데이터를 삽입하는 연산. 

2) `pop` : 스택의 맨 위에 있는 데이터를 삭제하고 반환하는 연산. 

3) `peek` 또는 `top` : 스택의 맨 위에 있는 데이터를 삭제하지 않고, 반환하는 연산.

4) `isEmpty` : 스택이 비어있는지를 확인하는 연산. 

5) `size` : 스택에 있는 데이터의 개수를 반환하는 연산. 

 

### 3. 스택의 사용예시 

1) 함수 호출 스택: 함수가 호출될 때마다 스택에 호출 정보가 저장되고, 함수가 종료되면 스택에서 제거된다. 이를 통해 함수 호출의 순서와 실행 상태를 관리한다. 

2) 역순 문자열 만들기 : 문자열의 각 문자를 스택에 차례로 넣은 다음, 스택에서 하나씩 꺼내면 원래 문자열의 역순이 된다. 

3) 수식의 괄호 검사: 프로그래밍 언어나 수학 수식에서 괄호가 올바르게 짝을 이루는지 확인할 때 사용. 

### 4. 스택 구조 구현하기 

방법1) 배열을 이용해 구현하기

class Stack {
  constructor() {
    this.items = [];
  }

  // 스택에 데이터 삽입
  push(item) {
    this.items.push(item);
  }

  // 스택에서 데이터 제거 및 반환
  pop() {
    if (!this.isEmpty()) {
      return this.items.pop();
    } else {
      return null;
    }
  }

  // 스택의 맨 위 데이터 반환 (제거하지 않음)
  peek() {
    if (!this.isEmpty()) {
      return this.items[this.items.length - 1];
    } else {
      return null;
    }
  }

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

  // 스택의 크기 반환
  size() {
    return this.items.length;
  }
}

// 사용 예시
const stack = new Stack();
stack.push(1);
stack.push(2);
console.log(stack.peek()); // 2
console.log(stack.pop());  // 2
console.log(stack.size()); // 1

 

방법2) 클래스를 이용해 구현하기

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

class LinkedListStack {
  constructor() {
    this.head = null;
    this.count = 0;
  }

  // 스택에 데이터 삽입
  push(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
    this.count++;
  }

  // 스택에서 데이터 제거 및 반환
  pop() {
    if (this.isEmpty()) {
      return null;
    }
    const value = this.head.value;
    this.head = this.head.next;
    this.count--;
    return value;
  }

  // 스택의 맨 위 데이터 반환 (제거하지 않음)
  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.head.value;
  }

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

  // 스택의 크기 반환
  size() {
    return this.count;
  }
}

// 사용 예시
const linkedListStack = new LinkedListStack();
linkedListStack.push(1);
linkedListStack.push(2);
console.log(linkedListStack.peek()); // 2
console.log(linkedListStack.pop());  // 2
console.log(linkedListStack.size()); // 1

 

방법3) 연결리스트를 이용해 구현하기

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

class LinkedListStack {
  constructor() {
    this.head = null;
    this.count = 0;
  }

  // 스택에 데이터 삽입
  push(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
    this.count++;
  }

  // 스택에서 데이터 제거 및 반환
  pop() {
    if (this.isEmpty()) {
      return null;
    }
    const value = this.head.value;
    this.head = this.head.next;
    this.count--;
    return value;
  }

  // 스택의 맨 위 데이터 반환 (제거하지 않음)
  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.head.value;
  }

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

  // 스택의 크기 반환
  size() {
    return this.count;
  }
}

// 사용 예시
const linkedListStack = new LinkedListStack();
linkedListStack.push(1);
linkedListStack.push(2);
console.log(linkedListStack.peek()); // 2
console.log(linkedListStack.pop());  // 2
console.log(linkedListStack.size()); // 1