ADT

어떤 데이터의 구체적인 구현 방식은 생략하고, 데이터의 추상적 형태와 그 데이터를 다루는 방법만 정의한 것을 ADT(Abstract Data Type), 추상 자료형이라고 합니당

ADT 중 대표적인 Stack과 Queue가 뭔지 알아봅시당

---

Stack

Stack이 뭥미?

재미있는 표현이 있어서 빌려보자면,

우리 가끔 먹는 프링글스 과자 있잖아요

그게 Stack임

무슨 소리냐면

프링글스 과자 꺼내 먹을 때, 맨 위에 있는 것 부터 하나 씩 꺼내먹죠? 냠냠
맨 위에 것을 먹어야 다음 감자칩을 먹을 수 있자나여

굳이 다 뒤집어 엎어서 맨 아래 것 부터 먹는 사람은 없을 듯

이걸보고 우리는 후입선출 (LIFO, Last In First Out) 자료구조 라고 합니다

즉, 마지막으로 추가된 요소가 제일 먼저 제거된다는 뜻임

위 그림에서 보듯이 push, pop 메서드를 사용하여 Stack 자료구조를 만들 수 있습니다.

---

Stack 기본 구조

기본 구조는 Node 클래스를 활용하고, Stack Class의 constructor에서는 first, last, size 프로퍼티를 둡니다.

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

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

그리고 Stack에 넣고 빼는, push, pop 메서드는 O(1) 시간복잡도를 갖는 shift, unshift 메서드를 활용함
따지고 보면 리스트 제일 앞에 추가하고, 제일 앞의 것을 제거하는 것이지만, 결과적으로는 Stack 자료 구조입니다

공간적으로 중요한 것이 아니라, 시간적으로 마지막에 추가한 요소를 제일 먼저 제거하는것과 다르지 않기 때문임

Stack의 성능 - 시간복잡도

• 삽입 : O(1)
• 제거 : O(1)
• 탐색 : O(N)
• 접근 : O(N)

push

unshift 로직을 활용합니다.

  push(val) {
    const newNode = new Node(val);
    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    } else {
      const temp = this.first;
      this.first = newNode;
      this.first.next = temp;
    }
    return ++this.size;
  }

pop

shift 로직을 활용합니다.

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

쉽게 만들면 대충 이렇다

var stack = [];

stack.push(2);       // stack is now [2]
stack.push(5);       // stack is now [2, 5]

var i = stack.pop(); // stack is now [2]

alert(i);            // console.log(i);

---

Stack 현실에선 언제 쓸까?

우리 콤푸타 만지다가 뭐 잘못 누르면 어케 되돌립니까
ctrl + z 누르지 않나여

가장 마지막에 실행한 동작을 첫 번째 만큼 되돌려줘

이것도 따지고 보면 Stack일 듯

이런거 몇 개 더 찾아보면

1. 웹 브라우저 방문 기록 (뒤로 가기)
2. 실행 취소 (Undo)
3. 역순 문자열 만들기
4. 후위 표기법 계산
5. 함수 호출의 Call Stack

여러 작업을 연달아 수행하면서, 이전의 작업 내용을 저장해 둘 필요가 있을 때 사용됩니당

---

Queue

Queue가 뭥미?

큐(Queue)는 스택이랑 아주아주 비슷함

얘도 자료구조로써 데이터를 추가하고 제거함, 근데 순서가 다름

위에 사진 보면, 대기줄로 번역이 됩니당.

우리 스타벅스가서 주문하려면, 먼저 온 사람부터 주문 받아주잖아용

그거처럼 먼저 들어온 것 부터 먼저 나가는,

선입선출 (FIFO, First In First Out) 자료구조 라고 합니당

---

Queue 기본 구조

기본적으로 Stack과 유사하지만, 데이터를 추가할 때마다, 인덱스를 다시 부여해야하므로, 성능이 나빠질 듯

성능을 신경써야 한다면, 직접 Queue Class를 정의하는 것이 좋아용

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

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

enqueue

push와 같이 Node를 가장 뒤에 추가한다.
시간복잡도 O(1)

  enqueue(val) {
    const 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

shift와 같이 가장 앞의 Node를 제거하고 반환함
시간복잡도 O(1)

  dequeue() {
    if (!this.first) return null;

    const temp = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return temp.value;
  }

Queue의 성능 - 시간복잡도

• 삽입 : O(1)
• 제거 : O(1)
• 탐색 : O(N)
• 접근 : O(N)

---

Queue 현실에선 언제 쓸까?

1. 은행 업무
2. 대기열 순서와 같은 우선순위 작업 예약 등
3. 대기 시간
4. 프로세스 관리

Queue는 순서대로 처리해야 하는 작업을 임시로 저장하는 버퍼(Buffer)로 많이 사용됨