[algorithm] 스택

스택이란?

후입선출, 나중에 들어온 것을 가장 먼저 사용하는 자료구조.
스택은 마지막 항목이 제거된다는 것을 이용하면 찾기와 삽입이 O(1)에 이루어지는 매우 빠른 자료구조이다.
다음 코드는 스택의 기본 뼈대 구성이다.

function Stack(array){
    this.array = [];
    if(array) this.array = array;
}

Stack.prototype.getBuffer = function(){
    return this.array.slice();
}

Stack.prototype.isEmpty = function(){
    return this.array.length == 0;
}

var stack1 = new Stack();
console.log(stack1) // {array: []}

들여다보기(peeking)

스택의 마지막에 있는 데이터를 제거하지 않고 반환하는 것이 peeking이다.

Stack.prototype.peek = function(){
	return this.array[this.array.length-1];
}

peeking을 통해서 데이터를 제거해야 할지 말아야 할지 결정할 때 사용할 수 있다. 시간복잡도는 O(1)이다.

삽입(push)

스택의 최상단에 데이터를 추가하는 것이 삽입이다.

Stack.prototype.push = function(value):void{
	this.array.push(value);
}

삭제(pop)

스택의 최상단에 데이터를 추가하는 것이 삽입이다.

Stack.prototype.pop = function(value):void{
	this.array.pop(value);
}

접근

위에서부터 n번째 노드에 접근하기 위해서는 pop을 n번 사용해야 한다.

function stackAccessNthTopNode(stack, n){
  var bufferArray = stack.getBuffer();
  if(n<=0) throw 'error';
  
  var bufferStack = new Stack(bufferArray);
  
  while(--n!==0){
  	bufferStack.pop();
  }
  return bufferStack.pop();
}

n번 반복하여 반환하므로 시간 복잡도는 O(n)이다.

검색

스택에서 pop이 버퍼 스택에 대해 호출할 수 있도록 버퍼 스택을 만들어 원본 스택은 건드리지 않아야 한다.

function stackSearch(stack, element) {
  var bufferArray = stack.getBuffer();
  var bufferStack = new Stack(bufferArray); // 버퍼스택으로 복사한다.
	
  while(!bufferStack.isEmpty()){
    if(bufferStack.pop()==element) return true;
  }
  return false;
}

원하는 값을 찾아 true를 반환하기 전까지는 n번 반복해야 하므로 시간복잡도는 O(n)