자료구조 - Stack

스마트폰을 사용할 때 '뒤로 가기' 버튼을 누르면 현재의 화면이 멈추고 이전 화면으로 돌아가게 된다. 스택 활용의 예시로 볼 수 있다.

데이터 입출력이 맨 위(stack top)에서만 일어나고 스택의 밑(stack bottom)이나 중간에서는 데이터 삭제가 불가능하다. 주요 특징을 살펴보면 다음과 같다.

✔︎ 스택에 데이터 요소가 하나도 없을 때, 공백 스택(empty stack)이라고 정의한다.

✔︎ 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우에 사용된다. 이를 후입선출(LIFO: Last IN First Out)의 구조라고 한다. undo가 예시.

✔︎ 스택은 복귀할 주소를 기억한다. 운영체제가 사용하는 시스템 스택에서는 함수가 호출될 때마다 함수 실행이 끝나면 돌아갈 복귀주소를 저장하는 활성 레코드(activaion record)를 만든다.

top에서 데이터를 추가할 때 push연산, 삭제할 때는 pop연산을 주로 사용하게 된다. 자바스크립트로 구현한 스택은 다음과 같다.

class Stack {
	constructor() {
	  this.stackArray = [];
	}
	
	push(item) {
	  this.stackArray.push(item);
	}
	
	pop() {
	  return this.stackArray.pop();
	}
  }

아래는 peek(요소를 보기만 함), 빈 상태에서 top을 고려한 코드.

class Stack {
    constructor() {
        this.top = -1;
        this.bucket = [];
    }
    
    isEmpty() {
        return this.bucket.length == 0;
    }

    push(val) {
        this.bucket[++this.top] = val;
    }

    pop() {
        if(this.top < 0) {
            return -1;
        } else {
            let popVal = this.bucket[this.top];
            this.bucket = this.bucket.slice(0, this.top);
            this.top--;
            return popVal;
        }
    }

    peek() {
        return this.bucket[this.bucket.length-1];
    }
    
    clear() {
        this.top = -1;
        this.bucket = [];
    }
    
    print() {
        for(let i=0; i<this.bucket.length; i++) {
            console.log("item[" + i + "] : " + this.bucket[i]);
        }
    }
}

마지막으로 스택을 통해 고민할 수 있는 알고리즘 문제로 '괄호 검사'가 있다.

✔︎ 오른쪽 괄호가 들어오면 직전에 읽었던 왼쪽 괄호와 비교해서 같지 않으면 에러 처리를 하고 같은 종류이면 pop연산으로 처리한다.
✔︎ 위와 같은 과정을 반복하여 인풋으로 들어온 괄호를 처리하고 빈 상태라면 올바른 괄호배치, 남아 있으면 에러 처리.

괄호 검사 알고리즘 문제 https://programmers.co.kr/learn/courses/30/lessons/12909

참고
1) https://www.programiz.com/dsa/stack
2) c언어로 쉽게 풀어 쓴 자료구조 - 천인국
3) https://gogomalibu.tistory.com/52
4) https://claude-u.tistory.com/74