Stack

스택은 나중에 들어온 것이 먼저 나가는 Last-In First-Out 구조를 가지고 있고 보통 스택구조는 물건을 쌓는 모습으로 비유 된다. 일반적으로 쌓는 것을 push 빼는 것을 pop이라고 한다. 대표적으로 자바스크립트의 callstack이 있다.

Stack의 Big-O 시간복잡도

삽입 insertion

stack 구조에서 삽입은 데이터를 위로 쌓기만 하면 되기 때문에 시간복잡도는 O(1)이다.

삭제 deletion

마찬가지로 단순히 나중에 들어온 데이터를 제거하면 되기 때문에 시간복잡도 는 O(1)이다.

탐색 search

보통 Big-O 는 최악의 경우를 가정하는데, stack 구조에서 탐색중 찾고자 하는 자료가 가장 밑에 있을경우 stack을 한번은 순회를 해야하기 때문에 시간복잡도는 O(N)이된다.

실제 사용예

• 브라우저 히스토리
• 자바스크립트 callstack

Stack 구현

function Stack() {
  this.storage = [];
  this.length = 0;
  this.top = null;
}

Stack.prototype.push = function(value) {
  this.storage.push(value);
  this.top = value;
  this.length++;

  return value;
};

Stack.prototype.pop = function() {
  const removedData = this.storage.pop();
  
  this.length--;
  this.top = this.storage[this.length - 1];

  return removedData;
};

Queue

큐는 먼저들어온 것이 먼저나가는 First-In First-Out 구조를 가지고있고 큐에서 삽입 연산은 enqueue, 삭제연산은 dequeue라고 한다. 대표적으로 이벤트 루프의 callback queue가 있다.

Queue Big-O 시간복잡도

삽입 insertion

queue 구조에서 삽입은 항상 자료를 마지막에 추가 때문에 시간복잡도는 O(1)이다.

삭제 deletion

삭제는 항상 먼저들어온 자료부터 삭제하기 때문에 시간복잡도는 O(1)이다.

탐색 search

queue 구조에서 탐색중 찾고자 하는 자료가 가장 뒤에 있을경우 queue을 한번은 순회를 해야하기 때문에 시간복잡도는 queue의 길이에 비례하는 O(N)이다.

실제 사용예

• 우선 순위를 두어야 하는 작업
• 이벤트 루프의 callback queue

Queue 구현

function Queue() {
  this.storage = [];
  this.front = null;
  this.back = null;
  this.length = null;
}

Queue.prototype.enqueue = function(value) {
  this.storage.push(value);
  this.length++;
  this.front = this.storage[0];
  this.back = this.storage[this.length - 1];

  return value;
};

Queue.prototype.dequeue = function() {
  const removedData = this.storage.shift();

  this.length--;
  this.front = this.storage[0];
  this.back = this.storage[this.length - 1];

  return removedData;
};

참고

• Data Structure: Stack and Queue