[JavaScript 자료구조] Stack & Queue

Main·2023년 8월 24일

Stack ?

스택은 데이터를 일시적으로 저장하거나 처리 순서를 관리하기 위해 사용됩니다.

스택은 데이터를 일렬 나열 하여 데이터의 추가와 제거가 한쪽 끝에서만 이루어지는 구조입니다.

스택은 LIFO(Last In Fisrt Out, 후입선출) 자료구조로 마지막으로 추가된 요소가 제일 먼저 제거됩니다.

JavaScript callStack 또한 stack 알고리즘 기반으로 동작합니다.

배열에서 push 메서드와 pop 메서드를 사용하여 스택 자료구조를 만들 수 있습니다.

별도의 자신만의 스택 자료구조를 만들 수도 있습니다.

Stack의 주요 연산

Push: 스택의 꼭대기에 데이터를 추가합니다.
Pop: 스택의 꼭대기에서 데이터를 제거하고 반환합니다.
Peek : 스택의 꼭대기에 위치한 데이터를 반환하지만 제거하지는 않습니다.
IsEmpty: 스택이 비어있는지 여부를 확인합니다.
Size: 스택에 저장된 데이터의 개수를 반환합니다.

JavaScript로 Stack 구현하기

1. 배열을 메서드를 활용하여 구현

export default class Stack {
  constructor() {
    // item들을 받을 배열 생성
    this.items = [];
  }
  
  push(item) {
    this.items.push(item);
  }

  pop() {
    if(this.items.length===0) return null;
    return this.items.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;
  }
}

2. Node 연결리스트를 활용하여 구현

Node 연결리스트를 활용하여 구조를 구성합니다.
Node 연결리스트는 연결 리스트(Linked List)는 데이터 요소들을 노드(Node)라 불리는 객체로 구성하며, 이들 노드가 선형적으로 연결되어 있는 자료구조입니다.
Node에는 현재 자신의 값과 다음 노드를 가르키는 next가 존재합니다.

Node 연결리스트 구조 코드

const node = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: {
          value: 5,
          next: null
        }
      }
    }
  }
};

function printNodeList(node) {
  let output = '';

  while (node !== null) {
    output += node.value;
    if (node.next !== null) {
      output += ' => ';
    }
    node = node.next;
  }

  console.log(output);
}

printNodeList(node);

Node 연결리스트를 활용한 구현 코드

// 노드 클래스 생성
class Node {
  constructor(value) {
    // 인자로 받은 값을 저장
    this.value = value;
    // 다음 노드를 가르킴
    this.next = null;
  }
}

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

  push(data) {
    const newNode = new Node(data);
    newNode.next = this.top;
    this.top = newNode;
    this.size++;
  }

  pop() {
    if(this.top===null) return null;
    const removeNode = this.top;
    this.top = this.top.next;
    this.size--;
    return removeNode.value;
  }

  peek() {
    if(this.top===null) return null;
    return this.top.value;
  }

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

Queue ?

큐는 자료구조로서 데이터를 일시적으로 저장하거나 처리 순서를 관리하기 위해 사용됩니다.

큐는 FIFO(First In First Out, 선입선출) 구조로 먼저 들어온 데이터가 먼저 처리되는 구조입니다.

배열을 활용한다면, unshift와 pop 메서드나 push와 shift 메서드 조합을 사용하는 것이 큐의 작동방식과 같습니다. 하지만 unshift 메서드를 써서 데이터를 추가할 때마다 전체 배열에 인덱스를 다시 부여해야 하므로 시간복잡도가 O(n)이 됩니다. 따라서 성능이 떨어질 수 있다는 단점이 존재합니다.

성능을 신경써야 하는 경우라면, 직접 큐 클래스를 만드는 것이 좋습니다. Node 연결리스트를 활용하여 큐 클래스를 구현하면 시간복잡도를 O(1)로 줄여 성능을 향상 시킬 수 있습니다.

Queue의 주요 연산

Enqueue : 큐의 맨 뒤에 데이터를 추가하는 작업입니다. 새로운 데이터가 큐의 뒤로 들어가게 됩니다.
Dequeue : 큐의 맨 앞에서 데이터를 제거하는 작업입니다. 가장 먼저 들어온 데이터가 제거됩니다.
getFront: 큐의 맨 앞에 있는 데이터를 조회합니다.
getRear : 큐의 맨 뒤에 있는 데이터를 조회합니다.
IsEmpty : 큐가 비어있는지 여부를 확인합니다.
getSize : 큐에 저장된 데이터의 개수를 확인합니다.

Queue 구현 방법

1. 배열을 이용한 Queue 구현

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

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

  dequeue() {
    if(this.items.length===0) return null;
    return this.items.shift();
  }
  

  getFront() {
    if (this.items.length===0) {
      return null;
    }
    return this.items[0];
  }
  
  getRear() {
     if (this.items.length===0) {
      return null;
    }
  	return this.items[this.items.length-1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

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

2. Node 연결리스트를 활용한 방법

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

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

  enqueue(item) {
    const newNode = new Node(item);
    if (this.rear === null) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
    this.size++;
  }

  dequeue() {
    if (this.front === null) {
      return null;
    }
    const removedNode = this.front;
    this.front = this.front.next;
    if (this.front === null) {
      this.rear = null;
    }
    this.size--;
    return removedNode.data;
  }
  
  getFront() {
    if (this.front === null) {
      this.rear = null;
    }
    return this.front.data;
  }
  
  getRear() {
    if (this.front === null) {
      this.rear = null;
    }
  	return this.rear.data;
  }

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

  getSize() {
    return this.size;
  }
}

정리

Stack과 Queue 자료구조는 스택은 데이터를 일시적으로 저장하거나 처리 순서를 관리하기 위해 사용됩니다. Stack과 Queue의 차이점은 데이터 처리구조에 있습니다.
Stack의 경우 LIFO(Last In Fist Out, 후입선출) Queue의 경우 FIFO(First In First Out, 선입선출)의 구조로 데이터가 처리됩니다.

Stack과 Queue를 JavaScript 구현하는 방법으로는 배열 메서드를 통해 구현하는 방법과 Node 연결리스트로 구현하는 방법이 있습니다.

Queue의 경우 배열 메서드의 unShift()로 인해 시간 복잡도가 O(n)되어 효율이 떨어질 수 있으므로, 시간 복잡도가 O(1)인 Node 연결리스트로 구현하는 것이 효율적인 코드를 작성할 수 있습니다.