[자료구조] stack

스택이란 무엇일까?

Push()

스택은 기본적으로 박스 쌓기와 비슷합니다. 맨 위에 있는 상자만 접근할 수 있습니다. 그래서 스택에서 데이터를 추가하거나 제거할 때, 항상 맨 위의 상자를 조작합니다. 이렇게 상자를 쌓아 올리는 것을 "푸시(push)"라고 부르며, 맨 위의 상자를 빼내는 것을 "팝(pop)"이라고 부릅니다.

Pop()

스택은 일상 생활에서도 자주 사용됩니다. 예를 들어, 접시를 쌓아 놓은 것을 생각해 본다면 가장 마지막에 쌓은 접시를 먼저 꺼내게 됩니다. 이렇게 쌓여있는 접시들은 스택과 유사한 구조를 가지고 있습니다.

접시를 쌓으려면, 처음에는 바닥에 하나의 접시를 놓습니다. 그런 다음 다음 접시를 가져와 첫 번째 접시 위에 올립니다. 이렇게 쌓기를 반복하면 스택이 형성됩니다.

여기서 스택은 먼저 쌓인 접시가 제일 아래에 있고, 마지막에 쌓인 접시가 제일 위에 있다는 것입니다. 따라서 마지막으로 올린 접시를 먼저 꺼내야 합니다.

만약 새로운 접시를 쌓으려고 할 때 스택이 가득 찼다면, 새로운 접시를 쌓을 수 없습니다. 이러한 상황은 스택 오버플로우(Stack Overflow)라고 합니다. 이와 반대로, 스택이 비어있는 경우 쌓여 있는 접시가 없으므로 꺼낼 수 없습니다. 이러한 상황은 스택 언더플로우(Stack Underflow)라고 합니다.

따라서 접시 쌓기와 같이 스택을 사용하는 상황에서는 먼저 들어온 것이 나중에 처리되고, 나중에 들어온 것이 먼저 처리되는 것이 일반적입니다. 이러한 동작 방식을 이해하면 프로그래밍에서 스택을 사용하는 데 도움이 됩니다.

---

후입선출(LIFO, Last-In-First-Out)

스택의 가장 큰 특징은 후입선출(LIFO, Last-In-First-Out) 구조입니다. 즉, 가장 나중에 추가된 데이터가 가장 먼저 제거됩니다. 이것이 스택의 가장 큰 장점이자 특징 중 하나입니다.

스택은 여러 가지 분야에서 사용됩니다. 프로그래밍에서는 함수 호출을 추적하거나, 괄호 짝 맞추기, 그리고 식의 계산 등에 사용됩니다. 또한, 인터넷 브라우저에서 방문한 웹 사이트의 기록을 저장하는 기능도 스택을 이용합니다.

스택의 구현은 배열(Array)이나 연결 리스트(Linked List)로 할 수 있습니다. 배열을 이용할 경우 크기를 지정해야 하지만, 빠른 접근 속도를 가지며 구현이 쉽습니다. 연결 리스트를 이용할 경우 크기를 지정할 필요가 없지만, 구현이 복잡하며 접근 속도가 느립니다.

---

스택 구현

class Stack {
  // stack constructor를 생성합니다.
  constructor() {
    this.storage = {};
    this.top = -1;
  }
  // stack의 사이즈를 구합니다.
  // this.top은 스택이 쌓일 때마다 하나씩 증가하기 때문에 top으로부터 size를 구할 수 있습니다.
  // this.top은 스택에 새롭게 추가될 요소의 인덱스를 나타냅니다. 빈 스택을 표현하는 -1부터 1씩 증감하며 표현하며 전체 요소의 개수를 추정할 수 있습니다
  size() {
    return this.top + 1;
  }
  // stack에 element를 추가합니다.
  // 현재 추가하는 element의 인덱스인 this.top을 키로, 요소를 값으로 하여 storage에 할당합니다.
  push(element) {
    this.top += 1;
    this.storage[this.top] = element;
  }
  // 만약 size가 0보다 작거나 같다면 이는 비어있는 스택을 의미하므로 아무 일도 일어나지 않습니다.
  // stack에서 현재 stack의 최상단에 있는 element를 변수에 저장합니다.
  // storage에서 해당 element를 제거합니다.
  // 하나를 제거했으니 방금 제거한 element의 인덱스를 나타내는 top 또한 감소시켜 업데이트 해줍니다.
  // 최상단에 있던 element가 저장된 변수 result를 반환합니다.
  pop() {
    if (this.size() <= 0) {
      return;
    }
    const result = this.storage[this.top];
    delete this.storage[this.top];
    this.top -= 1;
    return result;
  }
}

---

sitesbay - Data Structure

Stack Push Operation in C - Data Structure

code.tutsplus.com - Data Structures With JavaScript: Stack and Queue

Data Structures With JavaScript: Stack and Queue