CS) 자바스크립트로 Stack,Queue 자료구조 구현하기

김명성·2023년 7월 13일

Stack과 Queue

Stack과 Queue는 주로 임시데이터를 저장하는 목적으로 사용되는 자료구조이다.
Stack은 후입선출(LILO), Queue는 선입선출(FIFO)의 자료구조이다.
Stack과 Queue는 자바스크립트의 데이터 구조에 내장되어 있지 않지만, Singly-Linked-List의 개념으로 직접 구현할 수 있다.

왜 배열로 구현하지 않고 Singly-Linked-List 개념을 사용하나요?
Stack은 자바스크립트의 배열로 구현할 때 push(),pop() 메서드를 사용하면 쉽게 구현할 수 있다.
하지만 Queue와 같은 경우는 shift() 또는 unshift() 메서드를 사용해야 구현이 가능하고, 해당 메서드를 사용한다면 전체 배열을 다시 인덱싱하게 되어 O(N)의 시간복잡도를 갖게 되며, 원래의 자료구조 Stack, Queue의 빠른 시간복잡도 O(1)을 갖게 되지 못하게 된다.

인덱싱(Indexing)
빠진 값의 자리를 메꾸기 위해 요소들이 왼쪽으로 한칸씩 움직여 순서를 맞추는 것.

Singly-Linked-List (단일 연결 리스트)

Singly-Linked-List란 데이터를 연결된 Node들의 집합으로 나타내는 자료구조이다.
구현에 필요한 Node는 아래의 2가지 개념으로 구성되어 있다.

데이터(실제 값)
다음 Node를 가리키는 포인터(Next)

첫 번째 Node는 연결 리스트의 시작점을 가리키는 Node로 Head라고 불린다.
마지막 Node는 다음 Node를 가리키는 포인터가 null로 설정되어 연결 리스트의 끝을 나타낸다.

Singly-Linked-List는 특정 위치의 요소에 직접 접근하기 위해서는 전체 리스트를 순차적으로 탐색해야 하는 단점이 있지만 데이터 삽입 및 삭제 작업이 상대적으로 빠르기에 Stack과 Queue를 구현할 때에는 온전히 Singly-Linked-List의 장점에 의존할 수 있다.

Singly-Linked-List의 구현도

 Node 1      Node 2      Node 3      Node 4
+------+    +------+    +------+    +------+
| Data |    | Data |    | Data |    | Data |
+------+    +------+    +------+    +------+
| Next |--> | Next |--> | Next |--> | Null |
+------+    +------+    +------+    +------+

구현

1. Stack과 Queue 구현에서 공통으로 사용되는 Node Class 작성

Node Class는 Singly-Linked-List의 개념으로 구현하기에 Node는 값과 포인터로 구성되어 있어야 한다.

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

2. Stack

조금 혼동이 올 수 있겠지만 next는 previous node라고 기억하면 이해하기 편하다.
다음 노드를 가리키는 포인터 next는 Stack에서는 직전 노드를 가리키고 있기 때문이다.

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

  // 스택이 비어있는지 확인하는 isEmpty 메서드
  isEmpty() {
    return this.top === null;
  }
  
  // 요소를 스택의 최상단에 추가하는 push 메서드
  push(value) {
    const node = new Node(value); // { data: value, next: null }인 Node 인스턴스 생성
    node.next = this.top; // 처음 push되는 node의 next는 null, 이후 직전에 push된 node가 현재 push되는 node의 next에 할당된다.
    this.top = node; // 해당 Stack의 top에는 가장 최근에 Push된 인스턴스가 할당된다.
  }

  // 스택의 최상위 요소를 제거하고 제거된 값을 반환하는 pop 메서드
  pop() {
    if (this.isEmpty()) {
      return "this stack is empty";
    }

    const removedNode = this.top; // 반환을 위한 temp value.
    this.top = this.top.next; // 위에서 설명했듯이 next는 곧 previous node이다.
    return removedNode.value;
  }

  // 스택의 최상위 요소를 반환하는 peek 메서드
  peek() {
    if (this.isEmpty()) {
      return "this stack is empty";
    }
    return this.top.data;
  }

  // 스택의 요소 개수를 반환하는 size 메서드. 시간복잡도 O(N)을 갖는다. 
  size() {
    let count = 0;
    let current = this.top;

    while (current !== null) {
      count++;
      current = current.next;
    }

    return count;
  }

  // 스택을 초기화하는 clear 메서드. Link를 끊음으로 스택을 비울 수 있다.
  clear() {
    this.top = null;
  }
}

// 스택 사용 예시
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.peek()); // 3
console.log(stack.pop()); // 3
console.log(stack.size()); // 2
console.log(stack.isEmpty()); // false
stack.clear();
console.log(stack.isEmpty()); // true

3. Queue

Stack에서는 top을 프로퍼티로 갖고 있었다면, Queue에서는 head와 tail을 갖는다.


class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  
  
  // 큐가 비어있는지 확인하는 isEmpty 메서드
  isEmpty() {
    return this.head === null;
  }

  // 요소를 큐의 뒤쪽에 추가하는 enqueue 메서드
  enqueue(value) {
    const node = new Node(value);

    if (this.isEmpty()) {
      this.head = node; // Queue가 비어있다면 현재 enqueue되는 node가 head 할당된다.
      this.tail = node; 
    } else {
      this.tail.next = node; // Queue가 비어있지 않다면 현재 enqueue되는 node가 tail.next에 할당된다.
      this.tail = node;
    }
  }

  // 큐의 맨 앞 요소를 제거하고 반환하는 dequeue 메서드
  dequeue() {
    if (this.isEmpty()) {
      return "this queue is empty";
    }

    const removedNode = this.head; // temp value
    this.head = this.head.next;

    if (this.head === null) {
      this.tail = null;
    }

    return removedNode.data;
  }

  // 큐의 맨 앞 요소를 반환하는 front 메서드
  front() {
    if (this.isEmpty()) {
      return "this queue is empty";
    }
    return this.head.data;
  }


  // 큐의 요소 개수를 반환하는 size 메서드. 시간복잡도 O(N)을 갖는다.
  size() {
    let count = 0;
    let current = this.head;

    while (current !== null) {
      count++;
      current = current.next;
    }

    return count;
  }

  // 큐를 초기화하는 clear 메서드. 
  clear() {
    this.head = null;
    this.tail = null;
  }
}

// 큐 사용 예시
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.front()); // 1
console.log(queue.dequeue()); // 1
console.log(queue.size()); // 2
console.log(queue.isEmpty()); // false
queue.clear();
console.log(queue.isEmpty()); // true