자바스크립트의 자료구조 4 : 스택(Stack), 큐(Queue)

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

1. 스택(Stacks)과 큐(Queues)란?

스택과 큐

스택과 큐 모두 Linear한 자료구조형이다. 이 둘은 아주 유사한 자료구조이지만, element가 제거되는 방식에 차이가 있다.

 

- 스택 : 스택은 흔히 아는 자바스크립트 엔진에서의 콜 스택이 제거되는 방식과 동일하다. 마지막으로 삽입된 element가 가장 먼저 제거되는 방식을 취한다. LIFO(Last In, First Out)인 것이다. 따라서 스택은 브라우저 히스토리(이전 페이지, 다음 페이지) 또는 ctrl+z로 이전 작업을 취소하는 등의 동작에 쓰이는 자료구조이다.

 

- 큐 : 큐는 맛집에 들어가려고 기다리는 대기줄이라고 생각하면 쉽다. 먼저 도착한 사람이 먼저 입장하는 FIFO(First In, First Out) 개념이다. 따라서 레스토랑 앱, 예매 앱, 우버 앱 등에서 큐를 주요한 자료구조로 사용할 것이다. 

 

스택과 큐는 자바스크립트에 내장되어 있지 않으므로, 사용을 원하면 스스로 구조를 만들어야 한다. 구조를 만들 때, array와 linked list 중 어떤 것을 활용해서 구조를 만드는 것이 효율적일까?

 

- 스택 : array와 linked list 모두 크게 상관은 없다.

  1) array의 장점 : 각 element들이 서로 연관되어 있기 때문에 속도가 더 빠르다. 하지만 메모리 공간이 한정되어 있기 때문에 할당된 메모리를 다 사용하면 현재 배열을 다른 곳에 복사하기 때문에 메모리를 조금 더 사용하게 될 수도 있다.

  2) Linked List의 장점 : 메모리 여기저기에 흩어져있기 때문에 상대적으로 느릴 수 있다. 하지만 반면 메모리 공간이 한정되어 있지 않고 얼마든지 계속 값을 추가할 수 있다는 장점이 있다.

 

- 큐 : array로 만들면 좋지 않다. 앞서 배웠지만 Array의 경우 앞에서부터 element를 제거해야 하는데, 그 경우 index를 다시 재조정해야 하기 때문에 O(n)이 된다. 따라서 Queue는 반드시 Linked List로 만든다.

2. Stack 메소드 구현

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

class Stack {
  constructor(){
    this.top = null;
    this.bottom = null;
    this.length = 0;
  }
  peek() {
    // stack에 쌓인 가장 마지막 녀석을 확인하는 메소드
    return this.top;
  }
  push(value){
    const newNode = new Node(value);
    
    if (this.length === 0) {
      this.top = newNode;
      this.bottom = newNode;
    } else {
      const holdingPointer = this.top;
      this.top = newNode;
      this.top.next = holdingPointer;
    }
    this.length++;
    return this;
  }
  pop(){
    if (!this.top) return null;
    if (this.top === this.bottom) {
      this.bottom = null;
    }
    this.top = this.top.next;
    this.length--;
    return this;
  }
  //isEmpty
}

const myStack = new Stack();
console.log(myStack);
myStack.peek();
myStack.push('google');
myStack.push('facebook');
myStack.push('udemy');
myStack.pop();
myStack.pop();
myStack.pop();

 

3. Queue 메소드 구현

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

class Queue {
  constructor(){
    this.first = null;
    this.last = null;
    this.length = 0;
  }
  peek() {
    return this.first;
  }
  enqueue(value){
    const newNode = new Node(value);
    if (this.length === 0) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    this.length++;
    return this;
  }
  dequeue(){
    if(!this.first) {
      return null;
    }
    if (this.first === this.last) {
      this.last = null;
    }
    const holdingPointer = this.first;
    this.first = this.first.next;
    this.length--;
    return this;
  }
  //isEmpty;
}

const myQueue = new Queue();
myQueue.enqueue('Joy');
myQueue.enqueue('Matt');
myQueue.enqueue('Pavel');
myQueue.enqueue('hyunsol');


//Joy
//Matt
//Pavel
//Samir

 

4. 결론

- 장점 : Fast Operation(removing, pushing), Fast Peek, Ordered

- 단점 : Slow Lookup