자료구조(4) - 스택

hyejin·2024년 7월 19일

배열 기반 스택 스택 시간 복잡도 연결리스트 기반 스택 예제 자료구조

study-2024

목록 보기

13/16

스택(Stack)이란?

스택(Stack)은 쌓다라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다.

스택의 특징

가장 나중에 들어온 데이터가 가장 먼저 나가는 후입선출(LIFO-Last In First Out)구조이다.
리스트의 한쪽(top)으로 삽입(push)과 삭제(pop) 연산을 수행한다.
정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근 가능하다.

예제

기본 연산
기본 연산은 JavaScript나 Python과 같은 언어에서 특별히 스택 자료구조를 위한 내장 클래스나 자료구조로 제공되는 것이 아니다. 대신, 배열(Array)과 같은 기본 자료구조를 사용하여 직접 구현할 수 있다.

스택의 구현 방법에는 배열을 사용하는 방법과 연결리스트를 사용하는 방법이 있다. 아래 두 예제는 JavaScript 언어로 작성된 스택 구현 예제이다.

배열을 이용한 스택

연산 구현

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

    // 요소를 스택에 추가
    push(element) {
        this.items.push(element);
    }

    // 스택의 최상위 요소를 반환
    pop() {
        if (this.isEmpty()) {
            return "Stack is empty";
        }
        return this.items.pop();
    }

    // 스택의 최상위 요소를 반환 (제거하지 않음)
    peek() {
        if (this.isEmpty()) {
            return "Stack is empty";
        }
        return this.items[this.items.length - 1];
    }
  
    // 스택이 비어 있는지 확인
    isEmpty() {
        return this.items.length === 0;
    }

    // 스택의 크기 반환
    size() {
        return this.items.length;
    }
}

사용 예제

const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log("Is Empty: " + stack.isEmpty());  // false
console.log("Peek: " + stack.peek());  // 30
console.log("Size: " + stack.size());  // 3
console.log("Pop: " + stack.pop());    // 30
console.log("Pop: " + stack.pop());    // 20
console.log("Pop: " + stack.pop());    // 10
console.log("Is Empty: " + stack.isEmpty());  // true

연결 리스트를 이용한 스택

연산 구현

// 노드 클래스 정의
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

// 연결 리스트를 사용한 스택 클래스 정의
class Stack {
    constructor() {
        this.top = null;
        this._size = 0;
    }

    // 요소를 스택에 추가
    push(element) {
        const newNode = new Node(element);
        newNode.next = this.top;
        this.top = newNode;
        this._size++;
    }

    // 스택에서 요소를 제거하고 반환
    pop() {
        if (this.isEmpty()) {
            return "Stack is empty";
        }
        const poppedNode = this.top;
        this.top = this.top.next;
        this._size--;
        return poppedNode.value;
    }

    // 스택의 최상위 요소를 반환 (제거하지 않음)
    peek() {
        if (this.isEmpty()) {
            return "Stack is empty";
        }
        return this.top.value;
    }

    // 스택이 비어 있는지 확인
    isEmpty() {
        return this._size === 0;
    }

    // 스택의 크기 반환
    size() {
        return this._size;
    }
}

사용 예제

const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log("Peek: " + stack.peek());  // 30
console.log("Size: " + stack.size());  // 3
console.log("Pop: " + stack.pop());    // 30
console.log("Pop: " + stack.pop());    // 20
console.log("Pop: " + stack.pop());    // 10
console.log("Is Empty: " + stack.isEmpty());  // true

배열 기반 스택은 고정 크기나 빠른 인덱스 접근이 필요한 경우에 적합하며, 간단한 구현과 효율적인 연산이 장점이다. 연결 리스트 기반 스택은 스택의 크기에 따라 동적으로 메모리를 할당하고 해제할 수 있어 메모리 사용의 유연성이 뛰어나지만, 추가적인 메모리 오버헤드와 느린 접근 속도가 단점이다.
JavaScript와 Python 언어에서 *배열(리스트)은 동적으로 크기를 조절할 수 있어, 배열 기반 스택이 메모리 관리와 성능 면에서 매우 편리하다. 그러나 동적 배열의 크기 조절에 따른 성능 차이는 두 언어에서 다를 수 있으며, 특정 상황에 맞는 자료구조 선택이 중요히다.
* 배열 참고 링크

시간 복잡도

삽입(Push)

요소를 스택 맨위에 추가하는 연산
배열이나 연결리스트를 사용하여 스택을 구현할 때, 단순히 새로운 요소를 맨 위에 추가하고 스택의 최상위 포인터나 인덱스를 업데이트
시간 복잡도: O(1)

삭제(Pop)

스택의 맨 위에 있는 요소를 제거하고 반환하는 연산
배열의 경우, 맨 위 요소를 제거하고 인덱스 감소
연결리스트의 경우, 최상위 노드를 제거하고 포인터 업데이트
시간 복잡도: O(1)

검색(Search)

스택에서 특정 요소를 찾는 연산
모든 요소를 하나씩 확인
최악의 경우, 찾고자 하는 요소가 스택의 맨 아래 있을 수 있으므로, n개의 요소를 모두 확인
시간 복잡도: O(n)

검색 연산(search)를 제외하고, 스택의 기본 연산(push, pop, peek, isEmpty, size)은 모두 O(1) 시간 복잡도를 가진다. 이는 스택의 구조와 연산 방식이 매우 단순하며, 각 연산이 데이터의 위치나 크기와 관계없이 일정한 시간 내에 수행될 수 있기 때문이다. 스택의 이러한 특성 덕분에 알고리즘 설계 시 매우 효율적으로 사용될 수 있다.