스택

스택 개념

스택은 입력한 데이터를 제일 나중에 꺼낼수 있는 구조로 LIFO(Last In First Out)구조를 띄고 있습니다.

이때 스택에 삽입하는 연산을 푸시(push), 꺼내는 연산을 팝(pop)이라고 합니다.

스택의 동작 원리 이해하기

스택의 동작 원리는 배열과 같습니다.

const stack = [];

// 스택 삽입
stack.push("item");

console.log(stack); // ["stack"]

// 스택 삭제
const popItem = stack.pop();
console.log(popItem); // "stack"

stack.push("item1");
stack.push("item2");
stack.push("item3");
stack.push("item4");
stack.push("item5");

stack.pop();
console.log(stack); // ["item1", "item2", "item3", "item4"]

스택의 정의

스택의 ADT를 정의해보겠습니다.

구분	정의	설명
연산	boolean isFull()	스택에 들어있는 데이터의 갯수가 최대인지 확인합니다.
연산	boolean isEmpty()	스택에 들어있는 데이터가 하나도 없는지 확인합니다.
연산	void push(item: ItemType)	스택에 마지막에 데이터를 추가합니다.
연산	ItemType pop()	스택에 마지막에 있는 데이터를 제거하고 해당 데이터를 반환합니다.
상태	int top	스택에서 최근에 삽입한 데이터의 위치를 기록합니다. 만약 들어온 값이 없다면 -1을 기록합니다.
상태	ItemType[] data[maxSize]	스택의 데이터를 관리하는 배열입니다. 최대 maxSize 개의 데이터를 관리합니다.

스택 세부 동작에 대해 조금 더 자세히 알아보기

스택에서 데이터가 추가 될 경우: 일단 데이터가 가득 차있는지 검사합니다. isFull() 이후 top을 1만큼 증가시킵니다. 만약 -1의 경우 1로 만듭니다.

스택에서 데이터가 제거 될 경우: 데이터를 제거한 후 isEmpty() 함수를 실행합니다. 만약 데이터가 없다면 top을 -1로 가리키게 합니다. 데이터가 남아있다면 top을 1만큼 감소시킵니다.

스택 구현하기

아래 코드는 자바스크립트의 클래스를 이용하여 직접 구현한 자바스크립트 코드입니다.

class Stack {
    constructor(maxSize) {
        this.value = []
        this.maxSize = maxSize
        this.top = -1
    }

    isFull() {
        return this.top === this.maxSize
    }

    isEmpty() {
        return this.value.length === 0
    }

    push(newItem) {
        if (this.isFull()) {
            console.log('스택이 가득 찼습니다.')
        } else {
            this.value.push(newItem)
            this.top = Math.max(1, this.top += 1)
        }
    }

    pop() {
        if (this.isEmpty()) {
            console.log('스택이 비어져 있습니다.')
        } else {
            this.value.pop()
            if (this.isEmpty()) {
                this.top = -1
            } else {
                this.top -= 1
            }
        }
    }
}

Last modified: 07 August 2024