[ ᴀʟɢᴏʀɪᴛʜᴍ ] Stack ( 스택 )

NewHa·2023년 10월 17일

algorithm

스택(Stack)

스택의 특징(Characteristic of Stack)

ᴀʟɢᴏʀɪᴛʜᴍ

목록 보기

9/19

스택(Stack)

스택 (stack)은 '쌓다, 포개다'라는 직역 그대로 데이터를 순서대로 쌓는 구조입니다. 새로운 요소의 삽입과 기존 요소의 제거가 하나의 방향, 즉 스택의 최상단(top)에서만 발생하는 선형 데이터 구조입니다.

쉽게 말하자면 프링글스 안에 감자칩이 쌓여있는 모양입니다. 프링글스 안에 넣을 때도, 먹을 때도 상단의 입구를 통해서만 넣고 뺼 수 있습니다. 이러한 제한적 접근 특징 때문에 하나씩만 삽입, 삭제할 수 있고 스택 구조 내의 특정 데이터를 조회할 수 없습니다.

이렇게 먼저 들어간 데이터가 나중에 나오는 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out) 이라고 부릅니다. 어떤 자료구조이든지 FIFO 규칙만 지킨다면 스택에 해당합니다.

스택 자료구조를 사용하는 예로는, undo(되돌리기) 작업이 있습니다. 컴퓨터가 그동안의 작업 내역을 스택에 저장했다가 차례로 꺼내어 작업을 되돌립니다.

스택의 특징(Characteristic of Stack)

JavaScript에서는 배열로, push(data), pop() 메서드를 이용해 구현할 수 있습니다.

기본 기능

Method	시간복잡도	작 업
push(data)	O(1)	스택의 맨 뒤에 요소를 삽입합니다. 스택이 가득 차면 overflow 상태라고 합니다.
pop()	O(1)	스택의 맨 뒤에서 요소를 제거합니다. 푸시된 순서의 역순으로 pop 되며, 스택이 비어 있으면 underflow의 조건이라고 합니다.
isEmpty()	O(1)	스택이 비어 있으면 true, 그렇지 않으면 false를 반환합니다.
isFull()	O(1)	스택이 가득 차 있으면 treu, 그렇지 않으면 false를 반환합니다.
size()	O(1)	스택 내의 모든 요소들의 개수(크기)를 반환합니다.
top()	O(1)	스택의 최상위 요소를 반환합니다.
peek()	O(1)	top 포인터가 가리키는 데이터를 조회(확인)합니다.

😊 장 점

배열이나 연결 리스트를 사용해 구현하기 쉽고, 이해하기 쉽습니다.
인접한 메모리 블록을 사용하므로 다른 데이터 구조에 비해 메모리 활용이 더 효율적 입니다.
스택 상단에서 요소가 추가﹒제거되며 엑세스 시간이 빠릅니다.

😫 단 점

스택 데이터 구조는 프로그래밍 언어나 엔진에 따라 용량이 제한되어 있습니다. 스택이 가득 차 있는데 새 요소를 추가하면 stack overflow가 발생하여 데이터가 손실될 수 있습니다. 따라서 재귀적으로 함수를 호출해 스택에 쌓이게 되면 stack overflow로 프로그램이 종료될 수 있습니다.
스택이 비어 있는데도 요소를 제거하려고 pop() 하면 stack underflow가 발생할 수 있습니다.
스택 상단에서 요소를 추가하고 제거하는 것만 허용하고, 해당 요소에 대한 무작위 접근을 허용하지 않아, 스택 중간에 있는 요소에 접근하려면 그 위의 모든 요소를 제거해야 합니다. 검색 또는 정렬 알고리즘과 같이 중간에 있는 요소에 접근해야 하는 경우에는 적합하지 않습니다.
연속적인 메모리 블록을 사용해 스택을 구현하면 요소가 자주 추가되고 제거되면 메모리 조각화가 발생할 수 있습니다.

활 용

함수 호출과 해당 상태를 저장하는 데 스택 데이터 구조가 사용됩니다. 재귀 함수 호출을 효율적으로 구현하는 데 도움이 됩니다.
다양한 애플리케이션에서 실행 취소(undo), 다시 실행(redo) 기능, 방문 웹 페이지 추적 등에 스택에 사용됩니다. 작업 혹은 url이 스택에 push되고 실행 취소(undo) 버튼을 누르면 스택의 최상위 요소부터 pop되면서 되돌아갑니다.
트리순회 등의 알고리즘에서 사용할 수 있습니다.

구 현 ( Implements )

배열이나 연결리스트를 사용하여 구현할 수 있습니다. 스택에는 최상위 포인터가 포함됩니다.

🕶️ 배열로 구현

스택을 위한 배열을 하나 만듭니다. index가 0이면 스택이 비어 있는 것이고, 스택에 요소를 삽입할 때 index 자리에 넣고 index를 올립니다. index가 초기 배열 크기 이상이면 stack이 꽉 찬 것이고, 요소를 삭제할 때는 index에 있던 값을 반환하고 index를 하나 줄입니다.

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

  // 요소 추가 (push)
  push(element) {
    this.items.push(element);
  }

  // 요소 제거 (pop)
  pop() {
    if (this.isEmpty()) {
      throw new Error("스택이 비어있습니다.");
    }
    return this.items.pop();
  }

  // 가장 위의 요소 반환 (peek)
  peek() {
    if (this.isEmpty()) {
      throw new Error("스택이 비어있습니다.");
    }
    return this.items[this.items.length - 1];
  }

  // 스택이 비었는지 확인
  isEmpty() {
    return this.items.length === 0;
  }

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

  // 스택 초기화
  clear() {
    this.items = [];
  }

  // 스택 전체 출력 (디버깅용)
  print() {
    console.log(this.items.join(", "));
  }
}

🕶️ 연결 리스트로 구현

물리 메모리 상에서는 순서와 관계없이 무작위로 공간을 할당하고, 새 요소를 추가할 때 새 노드를 만들고 현재 최상위 노드의 다음 포인터로 새 노드 요소를 연결하면 됩니다. 런타임 시 필요에 따라 메모리가 확장﹒축소될 수 있어서 Overflow가 불가능합니다. 하지만 포인터 관련으로 추가 메모리가 필요하고 연결 리스트의 특징으로 무작위 접근이 불가능합니다.

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

class Stack {
  constructor() {
    this.top = null;  
    this.length = 0;
  }

  push(value) {
    const newNode = new Node(value);
    newNode.next = this.top;
    this.top = newNode;
    this.length++;
  }

  pop() {
    if (this.isEmpty()) {
      throw new Error("스택이 비어있습니다.");
    }

    const poppedNode = this.top;
    this.top = this.top.next;
    this.length--;
    return poppedNode.value;
  }

  peek() {
    if (this.isEmpty()) {
      throw new Error("스택이 비어있습니다.");
    }
    return this.top.value;
  }

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

  size() {
    return this.length;
  }

  print() {
    let current = this.top;
    let result = [];
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    console.log(result.join(", "));
  }
}