스택

• 리스트의 한 쪽 끝에서만 데이터의 삽입 및 삭제가 이루어지는 LIFO(Last In First Out) 형태의 선형 자료구조이다.
• LIFO(Last In First Out) : 가장 최근에 스택에 추가된 항목이 가장 먼저 제거되는 방식.

연산

• pop() : 스택에서 가장 위에 있는 항목을 제거한다.
• push(data) : data를 스택의 가장 윗 부분에 추가한다.
• peek() : 스택의 가장 위에 있는 항목을 반환한다.
• isEmpty() : 스택이 비어 있는 경우 true를 반환한다.

구현 - javaScript

• javascript는 배열 내장 함수로 간단히 스택을 구현할 수 있지만 원리 이해를 위하여 사용하지 않고 구현하였다.

• 배열을 사용한 경우와 연결리스트를 사용한 경우를 구현해보았다.
  
  
  

• 배열 활용

'use strict';

class Stack {
  constructor() {
    this.storage = []; // 배열을 사용
    this.top = 0;
  }

  pop() {
    if (this.isEmpty()) {
      console.log('스택이 비어 있습니다.');
      return;
    }

    return this.storage[--this.top];
  }

  push(data) {
    this.storage[this.top++] = data;

    return;
  }

  peek() {
    if (this.isEmpty()) {
      console.log('스택이 비어 있습니다.');
      return;
    }

    console.log(this.storage[this.top - 1]);

    return;
  }

  isEmpty() {
    return this.top === 0 ? true : false;
  }
}

const stack = new Stack();

stack.push(1);
stack.peek();

stack.push(2);
stack.peek();

stack.push(3);
stack.peek();

stack.pop();
stack.peek();

stack.pop();
stack.peek();

stack.pop();
stack.peek();

• 연결리스트 활용

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

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  push(value) {
    const newNode = new Node(value);

    newNode.next = this.top;
    this.top = newNode;

    this.size++;

    return;
  }

  pop() {
    const popNode = this.top;

    if(this.size === 1) {
      this.top = null;
    } else {
      this.top = popNode.next;
    }

    this.size--;

    return popNode.value;
  }

  peek() {
    return this.top.value;
  }

  size() {
    return this.size;
  }
}

const stack = new Stack();

stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.pop());

stack.push(4);

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

활용 예시

• 스택의 특징인 후입선출(LIFO)을 활용하여 여러 분야에서 활용 가능하다.
  
  
• 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
• 재귀 알고리즘