Udemy - 스택&큐

스택(Stack)

후입선출법을 따르는 LIFO(Last In, First Out) 자료구조다.
⇒ 나중에 들어온 것이 먼저 나간다는 뜻이다.

LIFO와 FIFO의 차이

필자도 처음엔 조금 헷갈렸는데, 편의점 알바생을 기준으로 생각을 해보니 이해하기가 쉬웠다.

대부분의 편의점 알바생들은 음료 냉장고 뒤로 가서 음료수를 채워 넣는다. 이런 방식으로 음료수를 채워 넣으면 먼저 넣은 음료수일수록 (들어간 순서가 빠른) 가장 먼저 손님들에게 팔리게 된다.

반대로, LIFO의 경우는 냉장고 뒤가 아닌 앞에서 음료를 채워 넣는 알바생을 떠올리면 된다. 이럴 경우 가장 마지막에 넣은 음료가 냉장고에서 가장 앞에 진열되게 된다. 따라서 이럴 때에는 늦게 넣은 음료수일수록 손님들에게 빨리 팔리게 되는 것이다.

다시, 스택은 LIFO 자료구조다

즉, 스택은 냉장고 앞에서 음료수를 집어넣는 방식을 따르는 자료구조라고 할 수 있다.

단일 연결 리스트로 예를 들면, 위의 예시와 같이 나중에 삽입된 노드가 먼저 탐색 또는 제거되는 경우라고 보면 될 것이다.

이를 배열로 예를 다시 들면, shift()와 unshift()만을 활용하여 배열 요소의 삽입과 제거를 하는 것 또한 스택을 배열로 구현한 것이라고 볼 수 있을 것이다.

스택 자료구조는 어떻게 만들고 활용할까

스택은 undo/redo, 라우팅 등에 사용되며, 트리 또는 그래프 등에 활용된다.
연결 리스트 또는 배열로 만들어 활용할 수 있다.

단일 연결 리스트로 만들어본 stack

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

class Stack {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  push(val) {
    const newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    return ++this.length;
  }
  pop() {
    if (!this.head) return null;
    // 만약 하나의 노드만 남아있는 상황이라면?
    if (this.head === this.tail) {
      // 우선 tail을 제거해준다.
      this.tail = null;
    }
    // 그리고 head를 변경해주는데,
    // 만약 위의 조건식에 해당하지 않는다면 앞에서 두 번째 노드가 새로운 헤드가 된다.
    // 하지만, 위 조건식에 해당한다면, head 또한 null이 된다. (노드가 하나일 때는 next가 null일 것이기 때문)
    this.head = this.head.next;
    return --this.length;
  }
}

이렇게 단일 연결 리스트로 스택을 구현해 보았는데, 이 때에는 push와 pop이 마치 shift와 unshift처럼 동작하게 된다.

stack의 시간 복잡도

메소드	시간 복잡도
push(insert)	O(1)
pop(remove)	O(1)
탐색 및 접근	O(N)

stack은 배열과 비교했을 때, shift와 unshift가 O(1)의 시간복잡도를 갖기에,
만약 리스트의 맨 앞의 요소들을 추가 및 삭제할 일이 많다면 스택을 활용하는 것이 효율적일 것이다.

---

큐(Queue)

큐는 스택과 반대로 **선입선출법(FIFO)**을 따르는 자료구조이다.

위의 편의점 냉장고 예시에서 더 나아가, 정말 쉽게 FIFO를 직관적으로 이해할 수 있는 방법이 있다.

바로 “줄 서기“이다.

위의 그림에서 볼 수 있듯이, 우리의 일상은 대부분이 FIFO로 이루어진다. 먼저 줄을 선 사람이 먼저 계산을 하고, 우선순위를 갖는 것 처럼 말이다. 그리고 이는 컴퓨터 또한 익숙해 하는 방식이다. 만약 학교 도서관에서 공용 프린터기를 사용하는데, 먼저 프린트를 요청한 사람보다 나중에 프린트를 요청한 사람의 프린트가 먼저 된다면 옳은 것일까?

이처럼 FIFO는 어쩌면 우리에게 더 친숙한 방식일 지 모른다.

큐(Queue)는 어떻게 활용되는가?

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  // enque는 단일 연결 리스트에서 작성했던 push와 동일하다
  enque(val) {
    const newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    return ++this.length;
  }
  // deque는 unshift와 같은 기능을 하기 때문에 위의 스택에서의 pop과 동일하다.
  deque() {
    if (!this.head) return null;
    if (this.head === this.tail) {
      this.tail = null;
    }
    this.head = this.head.next;
    return --this.length;
  }
}

큐의 시간복잡도

stack과 동일하다!

---