스택과 큐의 구현 방식과 시간 복잡도

자바스크립트로 자료구조에 대해 공부하다 스택(Stack)을 배열로 구현하고 큐(Queue)도 똑같이 배열로 구현했을 때 큐의 시간복잡도가 늘어나는 것을 보고 이유를 찾게 되었다.

자바스크립트엔 스택과 큐가 따로 내장되어 있지 않기 때문에 배열과 내장함수들을 이용하여 스택과 큐를 흉내내어 만드는데 배열로 스택과 큐를 구현하였을 때 element가 제거되는 방식에서 사용되는 두 내장함수 Array.prototype.pop() 과 Array.prototype.shift()의 차이에 의해 시간 복잡도가 달라진다.

그래서 시간 복잡도를 이해하고 스택과 큐에 적용하기 위해서는 스택과 큐의 구현 방식인 배열(Array) 방식과 연결리스트(Linked List) 방식의 차이를 이해해야 한다.

---

📌 스택(Stack)

• LIFO(Last In, Last Out)를 원칙으로 하는 자료구조다.

속성

• top : 스택 맨 위의 아이템

메소드

• push : 스택의 맨 위에 아이템을 삽입한다
• pop : 스택 맨 위의 아이템을 제거하고 및 그 아이템을 반환한다
• contains : 해당 아이템이 스택에 존재하는지 확인한다
• size : 현재 스택에 있는 아이템의 총 개수를 반환한다

스택 (Stack) 사용 사례

• 재귀 알고리즘
• 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
• 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
• 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
• 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
• 웹 브라우저 방문기록 (뒤로가기)
• 실행 취소 (undo)
• 역순 문자열 만들기
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
  Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
• 후위 표기법 계산

배열로 스택(Stack) 구현

처음 문제를 풀 때는 무작정 if문을 사용하여 구현하였는데 스택을 이해하고 클래스로 구현하니 코드가 더 쉽게 이해가 된다.

class Stack {
  constructor() {
    this.items = [];
  }

  push(item) {
    this.items.push(item);
  }

  pop() {
    return this.items.pop();
  }
  
  // pop과 달리 아이템은 유지한 채 값만 받아온다.
  peek() {
    if (this.items.length === 0) {
      return null;
    }
    return this.items[this.items.length - 1];
  }

  getSize() {
    return this.items.length;
  }

  isEmpty() {
    return this.getSize() === 0;
  }
}

연결리스트로 스택(Stack) 구현

연결리스트로 구현하니 size를 어떻게 가져올지 고민이었다. 결국 stack에 index 변수를 담아 관리하기로 했다. 연결리스트에 대한 개념은 이해했으나 구상이 제대로 되지 않았는데 스택을 이해하고 이를 연결리스트로 구현하니 머릿속에서 좀 더 구체화가 된 것 같다.

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

class Stack {
  constructor() {
    this.top = null
    this.index = 0;
  }

  isEmpty() {
    return this.top === null;
  }

  push(data) {
    // ex) data = 13
    const newNode = new Node(data);
    // newNode.data = 13, newNode.next = null
    newNode.next = this.top;
    // stack.top = newNode {data : 13, next = null}
    this.top = newNode;
    this.index++ ;
  }

  pop() {    
    if (this.isEmpty()) return;
    let re = this.top
    this.top = this.top.next;
    this.index-- ;
    return re.data
  }

  peek() {
    if (this.isEmpty()) return false;
    return this.top.data;
  }

  size(){
    return this.index;
  }
}

두 방식의 시간 복잡도 차이

스택에서는 배열과 연결리스트에서 시간 복잡도 차이는 크게 생기지 않는다. 그 이유는 둘 다 최상단의 데이터를 삽입, 삭제하며 관리하기 때문에 모두 O(1)의 시간 복잡도를 갖는다. 하지만 큐에서는 두 방식에서 시간 복잡도의 차이가 발생한다.

---

📌 큐(Queue)

• FIFO(First In, First Out)을 원칙으로 하는 자료구조다.

속성

• first : 큐 맨 앞의 아이템

메소드

• dequeue : 큐 맨 앞의 아이템을 제거하고 및 그 아이템을 반환한다
• enqueue : 큐에 아이템을 추가한다
• contains : 해당 아이템이 큐에 존재하는지 확인한다
• size : 현재 큐에 있는 아이템의 총 개수를 반환한다

큐 (Queue) 사용 사례

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다.
• 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
• 노드를 접근한 순서대로 처리할 수 있다.
• 캐시(Cache) 구현
• 우선순위가 같은 작업 예약 (인쇄 대기열)
• 선입선출이 필요한 대기열 (티켓 카운터)
• 콜센터 고객 대기시간
• 프린터의 출력 처리
• 윈도 시스템의 메시지 처리기
• 프로세스 관리

배열로 큐(Queue) 구현

스택과 다른점은 가장 앞에 있는 element를 추출하기 위해 pop() 대신 shift() 메서드를 사용한다는 것이다. shift()는 가장 앞에 있는 요소를 추출하고 나머지 요소들을 앞으로 당겨줘야하기 때문에 O(n)의 시간복잡도를 갖게 된다. 그래서 시간복잡도를 O(1)로 하기 위해 연결리스트 방식을 사용해야 정석적인 큐(Queue)를 만들 수 있다.

export default class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    return this.items.shift();
  }

  peek() {
    return this.items[0];
  }

  getSize() {
    return this.items.length;
  }

  isEmpty() {
    return this.getSize() === 0;
  }
}

연결리스트로 큐(Queue) 구현

연결리스트로 큐를 구현하여 element를 추출하는 과정에서 shift() 메서드를 사용하지 않아 시간복잡도 O(1)을 구현할 수 있다.

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

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.index = 0;
  }

  isEmpty() {
    return this.front == null && this.rear === null;
  }
  insert(data) {
    const newNode = new Node(data);
    if (this.isEmpty()) this.front = newNode;
    else this.rear.next = newNode;

    this.rear = newNode;
    this.index++;
  }

  remove() {
    if (this.isEmpty()) return;
    this.front = this.front.next;
    if (!this.front) this.rear = null;
    this.index--;
  }

  peekFront() {
    if (this.isEmpty()) return false;
    return this.front.data;
  }
  
  size(){
  	return this.index;
  }
}

두 방식의 시간 복잡도 차이

위에서 계속 언급했던 것처럼 shift() 메서드를 사용하면 뒤 요소들을 앞으로 당겨줘야 하기 때문에 시간복잡도가 O(n)이 되지만 연결리스트로 큐를 구현하면 가장 앞에 있는 요소만 제거하면 되기 때문에 O(1)의 시간복잡도를 갖는다.

---

마무리

여러 가지 자료구조 중 스택과 큐에 대하여 알아보았는데 처음 개념 공부를 하고 문제를 풀 때는 어떻게 문제에 적용할지 어려웠는데 문제를 먼저 풀어서도 있겠지만 개념을 클래스로 구현하여 다시 정리해보니 확실히 이해가 더 된 느낌이다.