스택(Stack) - JS

• 참고사이트자바스크립트의 자료구조 4 : 스택(Stack), 큐(Queue)
• [자료구조] 스택(Stack)

스택(stack)이란?

후입선출(Last In First Out - LIFO)특성을 가지는 자료구조

• pop() : 스택에서 가장 위에 있는 항목 제거
• push(item) : item하나를 스택의 가장 윗 부분에 추가
• peek() : 스택의 가장 위에있는 항목 반환
• isEmpty() : 스택이 비어있을 때에 true반환
• size() : 스택의 크기를 return

스택의 특징

1. LIFO 구조
2. 제일 위의 데이터만 알 수 있다
3. 데이터 갯수 확인 가능
4. 중간 데이터는 모름, 알고싶으면 제일 위부터 있을거라 추정되는 그 데이터까지 모조리 꺼내야한다
5. 제일 처음 들어간 자료는 모든 자료를 꺼내기 전까지 확인할 수 없고, 제일 마지막에 들어간 자료 바로 꺼낼 수 있다
6. 자료가 없을 때 pop하는 오류를 stack underflow. 스택의 크기 이상의 자료를 push하려고 할 때 오류를 stack overflow라고 함

overflow

스택은 용량이 제한되도록 구현될 수 있다. 용량이 꽉 찼을 경우 원소를 push()할 경우 overflow error발생. 이때 용량을 늘리거나 pop()을 이용해 원소를 제거한 후 push()하는 방법이 있다.

흔히 알고있는 깊이우선탐색(DFS)를 구현할 때 재귀로 구현하는데 이 떄 Stack overflow가 종종 발생한다

Underflow

스택 비어있는 경우 pop()또는 top()을 수행하면 underflow error가 발생한다.

즉 존재하지 않는 원소에 접근하기 때문에 발생하는 에러

이때는 isEmpty()로 스택이 비어있는지 확인하여 에러를 방지

장점

• 데이터의 삽입과 삭제가 빠르다

단점

• 탐색을 하려면 원소를 하나하나 꺼내서 옮겨가면서 해야됨
• 맨 위의 원소만 접근 가능

스택의 시간 복잡도

추상적 자료구조여서 구현하는 방법에 따라 시간복잡도 달라짐 검색기능이 없고 검색이 없으니 갱신도 없음

• push ⇒ O(1)
• 제일 위에 들어가니 시간 복잡도 필요 없음
• pop ⇒ O(1)
• 무조건 제일 위에걸 빼니까 시간복잡도 상수 시간 나옴
• peek ⇒ O(1)
• 제일 위에거 탐색하니 1
• empty ⇒ O(1)
• NULL인지 아닌지만 확인해주면 됨
• size ⇒ O(1) or O(n)왜냐면 배열을 만들때 항상 level을 기재하고 있기 때문
• 그러나 list로 구현할 경우엔 끝에서 끝까지 운행을 마쳐야 level을 알 수 있기 때문에 O(n)
• 스택의 구현 방식에 따라 다른데 스택을 배열로 만들면 무조건 1

스택의 사용 사례

1. 재귀 알고리즘
   • 재귀적으로 함수 호출해야 하는 경우 임시 데이터 스택에 넣어줌
   • 재귀 함수를 빠져나와 퇴각검색(backtrack)을 할때는 스택을 넣어 두었던 임시 데이터를 빼줘야함
   • 스택은 이런 일련의 행위를 직관적으로 가능하게 해줌
   • 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다
2. 역추적 해야될 때
3. 웹 브라우저 방문기록(뒤로가기)
4. 실행 취소(undo)
5. 역순 문자열 만들기
6. 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
   • 올바른 괄호 문자열(Valid Parenthesis String) 판단하기
7. 후위 표기법 계산

구현

stack은 Array또는 singly linked List로 구현하는 두가지 방법이 있다

Array

장단점

각 element들이 서로 연관되어 있기 때문에 속도가 더 빠르다.

하지만 메모리 공간이 한정되어 있기 때문에 할당된 메모리를 다 사용하면 현재 배열을 다른 곳에 복사하기 때문에 메모리를 조금 더 사용하게 될 수도 있다

class Stack {
	constructor() {
		this.store = [];
	}
	
	push(item) {
		this.store.push(item)
	}

	pop() {
		return this.store.pop()
	}
}

const stack = new Stack();
stack.push(1);
stack.push(2); //[1, 2]
stack.pop() //2

Linked List

장단점

메모리가 여기저기 흩어져 있기 때문에 상대적으로 느릴 수 있따

하지만 메모리 공간이 한정되어 있지 않고 얼마든지 값을 계속 추가할 수 있다

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

class Stack {
	constructor() {
		this.top = null;
		this.bottom = null;
		this.length = 0;
	}
	
	peek() {
		//stack에 쌓인 가장 마지막 녀석 확인하는 메소드	
		return this.top;
	}
	push(value) {
		const newNode = new Node(value);
		if (this.length === 0) {
			this.top = newNode;
			this.bottom = newNode;
		} else {
			const holdingPointer = this.top;
			this.top = newNode;
			this.top.next = holdingPointer;
		}
		this.length ++;
		return this
	}

	pop() {
		if(!this.top) return null;
		if (this.top === this.bottom) {
			this.bottom = null;
		} 
		this.top = this.top.next;
		this.length--;
		return this
	}
}

const myStack = new Stack();
console.log(myStack)
myStack.push('google');
console.log(myStack)
myStack.push('facebook');
console.log(myStack)
myStack.push('udemy');
console.log(myStack)
myStack.pop();
console.log(myStack)

출력

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

class Stack {
	constructor() {
		this.top = null;
		this.bottom = null;
		this.length = 0;
	}
	
	peek() {
		//stack에 쌓인 가장 마지막 녀석 확인하는 메소드	
		return this.top;
	}
	push(value) {
		const newNode = new Node(value);
		if (this.length === 0) {
			this.top = newNode;
			this.bottom = newNode;
		} else {
			const holdingPointer = this.top;
			this.top = newNode;
			this.top.next = holdingPointer;
		}
		this.length ++;
		return this
	}

	pop() {
		if(!this.top) return null;
		if (this.top === this.bottom) {
			this.bottom = null;
		} 
		this.top = this.top.next;
		this.length--;
		return this
	}
}

const myStack = new Stack();
console.log(myStack)
myStack.push('google');
console.log(myStack)
myStack.push('facebook');
console.log(myStack)
myStack.push('udemy');
console.log(myStack)
myStack.pop();
console.log(myStack)