[JavaScript] 스택, 큐 구현

1. 스택

const stack = [];

stack.push(3);
stack.push(2);
stack.pop();

console.log(stack.reverse());    // [2, 3]

 

push(), pop() 메소드로 구현할 수 있다.

 

 

2. 큐

push(), shift() (맨 앞에 있는 요소 추출) 를 사용하여 구현할 수 있지만, shift()는 O(n)의 시간복잡도를 가지고 있다. 시간상 이점을 가져오고 싶다면 연결 리스트로 큐를 만든다.

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

class Queue {
    constructor() {
        this.front = null;    // (제일 먼저 나갈) 첫번째 노드
        this.rear = null;    // 마지막 노드
        this.size = 0;
    }
    
    enqueue(data) {
    	const newNode = new Node(data);
        
        if (this.size === 0) {
            this.front = newNode;
        } else {
            this.rear.next = newNode;    // 마지막 노드에 새로 들어온 노드 연결
        }
        
        this.rear = newNode;    // 큐의 마지막 노드를 새로 들어온 노드로 변경
    	this.size++;
    }
    
    dequeue() {
    	if (this.size === 0) {
            return;
        }
        
    	const data = this.front.data;
    	this.front = this.front.next;    // 첫번째 노드에 연결된 노드가 첫번째 노드가 됨
        this.size--;
        
        return data;
    }
}