Stack & Queue 자료구조

Stack

데이터의 모음이 되는 자료 구조중의 하나로서 단순하게 LIFO, Last In Last Out(후입선출)의 특징을 가진 자료구조이며 여러한 곳에서 사용된다. 예를들면 자바스크립트에서 재귀함수 호출시, Undo와 같이 이전 작업으로 되돌릴때, 인터넷 브라우저의 방문기록을 쌓고 뒤로가기를 사용할때 혹은 트리나 그래프같은 알고리즘의 중간 매개체로도 사용된다.

 

 

배열을 이용한 Stack

push()와 pop() 혹은 shift()와 unshift()의 조합을 이용하여 배열을 스택으로 사용할수 있지만 배열의 특성상 shift()와 unshift()의 경우 배열안의 아이템들의 인덱스를 모두 바꿔주는 작업이 생기므로 push()와 pop()을 이용한다.

 

 

Linked list를 이용한 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) {
    let newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this.length;
  }

  pop() {
    if (!this.head) return null;
    if (this.head === this.tail) this.tail = null;
    let currentNode = this.head;
    this.head = currentNode.next;
    this.length--;
    return currentNode.val;
  }
}

const stack = new Stack();

링크 리스트의 경우 마지막노드를 삭제할 경우 이전노드의 값을 알아야 하기에 위의 코드와 같이 리스트의 head부터 LIFO 과정이 진행된다. 삽입 메소드의 경우 리스트의 head부터 시작하며 삭제 메소드 또한 리스트의 head부터 삭제된다.

 

 

Stack의 Big O notation

삽입과 제거의 시간복잡도는 O(1)이며 탐색과 접근은 O(n)이다.

스택의 Big O notaion 중 제일 중요한것은 삽입과 제거 작업이다. 그로 인해서 배열을 이용할 경우 shift()와 unshift()를 사용하지않고 push()와 pop()이 사용된다.

 

탐색과 접근은 스택형 자료구조에서 그렇게 중요하지 않으며 만약 탐색과 접근이 중요한 경우 배열이나 다른 데이터 구조를 사용한다.

 

 

 

Queue

스택과 다르게 FIFO, First In First Out(선입선출)의 성질을 가진 자료구조이다.

게임에서의 접속대기, 무언가를 업로드하거나 다운로드 하는경우 첫번째 파일이 먼저 처리되도록 하는 시스템, 프린터의 대기열도 이 자료구조를 사용하며 데이터를 추가하는작업을 Enqueue, 삭제하는 작업을 Dequeue라고 한다.

 

 

배열을 이용한 Queue

배열을 이용하여 Queue형 자료구조를 만들때에는 unshift(), pop() 또는 push(), shift()의 조합을 사용해야한다. 하지만 shift()와 unshift()의 경우 효율이 좋지 않기 때문에 링크 리스트를 사용하는것이 더 좋다. 

 

 

Linked list를 이용한 Queue

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  enqueue(val) {
    let newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this.length;
  }

  dequeue() {
    if (!this.head) return null;
    if (this.head === this.tail) this.tail = null;
    let currentNode = this.head;
    this.head = currentNode.next;
    this.length--;
    return currentNode.val;
  }
}

const queue = new Queue();

Dequeue의 경우 리스트의 head에서 시작해야 상수 시간복잡도를 가지므로 Enqueue는 tail에서 부터 데이터를 추가해준다.

 

 

Queue의 Big O notation

위에 작성한 클래스를 이용할경우 삽입과 제거는 상수 시간 복잡도인 O(1)이 된다. 만약 배열을 사용한다면 삽입 혹은 제거 둘 중 하나는 O(n)이 될것이다. 

Stack과 마찬가지로 Queue의 경우에도 탐색과 접근은 중요하지 않다.