스택(Stack)

스택(Stack)

- LIFO(Last In First Out) 으로 데이터를 저장하는 구조입니다.

- 나중에 들어온 데이터가 먼저 나갑니다.

- 주요 동작으로는 push, pop, peek 등이 있습니다.

- push(데이터) : 스택에 데이터 추가

- pop() : 스택으로부터 최상단에 있는 데이터 제거

- peek() : 스택 최상단에 있는 데이터 값 반환

JavaScript 로 스택 구현(feat. Array)

class Stack {
  constructor() {
    // item들을 받을 배열 생성
    this.stack = [];
  }
  
  isEmpty() {
    return this.stack.length == 0;
  }
  
  push(item) {
    this.stack.push(item);
  }
  
  pop() {
    return this.stack.pop();
  }
  
  peek() {
    if (this.isEmpty()) return null;
    return this.stack[this.stack.length - 1];
  }
}

const stack = new Stack();
stack.push(1); // stack: [1]
stack.push(2); // stack: [1, 2]
stack.push(3); // stack: [1, 2, 3]

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

JavaScript 로 Stack 구현(feat. Linked List)

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

class Stack {
  constructor() {
    this.top = null;
  }
  
  isEmpty() {
    return this.top == null;
  }
  
  push(data) {
    const newNode = new Node(data);
    newNode.next = this.top;
    this.top = newNode;
  }
  
  pop() {
    if (this.isEmpty()) return;
    this.top = this.top.next;
  }
  
  peek() {
    if (this.isEmpty()) return null;
    return this.top.data;
  }
}

스택의 시간 복잡도

삽입 : 스택에 들어 있는 값들이 무수히 많아도 데이터 삽입은 한 번이기 때문에 시간 복잡도는 O(1) 이 됩니다.

삭제 : LIFO 에 따라 삭제 시 최상위 데이터만 삭제되므로 스택의 크기에 상관없이 시간 복잡도는 O(1) 이 됩니다.

접근 : 스택 특성상 한쪽 끝으로만 자료를 넣고 뺄 수 있는 구조이므로 데이터 접근 또한 데이터가 삽입된 top을 통해서만 접근 가능합니다. 따라서 n번째 접근은 top 데이터부터 순회하기 때문에 시간 복잡도는 O(n) 이 됩니다.

탐색 : 데이터 탐색 시 만약 스택의 가장 최상단에 있는 데이터를 찾는다면 시간 복잡도는 O(1) 일 것입니다. 하지만 가장 밑에 있는 데이터를 탐색한다면 데이터의 개수 n 만큼 작업이 발생하므로 시간 복잡도는 O(n) 일 것입니다.

시간 복잡도	삽입	삭제	접근	n번째 접근	탐색
스택	O(1)	O(1)	O(1)	O(n)	O(n)

 

스택 사용 사례 :

- 함수 실행 컨텍스트들이 쌓이는 Call Stack 과 브라우저의 방문 기록이 쌓이는 History Stack 이 대표적입니다.

- 재귀적으로 함수를 호출해야 하는 경우 임시 데이터를 스택에 넣어줍니다.