[JS] 연결 리스트로 스택(Stack) 구현

Linked List를 내부에서 생성하여 구현하는 방법이 아니라, Stack Class 자체가 Linked List가 되도록 구현한다.

구현할 메서드

• push(e) - 스택의 맨 위에 원소를 삽입한다.
• pop(e) - 스택의 맨 위에 있는 원소를 반환한다. (반환 후에는 삭제한다.)
• peek(e) - 스택의 맨 위에 있는 원소를 확인한다.
• isEmpty() - 스택이 비었는지 확인한다.
• isFull() - 스택이 가득 찼는지 확인한다.

자바스크립트에서는 이미 내장 메서드로 push(), pop() 과 같은 메서드가 존재하지만, 이전에 배운 연결 리스트를 사용하여 구현해보고자 한다.

노드 생성자

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

연결 리스트를 사용하기때문에 노드 객체를 만들기 위한 생성자를 구현해주어야 한다.

stack 생성자

class Stack {
    constructor() {
        this.top = null; // 스택의 맨 위를 나타내는 포인터
        this.size = 0; // 스택의 크기를 나타내는 변수
    }
}

이후 연결 리스트에서의 head 와 마찬가지로 제일 최상의 노드를 가리키는 포인터를 만들어준다.

 

즉 top 이 가리키는 요소가 Stack 에서 최상위 노드가 될 것이다.

push()

    push(data) {
        const newNode = new Node(data);
        if (!this.top) {
            this.top = newNode; // Stack에 요소가 존재하지 않으면 top이 새로 추가한 노드를 가리키도록 한다.
        } else {
            newNode.next = this.top; // 새로 추가된 노드의 next기 현재 top인 노드를 가리키도록한다.
            this.top = newNode; // 현재의 top을 새로 추가된 노드로 초기화 한다.
        }
        this.size++;
    }

가장 최근에 추가된 요소가 맨 위에 있는 구조 이기 때문에

 

값이 추가 될 때 마다 top이 가리키는 노드를 새롭게 초기화 해주어야 한다.

 

또한 연결 리스트로 동작하기 때문에 각 노드를 next로 연결해주는 작업이 필요하다.

pop()

    pop() {
        if (!this.top) return null; // Stack에 요소가 존재하지 않으면 null을 반환한다.

        const removedData = this.top.data;
        this.top = this.top.next; // top이 현재 노드의 다음 노드를 가리키도록 한다.
        this.size--;
        return removedData;
    }

pop() 은 top 이 가리키는 노드를 Stack 에서 제거하기 때문에

 

top 이 현재 최상위 노드의 다음 노드를 가리키도록 하면 된다.

peek()

    peek() {
        if (!this.top) return null; // Stack에 요소가 존재하지 않으면 null을 반환한다.

        return this.top.data;
    }

Stack 맨 위에 있는 요소를 반환한다.

isEmpty()

    isEmpty() {
        return this.size === 0;
    }

Stack 의 크기가 0 이면 true 를 반환하고, 그렇지 않으면 false 를 반환한다.

isFull()

    isFull() {
        return false;
    }

연결 리스트로 구현한 Stack 은 크기 제한이 없으므로 항상 false 를 반환한다.

전체 코드

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

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

    push(data) {
        const newNode = new Node(data);

        if (!this.top) {
            this.top = newNode;
        } else {
            newNode.next = this.top;
            this.top = newNode;
        }
        this.size++;
    }

    pop() {
        if (!this.top) return null;

        const removedData = this.top.data;

        this.top = this.top.next;
        this.size--;

        return removedData;
    }

    peek() {
        if (!this.top) return null;

        return this.top.data;
    }

    isEmpty() {
        return this.size === 0;
    }

    isFull() {
        return false;
    }
}

Big-O (시간 복잡도)

• 삽입 : O(1)
• 삭제 : O(1)
• 탐색 : O(n)

연결 리스트로 구현한 Stack 은 삽입 및 삭제 연산에서 O(1) 이다.

 

하지만 데이터를 찾는 경우에는 최상위 노드에서 부터 하나 씩 탐색하기 때문에,

 

가장 아래에 있는 요소를 찾기 위해서는 전체 요소의 개수 만큼의 작업이 발생되므로 시간 복잡도는 O(n) 이 된다.