Stacks

1. 스택이란?

스택은 후입선출을 가진 자료 구조 입니다. 위키 백과 사전에는 다음과 같이 스택을 정의 합니다.

For the use of the term LIFO in accounting, see LIFO (accounting). For the use of the term pushdown in strength training, see Pushdown (exercise). For other uses, see Stack (disambiguation).

마지막 요소가 스택에 추가 되고 첫번째 요소가 제거가 됩니다.

2. 스택 의사 코드

배열의 왼쪽부터 오른쪽 방향으로 확인하면서 최솟값을 결정합니다.
한 차례씩 이동하면서 가장 작은 값을 저장합니다.
변수에 들어 있는 값보다 작은 값이 들어 있으면 변수가 새 인덱스로 값이 대체됩니다.
최솟값이 어느 인덱스에 있는지 알고 있으면 그 인덱스 값과 패스스루를 통해 값을 교환합니다.
이 과정을 계속 반복합니다.

3. 스택 구현

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

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

    push(value) {
        const newNode = new Node(value);
        if(!this.first) {
            this.first = newNode;
            this.last = newNode;
        } else {
            const temp = this.first;
            this.first = newNode;
            this.first.next = temp;
        }
        return ++this.size;
    }

    pop() {
        if(!this.first) return null;
        const temp = this.first;
        if(this.first === this.last) {
            this.last = null;
        }
        this.first = this.first.next;
        return temp.value;
    }
}