스택(Stack) 개념정리

스택(Stack)이란?

스택은 LIFO원칙을 따르는 선형 자료구조이다.

LIFO(Last-In-First-Out)란 ?

가장 나중에 들어간 데이터가 가장 먼저 나온다.

스택은 ADT(추상 자료형)이다.

“데이터 구조의 논리적인 특성을 정의하지만 직접적인 구현은 추상화 하는 것”

제약사항

스택은 배열처럼 순차적으로 데이터를 List형태로 저장한다.

1. 데이터는 스택의 끝에서만 삽입 가능하다.
   ->구현) push()
2. 데이터는 스택의 끝에서만 삭제 가능하다.
   ->구현) pop()
3. 스택의 마지막요소만 읽을 수 있다.
   ->구현) peek()

구현코드

class Stack{
    constructor() {
        this._items = [];
    }
    
    push(item) {
        this._items.push(item);
    }
    
    pop() {
        this._items.pop();
    }
    
    peek() {
        return this._items[this._items.length - 1]
    }
}

const s = new Stack();

s.push(10)
s.push(20)
s.push(30)
s.push(40)
console.log(s) // [10, 20, 30, 40]
console.log(s.peek()) // 40

s.pop() // 맨 마지막 데이터인 40 제거
s.pop() // 맨 마지막 데이터인 30 제거

console.log(s) // [10, 20]

push의 경우 스택의 맨 위에 요소를 추가하는 연산작업으로
기존의 요소들을 이동할 필요가 없어서 상수시간에 성능을 가지게 된다. 상수시간 또는 O(1)

pop도 마찬가지로 스택의 맨위의 요소를 제거하고 그 값을 반환하는 연산작업으로
기존 요소를 이동 시킬 필요가 없다. -> 상수시간 또는 O(1)

peek도 스택의 맨 위의 요소를 조회하는 메서드이고, 마찬가지로 특정위치 요소를 단순 참조만 하기때문에
기존 요소를 이동 시킬 필요가 없다. -> 상수시간 또는 O(1)

결론

스택은 위와 같이 구현이 매우 간단하고 매우 효율적인 선형 자료구조이다.
그리고 후입 선출의 원칙에 따라 동작한다.
이 원칙에 따라서 스택에 데이터를 추가하거나 제거할 때 최근 추가된 요소부터 처리를 해야한다.

이러한 처리를 해야되는 상황에서 사용되는 자료구조이다.
그리고 push, pop, peek메서드는 모두 상수시간으로 동작한다.
스택의 크기와 관계없이 일정한 실행시간을 보장하게 된다.