[Udemy] 스택(Stack)이란 ?

 

정의

스택(Stack)은 선형자료구조로, 후입선출(LIFO) 특징을 가지고 있다.

브라우저 히스토리, 쌓여있는 접시, ctrl + z로 undo 하는 행위에 사용된다.

 

 

코드 및 구현

1. 배열로 구현

가장 간단하게 스택을 구현하는 방법은 배열로 구현하는 것이다.

const stack = [];

stack.push('a');
stack.push('b');
stack.push('c');

stack.pop(); // c
stack.pop(); // b
stack.pop(); // a

// or

stack.unshift('hi');
stack.unshift('my');
stack.unshift('name');

stack.shift(); // name
stack.shift(); // my
stack.shift(); // hi

 

배열로 스택을 구현할 때 주의할 점은 데이터를 추가하는 방향와 빼내는 방향이 동일해야 하는 것이다.

push 메서드로 데이터를 뒤에서 추가했다면, 데이터를 빼낼 때도 pop 메서드를 사용하여 뒤에서 데이터를 빼내야한다.

unshift 메서드로 데이터를 앞에서 추가했다면, 데이터를 빼낼 때도 shift 메서드로 앞에서 데이터를 빼내야한다.

 

 

2. 연결 리스트로 구현

아주 큰 데이터를 스택으로 다뤄야 할 경우, 배열 대신 연결 리스트를 사용하면 메모리 사용량을 줄일 수 있다.

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

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

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

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

 

연결 리스트로 스택을 구현할 때 주의할 점은 메서드 이름은 push, pop을 사용하였지만

실제 구현 로직은 연결리스트의 unshift, shift 처럼 구현해야한다.

왜냐하면 이전 시간에 배운 연결리스트의 pop 메서드 처럼 구현하게되면

head에서부터 마지막 이전까지 순회 해야하므로 O(n)의 시간복잡도로 접근해야한다.

 

하지만 스택의 경우 삽입과 제거는 O(1)의 시간복잡도를 가져야 하기 때문에

위와 같이 연결리스트 앞에서부터 삽입, 제거를 해줘야한다.

 

 

시간복잡도

삽입 및 제거 - O(1)

검색 및 접근 - O(n)

 

스택 자료구조는 데이터를 검색하거나 접근하는 것이 주된 용도가 아닌

후입선출의 선형 자료구조를 사용해야할 경우 시간 복잡도를 효율적으로 사용할 수 있다.

 

 

참조

Udemy - Js 알고리즘 & 자료구조 강의