스택(Stack)

스택은 쌓다라는 의미를 가진, 데이터가 쌓인 형태의 자료구조이다.

후입선출(LIFO) 구조를 기본으로 하고 있기에,  가장 마지막에 삽입된 데이터가 가장 먼저 삭제된다.

스택은 정해진 방향(top)으로만 데이터가 쌓이게 된다. 물론 데이터에 접근할 때도 마찬가지로 정해진 방향으로만 접근할 수 있다. 삭제도 마찬가지이다.

Push는 삽입, Pop은 삭제를 의미한다.

스택(Stack)의 시간복잡도

삽입 (Inertion)	O(1)
삭제 (Deletion)	O(1)
검색 (Search)	O(n)

💻 자바스크립트 스택(Stack) 구현

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

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

  push(value) {
    let newNode = new Node(value);
    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    } else {
      let tmp = this.first;
      this.first = newNode;
      this.first.next = tmp;
    }
    return ++this.size;
  }

  pop() {
    if (!this.first) return null;
    let tmp = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return tmp.value;
  }

  print() {
    let current = this.first;

    while (current) {
      console.log(current.value);
      current = current.next;
    }
  }
}

const stack = new Stack();
stack.push(0);
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop();
stack.print();

/**
2
1
0
*/

배열에서 사용할 수 있는 .push() / .pop() 메소드를 통해 스택처럼 사용할 수 있지만,

배열의 한계점으로 인해 연결리스트로 구현한다.

큐(Queue)

큐는 스택과 반대로, 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO) 구조의 자료구조이다.

삽입연산(Enqueue)이 일어나는 곳은 Back(혹은 Rear),

삭제연산(Dequeue)이 일어나는 곳은 Front라고 한다.

큐(Queue)의 시간복잡도

삽입 (Inertion)	O(1)
삭제 (Deletion)	O(1)
검색 (Search)	O(n)

스택과 동일하다.

💻 자바스크립트 큐(Queue) 구현

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

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
  enqueue(value) {
    let newNode = new Node(value);
    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;
  }
  print() {
    let current = this.first;

    while (current) {
      console.log(current.value);
      current = current.next;
    }
  }
}

const queue = new Queue();
queue.enqueue(0);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.dequeue();
queue.print();

/**
1
2
3
4
*/

Reference

[자료구조] 스택(Stack)과 큐(Queue)에 대해서 알아보자!

[Javascript] Stack, Queue / Javascript Queue 구현해야 하는 이유