스택(Stack)
스택은 블록을 아래에서부터 위로 쌓아 올리는 구조를 가지고 있으며, 가장 마지막에 들어간 원소가 가장 먼저 나오게 된다. 이러한 자료구조의 특성을 LIFO(Last-in, First-out)라고 한다.
스택의 연산은 Push, Pop으로 단순하다.
Push 연산 시 가장 위에 원소를 추가하게 되고, Pop 연산 시 가장 위의 원소를 반환한다.
push, pop을 할 때는 해당 위치를 알고 있어야 하므로, 기억하고 있는 '스택 포인터(SP)'가 필요하다.
스택 포인터는 다음 값이 들어갈 위치를 가리키고 있다. (처음 기본값은 -1)
구현
스택을 구현할 때는 배열로 구현할 수도 있고, 연결리스트(Linked List)를 이용해 구현할 수도 있다.
여기서는 배열을 이용해 스택을 간단히 구현할 것이다.
1. 스택의 초기화
스택의 사이즈를 결정할 STACK_SIZE를 할당하고 해당 사이즈만큼의 배열을 선언한다. 또한 가장 위의 원소를 가리킬 top 변수를 -1로 초기화한다.
이는 스택의 index를 0부터 시작하기 위함이다.
const STACK_SIZE = 10; // 스택의 크기
const stack = new Array(STACK_SIZE); // 스택 배열
let top = -1; // 스택의 맨 위 인덱스2. isFull() 함수, isEmpty() 함수 구현
// 스택이 가득 찼는지 확인하는 함수
function isFull() {
if (top >= STACK_SIZE - 1) { // stack의 인덱스는 0부터 시작
console.log("Error: Stack is Full!");
return true;
}
return false;
}
// 스택이 비어 있는지 확인하는 함수
function isEmpty() {
if (top === -1) {
console.log("Error: Stack is empty!");
return true;
}
return false;
}스택이 꽉 차있는 경우에 원소를 집어 넣으려고 push 연산을 하면 스택이 넘치게 된다. 이를 스택 오버플로우(stack overflow)라고 한다.
반대로 스택이 비어 있는 상태에서 pop 연산을 하면, 아무것도 없는 상태에서 원소를 반환하려고 하기 때문에 오류가 발생할 것이다.
따라서 이를 방지하기 위해 스택의 상태를 체크하는 함수인 isFull() 함수와 isEmpty() 함수가 필요하다.
isFull() 함수는 스택이 꽉 차 있는지 검사한다.
만약 top 변수가 STACK_SIZE-1보다 크거나 같다면 스택이 꽉 차 있는 상태인 것이다. 이는 스택의 index가 0부터 시작하기 때문이다.
예를 들어 STACK_SIZE를 10으로 설정했는데, 만약 top 변수가 9 값을 갖고 있다면, 인덱스 0부터 9까지 총 10개의 원소가 있는 것이므로 스택이 꽉 차 있는 것이다.
isEmpty() 함수는 스택이 비어 있는지 검사한다.
만약 top 변수가 -1 값을 갖는다면 초기 상태, 원소가 아무 것도 없는 상태이므로 비어 있는 것이다.
3. push() 함수
스택이 꽉 차 있는지 검사하고, 그렇지 않다면 원소를 스택의 가장 윗 부분에 추가한다.
function push(data) {
if (!isFull()) {
top++;
stack[top] = data;
} else {
console.log("Error: Stack is Full!");
}
}4. pop() 함수
스택이 비어 있는지 검사하고, 그렇지 않다면 가장 위에 있는 원소를 반환한다.
function pop() {
if (!isEmpty()) {
const poppedData = stack[top];
top--;
return poppedData;
} else {
console.log("Error: Stack is Empty!");
return undefined; // 또는 다른 값을 반환하거나 예외를 던질 수 있음
}
}5. printStack() 함수
스택의 모든 원소를 출력하는 함수이다. 이 때 아래에서부터 위의 순서로 원소를 출력하는 것에 유의한다.
function printStack() {
for (let i = 0; i <= top; i++) {
console.log(stack[i]);
}
console.log(); // 개행 문자를 출력하여 줄 바꿈
}전체 코드
const STACK_SIZE = 10;
const stack = new Array(STACK_SIZE);
let top = -1;
function isFull() {
return top >= STACK_SIZE - 1;
}
function isEmpty() {
return top === -1;
}
function push(data) {
if (!isFull()) {
top++;
stack[top] = data;
} else {
console.log("Error: Stack is Full!");
}
}
function pop() {
if (!isEmpty()) {
return stack[top--];
} else {
console.log("Error: Stack is Empty!");
return undefined;
}
}
function printStack() {
for (let i = 0; i <= top; i++) {
console.log(stack[i]);
}
console.log();
}
push(5);
push(4);
push(3);
push(2);
push(1);
printStack(); // 5 4 3 2 1
pop();
printStack(); // 5 4 3 2 동적 배열 스택
위와 같이 구현할 경우, 스택에는 MAX_SIZE라는 최대 크기가 존재해야 한다.
(스택 포인터와 MAX_SIZE를 비교해서 isFull 메소드로 비교해야 하므로)
최대 크기가 없는 스택을 만드려면 arraycopy를 활용한 동적 배열을 사용해야 한다.
function push(o) {
if (isFull(sp)) {
const newArr = new Array(MAX_SIZE * 2);
for (let i = 0; i < MAX_SIZE; i++) {
newArr[i] = stack[i];
}
stack = newArr;
MAX_SIZE *= 2; // 2배로 증가
}
stack[sp++] = o;
}기존 스택의 2배 크기만큼 임시 배열(arr)을 만들고, arraycopy를 통해 stack의 인덱스 0부터 MAX_SIZE만큼을 arr 배열의 0번째부터 복사한다.
복사 후, arr의 참조값을 stack에 덮어 씌운다.
마지막으로 MAX_SIZE의 값을 2배로 증가시켜주면 된다.
이렇게 하면 스택이 가득 찼을 때, 자동으로 확장되는 스택을 구현할 수 있다.
