스택(Stack)

특징

• 끝에서만 접근 가능한 자료 구조. 
• 가장 마지막에 넣은 자료부터 꺼낼 수 있습니다. 이 때문에 LIFO(Last In First Out), 후입선출 구조라고 불립니다.
• 함수 호출 시 콜 스택에 사용됨.
• 웹 페이지 히스토리, ctrl+z 로 이전 작업 취소 등에 사용됩니다.

장점

• (배열로 구현할 경우)구현이 쉽습니다.

단점

• 맨 마지막 데이터로만 접근하고 작업할 수 있기 때문에 특정 요소를 검색, 조회하는데 불리한 구조입니다.

구현

배열(Array)로 구현

class StackByArray {
    constructor() {
        // JS 배열 메소드를 배제하기 위해 object로 구현
        this.arr = {};
        this.top = 0;
    }
    // 맨 마지막 데이터 확인
    peek() {
        return this.arr[this.top - 1];
    }
    // 삽입
    push(data) {
        // 가장 끝(top) 위치에 데이터 삽입
        this.arr[this.top] = data;
        // top + 1
        this.top++;
    }
    // 삭제
    pop() {
        let result;
        // top이 1이상일 때만 반환값을 할당함을 명시적으로 표시
        if (this.top > 0) {
            result = this.arr[--this.top];
            // 마지막 요소 제거
            delete this.arr[this.top];
        }
        return result;
    }
    // 모든 데이터 순서대로 확인
    printAll() {
        let result = '';
        for (let i = 0; i < this.top; i++) {
            result += this.arr[i];
            if (i < this.top - 1) {
                result += ',';
            }
        }
        console.log(result);
    }
}

let stack = new StackByArray();
stack.push(1);
console.log(stack.peek());
stack.push(2);
console.log(stack.peek());
stack.push(3);
console.log(stack.peek());
stack.printAll();
console.log(stack.peek());
console.log(stack.pop());
console.log(stack.peek());
console.log(stack.pop());
console.log(stack.peek());
console.log(stack.pop());
stack.printAll();

연결리스트로 구현

class Node {
    constructor(data, next = null) {
        this.data = data;
        this.next = next;
    }
}
class StackByLinkedList {
    constructor() {
        this.top = null;
        this.size = 0;
    }
    // 마지막 데이터 조회
    peek() {
        if (this.size > 0) {
            return this.top.data;
        }
        return null;
    }
    // 삽입
    push(input) {
        // 기존 node를 next로 하는 node 생성
        const newNode = new Node(input, this.top);
        // 생성한 노드를 top에 할당
        this.top = newNode;
        this.size++;
    }
    // 삭제
    pop() {
        if (this.size > 0) {
            // top 노드 데이터 꺼낸다
            let data = this.top.data;
            // top 다음 노드를 top으로 할당
            this.top = this.top.next;
            this.size--;
            return data
        }
        this.size--;
        return null;
    }
}
let stack = new StackByLinkedList();
stack.push(1);
console.log(stack.peek());
stack.push(2);
console.log(stack.peek());
stack.push(3);
console.log(stack.peek());
console.log(stack.pop());
console.log(stack.peek());
console.log(stack.pop());
console.log(stack.peek());
console.log(stack.pop());