[algorithm] stack(스택)이란? 사용 예제/방법 (javascript 코드)

 

스택(Stack) 이란?

메모리의 스택 영역은 함수의 호출과 관계되는 지역변수, 매개변수, 리턴 값 등의 임시데이터를 저장되는 영역.

LIFO(Last In First Out, 후입선출) 구조

(데이터는 넣은 순서에 따라 아래서부터 위로 쌓이고, 제일 최상위(최근에 저장된 데이터) 부터 빠지는 구조입니다.

스택 push().  https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Ft1.daumcdn.net%2Fcfile%2Ftistory%2F99AF81395BB1D8212B

stack pop()  https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Ft1.daumcdn.net%2Fcfile%2Ftistory%2F99A10C4A5BB1D83C0F

 

스택의 TOP & BOTTOM 

TOP/BOTTOM은 스택의 특정위치를 가르킨다.

TOP은 가장 최근에 스택에 저장된 값, BOTTOM은 가장 처음 스택에 저장된 값을 가르킨다. 

현재 TOP은 최상의 (B)이고 BOTTOM은 최하위 (A) 이다.

여기서 새로운 요소(C)가 추가 된다면!  가장 최근에 추가된 요소가 최상위로 가기때문에 TOP은  (C), BOTTOM은 최하위 (A)를 가르킨다.

 

예제

javascript array는(은)  push()와 pop()을 내장함수로 가지고 있기 때문에 쉽게 구현할 수 있다. 

const arr = [1,2,3,4,5,6];

arr.pop(); // 6   
console.log(arr); // [1,2,3,4,5];
arr.push(7); 
console.log(arr); // [1,2,3,4,5,7];

시간복잡도는 상수시간이 소요된다.(빠름!)     (shift/unshift 와는 달라요)

https://joyhong-91.tistory.com/entry/javascript-%EB%B0%B0%EC%97%B4%EC%9D%98-pushpopunshiftshift-%EC%82%AC%EC%9A%A9%EB%B2%95

[javascript] 배열의 push,pop,unshift,shift 사용법

 

연결리스트로 작성해본다면, 

// 다음요소와 연결되는 Node class
class Node {
	constructor(value) {
    	this.value = value;
        this.next = null;
    }
}

// Stack class
class Stack {
	constructor() {
    	this.top = null;
        this.size = 0;
    }
    
    push(value) {
    	const node = new Node(value);
        node.next = this.top; //새로 추가될 node의 다음요소는 추가되기 전상태인 최상단을 가르키게 해주고 
        this.top = node; // 최상단에 지금 추가할 노드를 넣는다.
        this.size += 1; // stack 요소의 사이즈는 1 증가
    }
    
    pop() {
    	const value = this.top.value;  //this.top에 위치한 node의  value
		this.top = this.top.next; // 최상단이 빠져나간 후의 최상위 요소는 다음요소가 TOP이 된다.
    	this.size -= 1;  //사이즈는 1 감소;
        return value;
    }
    
    size() {
    	return this.size;
    }
    
}



const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // "3" 추출 |  스택의 잔여요소: 1,2
stack.push(4); // 스택의 잔여요소: 1,2,4
console.log(stack.pop()); // "4" 추출 | 스택의 잔여요소 1,2
console.log(stack.pop()); // "2" 추출 | 스택의 잔여요소 1

 

 

 

 

잘못된 정보에 대한 피드백은 언제나 환영입니다  (´▽`ʃƪ)♡