[자료구조] 스택-큐

1. 스택과 큐

스택 : 후입선출 - 나중에 들어온것이 먼저 나간다.

큐 : 선입선출 - 먼저 들어온것이 먼저 나간다.

배열을 이용하여 구현한다면 스택은 배열의 기본 메소드 push와 pop을 이용하면 시간 복잡도 O(1)로 처리할 수 있지만

큐는 push, shift 또는 unshift, pop 을 이용하기 때문에 시간복잡도 O(n)이다.

자료구조를 직접 만들어 사용한다면 큐의 시간복잡도를 O(1)로 낮출수 있다.

2. 스택

(1) 클래스 및 노드

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

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

(2) push

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

(3) pop

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

3. 스택의 빅O

insertion(삽입)	removal(제거)	searching(탐색)	access(접근)
O(1)	O(1)	O(n)	O(n)

4. 큐

(1) 큐의 사용처 예시

  - 게임 로딩대기시 먼저 로딩에 들어간사람 들여보내주기

  - 여러개 파일 다운로드시 먼저 다운로드 클릭한것부터 다운로드 하기

  - 프린트할때 먼저 출력한것부터 먼저 나오게 하기

(2) 클래스 및 노드

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

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
}

(3) enqueue

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

(4) dequeue

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

5. 큐의 빅O

insertion(삽입)	removal(제거)	searching(탐색)	access(접근)
O(1)	O(1)	O(n)	O(n)