Stacks
1. 후입 선출(LIFO)의 특성을 가지는 데이터 구조
2. 마지막으로 들어온 값은 언제나 먼저 나가게 된다.
3. 함수의 호출스택, 실행취소 및 다시실행, 브라우저의 접속 기록을 추적하는 경우 등 다양한 곳에서 쓰인다.

Queues
1. 선입 선출(FIFO)의 특성을 가지는 데이터 구조
2. 처음으로 들어온 값이 언제나 가장 먼저 나가게 된다.
3. 온라인 게임 접속대기, 백그라운드 작업, 업로드 작업, 프린트 대기열 등 다양한 곳에서 쓰인다.

Class로 스택 구현하기

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;
  }
}

Class로 큐 구현하기

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
  enqueue(val) {
    let newNode = new Node(val);
    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    return ++this.size;
  }
  dequeue() {
    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;
  }
}

스택과 큐의 BigO

Insertion : O(1)
Removal : O(1)
Searching : O(N)
Access : O(N)