스택(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!