알고리즘의 Stack: 데이터 구조의 핵심

 

안녕하세요! goodchuck 입니다!

블로그에 방문해주셔서 감사합니다!

 

 스택의 개념

 

스택(Stack)은 후입선출(LIFO, Last-In-First-Out) 원칙에 따라 동작하는 데이터 구조로, 가장 마지막에 삽입된 항목이 가장 먼저 삭제됩니다. 이는 책을 쌓는 것과 비슷한 개념으로 이해할 수 있습니다.

 

 스택의 등장 이유

 

스택은 컴퓨터 과학에서 다양한 분야에서 활용되며, 주요 이유는 다음과 같습니다:

- 함수 호출과 복귀: 함수 호출 시에 함수의 정보를 저장하고 복귀 시에 복귀 주소를 스택에 저장합니다.

- 재귀 알고리즘: 재귀적으로 함수를 호출할 때 스택을 사용하여 호출된 함수의 정보를 저장합니다.

- 후위 표기법 계산: 후위 표기법의 수식을 계산할 때 스택을 사용하여 연산자와 피연산자를 관리합니다.

- 브라우저 히스토리: 웹 브라우저의 뒤로 가기 버튼을 누를 때 이전 페이지로 이동하기 위해 스택을 사용합니다.

 

 스택의 장단점

 

**장점:**

- 구현이 간단하고 쉬움

- 데이터의 삽입 및 삭제가 빠름

- 후입선출의 특성으로 인한 효율적인 자료 관리

 

**단점:**

- 고정된 크기의 제한된 메모리를 사용

- 데이터의 중간 삽입, 삭제가 어려움

 

 스택의 시간복잡도

 

스택의 주요 연산인 push와 pop은 모두 상수 시간 O(1)에 수행됩니다. 즉, 스택의 크기에 관계없이 항상 일정한 시간이 소요됩니다.

 

 스택과 비교되는 다른 알고리즘: 큐(Queue)

 

큐(Queue)는 선입선출(FIFO, First-In-First-Out) 원칙에 따라 동작하는 데이터 구조입니다. 큐는 스택과는 반대로 가장 먼저 삽입된 항목이 가장 먼저 삭제됩니다. 큐는 대기열이나 버퍼와 같은 상황에서 사용되며, 예를 들어 작업 처리나 이벤트 처리에 활용됩니다.

 

 스택의 실제 활용도

 

스택은 다음과 같은 분야에서 실제로 활용됩니다:

- 함수 호출과 복귀에 사용되는 호출 스택(Call Stack)

- 웹 브라우저의 뒤로 가기 버튼 기능

- 괄호 검사와 같은 문법 분석

- 후위 표기법(Postfix Notation)의 수식 계산

- 메모리 관리와 데이터 저장에 활용

 

 스택의 메모리 할당 방식

 

스택은 일반적으로 프로그램의 메모리 공간 중 스택 영역(Stack Segment)에 할당됩니다. 이 스택 영역은 프로그램 실행 중에 동적으로 크기가 조정되지 않고, 고정된 크기를 가지며, 주로 함수 호출 및 지역 변수와 같은 데이터를 저장하는 데 사용됩니다.

 

메모리 할당은 스택 프레임(Stack Frame)이라는 작은 블록 단위로 이루어집니다. 각 함수 호출 시에는 새로운 스택 프레임이 생성되어 스택의 맨 위에 추가되고, 함수의 실행이 완료되면 해당 스택 프레임이 제거되어 스택에서 제거됩니다. 이러한 방식으로 스택은 후입선출(LIFO, Last-In-First-Out)의 구조를 유지하며, 함수 호출의 순서대로 메모리가 할당되고 해제됩니다.

 

이렇게 스택의 메모리 할당 방식을 설명함으로써 스택이 프로그램에서 어떻게 동작하는지에 대한 이해를 더욱 깊게 할 수 있습니다.

 

 Node.js로의 스택 구현

 

class Stack {
    constructor() {
        this.items = [];
    }

    push(item) {
        this.items.push(item);
    }

    pop() {
        if (!this.isEmpty()) {
            return this.items.pop();
        }
    }

    peek() {
        if (!this.isEmpty()) {
            return this.items[this.items.length - 1];
        }
    }

    isEmpty() {
        return this.items.length === 0;
    }
}

// 스택 인스턴스 생성
const stack = new Stack();

// 스택에 데이터 추가
stack.push(1);
stack.push(2);
stack.push(3);

// 스택에서 데이터 제거
console.log(stack.pop()); // 출력: 3

이상 글 읽어주셔서 감사합니다 다음에도 또 뵐수있길 빌겠습니다!