02. 스택(Stacks)

1. 스택 구조

- 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책

- FILO(First-In, Last-Out) 또는 LIFO(Last-In, First-Out)

- 대표적인 스택의 활용으로 컴퓨터 내부의 프로세스 구조의 함수 동작 방식이 있음

- 구조가 단순해서 구현이 쉬우며 데이터 저장/읽기 속도가 빠름

- 데이터 최대 갯수를 미리 정해야 하므로 저장공간의 낭비가 발생할 수 있음 (미리 최대 갯수 만큼 저장 공간을 확보해야 함)

push	데이터를 스택에 넣기
pop	데이터를 스택에서 꺼내기

2-1. 스택 구현 (Array-based)

class stack {

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

    // 1. 스택에 새로운 element 추가
    push(element) {
        this.items.push(element);
    }

    // 2. 스택에서 element 삭제
    pop() {
        return this.items.pop();
    }

    // 3. If we would like to know what the last element added to our stack was, we can use the peek method
    // stack 이니까 top element가 return 됨 (LIFO, FILO)
    peek() {
        return this.items[this.items.length - 1];
    }

    // 4. 스택이 비었는지 확인하는 method
    isEmpty() {
        return this.items.length === 0;
    }

    // 5. 스택을 비우는 method
    clear() {
        this.items = [];
    }

    // 6. 스택 사이즈를 리턴하는 method
    size() {
        return this.items.length;
    }

}

2-2. 스택구현 (Object based)

class stack {

    constructor() {
        this.count = 0;
        this.items = {};
    }

    // 1. 스택에 새로운 element 추가
    push(element) {
        this.items[this.count] = elememt;
        this.count++;
    }

    // 2. 스택에서 element 삭제
    pop() {

        if (this.isEmpty()) {
            return undefined;
        }

        this.count--;

        const result = this.items[this.count];
        delete this.items[this.count];

        return result;

    }

    // 3. If we would like to know what the last element added to our stack was, we can use the peek method
    // stack 이니까 top element가 return 됨 (LIFO, FILO)
    peek() {

        if (this.isEmpty()) {
            return undefined;
        }

        return this.items[this.count - 1];

    }

    // 4. 스택이 비었는지 확인하는 method
    isEmpty() {
        return this.count === 0;
    }

    // 5. 스택을 비우는 method
    clear() {
        this.items = {};
        this.count = 0;
    }

    // 6. 스택 사이즈를 리턴하는 method
    size() {
        return this.count;
    }

    toString() {

        if (this.isEmpty()) {
            return '';
        }

        let objString = `${this.items[0]}`;
        for (let i = 1; i < this.count; i++) {
            objString = `${objString}, ${this.items[1]}`;
        }

        return objString;

    }

}

 

소스참고: Learning JavaScript Data Structures and Algorithms