[자료구조 with JS] 스택(Stack)

 

스택(Stack)

 데이터가 들어오는 방향과 나가는 방향이 같은 자료구조이다. 마지막에 삽입된 항목만을 제거하고 접근할 수 있다. 상자 안에 그릇이 쌓여있는 것을 상상하면 쉽다. 그릇을 추가할 때에도 맨 위에만 추가할 수 있고, 제거할 때에도 맨 위에 있는 그릇만 제거할 수 있다.

스택

스택의 특징

1. First In Last Out (FILO): 마지막에 들어온 정보가 먼저 나간다.

2. 스택의 삽입과 삭제는 각각 배열의 push(), pop() 메서드를 사용하여 구현할 수 있다.

3. 속도가 빠르다는 장점이 있다.

 

 

삽입(push), 삭제(pop), 들여다보기(peek)

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

• 세 메서드 모두 시간복잡도가 O(1)이므로 처리 속도가 빠르다.

 

반응형

 

스택으로 큐 만들기

관련글: [자료구조 with JS] 큐(Queue)

 

<문제>

스택 두 개를 사용하여 큐를 구현하라. 단, Queue 클래스 안에 배열을 만들면 안 된다. Queue 클래스 안에는 add, remove, peek 메서드가 존재해야 한다. 

//예시
const q = new Queue();
q.add(1);
q.add(2);
q.peek(); //returns 1
q.remove(); //returns 1
q.remove(); //returns 2

 

<Solution>

 두 개의 스택 stack, reverse를 이용해서 Queue 클래스를 구현하였다. stack의 데이터를 reverse로 순서대로 전부 옮기면 stack과 정반대로 데이터가 나열되게 된다. 즉, reverse 스택의 가장 위에는 stack에 가장 먼저 삽입된 데이터가 위치하게 된다. 따라서 가장 먼저 삽입된 데이터를 반환하는 peek()과 remove() 메서드를 구현할 수 있다.

 또한, peek()과 remove()에서 데이터를 return 하기 전에 reverse에 옮겨진 데이터를 stack으로 다시 옮겨 원상태로 되돌려야 한다. 

class Queue {
    
    constructor() {
        this.stack = new Stack();
        this.reverse = new Stack();
    }
    
    add(n) {
        this.stack.push(n);
    }
    
    peek() {
        while(this.stack.peek()) {
            this.reverse.push(this.stack.pop());
        }
        const peeked = this.reverse.peek();
        while(this.reverse.peek()) {
            this.stack.push(this.reverse.pop());
        }
        return peeked;
    }
    
    remove() {
        while(this.stack.peek()) {
            this.reverse.push(this.stack.pop());
        }
        const removed = this.reverse.pop();
        while(this.reverse.peek()) {
            this.stack.push(this.reverse.pop());
        }
        return removed;
    }
}

 

 

 

참고: ⟨자바스크립트로 하는 자료구조와 알고리즘(배세민 저)⟩, The Coding Interview Bootcamp: Algorithms + Data Structures (Udemy Course)