AHRIBORI.COMv0.9
HomeAbout (2)Javascript (7)CSS (12)React (3)Webpack (1)Java (0)Node.js (4)ElasticSearch (1)자료구조 (8)알고리즘 (6)Selenium (1)Linux (2)Docker (1)Git (1)Tip (4)Issue (1)Memo (3)

[자료구조] 스택(Stack)

아리보리 | 2017.05.14 01:56 | 조회 943 | 추천 0 | 댓글 0

스택(Stack)은 후입선출(LIFO, Last-In, First Out)의 자료구조이다.

입출력이 같은 곳에서 일어나며, 데이터를 삽입하는 것을 푸시(Push), 데이터를 반출하는 것을 팝(Pop)이라고 한다.

 

맨 위에 있는 데이터를 가리켜 탑(Top) 이라고 하고 Top을 읽는 작업을 피크(Peek)라고 한다.

 

스택이 가득 차 있을 때 Push를 하게 되면 스택 오버플로우(Stack Overflow),

스택이 비어있을 때 Pop을 하게 되면 스택 언더플로우(Stack Underflow)라고 한다.

 

자바스크립트로 스택을 구현해보면,

 

class Stack {
    
	constructor(size) {
        // default size 5
        const _size = isNaN(size) ? 5 : size;
        this.data = new Array(_size);
        this.size = _size;
		this.top = -1;
	}
	
	push(item) {
        if (!this.isFull()) {
            this.data[this.top + 1] = item;
            this.top++;
        } else {
            console.log('Stack Overflow!');
        }
		return this;
	}
	
	pop() {
        if (!this.isEmpty()) {
            this.data[this.top] = undefined;
            this.top--;
        } else {
            console.log('Stack Underflow!');
        }
		return this;
	}
	
	peek() {
		console.log(this.top);
	}
	
	isEmpty() {
		return this.top === -1;
	}
	
	isFull() { 
		return this.top === this.data.length - 1;
	}
	
	clear() {
		this.data = new Array(this.size);
        return this;
	}
	
	print() {
		console.log(this.data);
	}
    
}


const stack = new Stack(3); // [undefined, undefined, undefined]

stack
    .push(1) // [1, undefined, undefined]
    .push(2) // [1, 2, undefined]
    .push(3) // [1, 2, 3]
    .push(4) // Stack Overflow!
    .pop() // [1, 2, undefined]
    .pop() // [1, undefined, undefined]
    .pop() // [undefined, undefined, undefined]
    .pop() // Stack Underflow!