Stack

스택(Stack)이란?

• Stack은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 데이터 구조이다.
• 후입 선출(LIFO: Last In First Out) 구조를 따른다.( Stack의 삽입과 삭제는 같은 방향에서 일어난다.)
  •   후입 선출이란? 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조이다.
• Stack에서는 주로 아래 세 가지 기본 작업이 수행된다.
  • Push: 스택에 항목을 추가한다. (스택이 가득 차면 Overflow condition)
  • Pop: 스택에서 항목을 제거한다. 항목은 푸시된 순서의 반대로 제거된다. (스택이 비어 있으면 Underflow condition)
  • Peek or Top: 스택의 최상위 항목을 반환한다.
• 식당에 쌓여있는 접시를 예로 들면 편하다. 접시는 순서대로 쌓아두지만 사용하는 접시는 위에서부터 꺼내기 때문이다.

Stack의 기본 구조

---

Stack 생성

• JS에서 스택은 Array를 사용하거나 Linked List를 사용해서 구현할 수 있다.
• Array로 생성하면 더욱 간단하다.

Stack을 Array로 생성하기

class Stack {
    constructor() {
        // 빈배열로 stack을 초기화
        this.stackArray = [];
    }

    // stack 마지막에 item 추가
    push(item) {
        this.stackArray.push(item);
    }

    // stack 마지막 item 제거
    pop() {
        return this.stackArray.pop();
    }

    // stack의 최상위 item 반환
    peek() {
        return this.stackArray[this.stackArray.length - 1];
    }

    // stack print
    print()  {
        console.log(`Stack: [${this.stackArray}]`);
    }
    
    // 스택이 비었는지 확인 비었으면 true 아니면 false
    isEmpty () {
        return this.stackArray.length === 0;
    }
}

const stack = new Stack();
console.log(`Is stack empty?: ${stack.isEmpty()}`); // 현재 stack은 [] 이기 때문에 'Is stack empty?: true'
stack.push(1);  // 현재 스택의 상태: [1]
stack.push(2);  // 현재 스택의 상태: [1, 2]
stack.push(3);  // 현재 스택의 상태: [1, 2, 3]
console.log(`Stack의 최상위 item: ${stack.peek()}`)   // Stack의 최상위 item: 3
stack.print()   // Stack: [1,2,3]
console.log(`${stack.pop()} 이 Stack에서 삭제되었습니다.`);    // 3 이 Stack에서 삭제되었습니다.
stack.print()   // Stack: [1, 2]
console.log(`Stack의 최상위 item: ${stack.peek()}`)   // Stack의 최상위 item: 2
console.log(`Is stack empty?: ${stack.isEmpty()}`); // 현재 stack은 [1, 2] 이기 때문에 'Is stack empty?: false'

---

사용된 전체 코드

https://github.com/rkdden/Data-Structure/blob/main/stack.js

GitHub - rkdden/Data-Structure

출처

https://www.geeksforgeeks.org/stack-data-structure-introduction-program/?ref=lbp 

Stack Data Structure (Introduction and Program) - GeeksforGeeks