[자료구조] 스택

📌 참고 사이트

[자료구조] 스택 with JavaScript (tistory.com)

[자료구조] 스택 with JavaScript

 

 

 

📋 스택 (stack)

❓ 스택

데이터를 탑을 쌓듯 추가하는 형태의 자료 구조이다.

가장 마지막에 쌓인 데이터가 가장 먼저 나오는 형태, 즉 LIFO(Last-In First-out)의 형태를 가지고 있다.

stack의 맨 위에 데이터를 추가하는 것은 push, 맨 위의 데이터부터 하나씩 제거하는 것을 pop이라 한다.

 

 

📍 스택이 쓰이는 예시

➡️ 어떤 글을 잘못 썼거나 수정하고 싶을 때 되돌리기를 하거나 그렇게 되돌린 것을 취소할 때 스택의 원리가 이용된다.

➡️ JS의 모든 함수 호출은 스택 자료 구조로 이루어져 있다.

 

 

📍 시간 복잡도

1️⃣ push (삽입)

스택의 크기가 매우 큰 상태여도 자료를 맨 위에 하나만 올리면 되기 때문에 다른 작업 필요 없이 push 한 번의 노력만 된다. 따라서 시간 복잡도는 O(1)이다.

 

2️⃣ pop (삭제)

스택이 매우 크더라도 마찬가지로 맨 위에 있는 자료를 하나만 빼내면 되기 때문에 다른 작업 필요 없이 pop 한 번의 노력만 하면 되므로 시간 복잡도는 O(1)이다.

 

3️⃣ search (검색)

맨 위에 있는 데이터는 한번에 찾는 것이 가능하지만, 가장 아래에 있는 데이터를 검색하려면 위에서부터 하나씩 데이터들을 거쳐야 하기 때문에 결국에는 모든 데이터들을 찾아봐야 한다.

따라서 시간 복잡도는 데이터의 개수만큼인 O(n)이다.

 

 

📍 JS로 스택 구현하기

✔️ stack의 ADT(Abstract Data Type)

* ADT란, 데이터를 구체적으로 구현하는 방식은 생략하고 데이터의 추상적인 형태와 데이터를 이루는 방법만을 정해놓은 것이다.

 

ADT	종류	설명
Array	배열	stack에 해당
push	함수	stack에 새 요소 추가
pop	함수	stack의 맨 위에 있는 요소 삭제 (배열의 맨 마지막 인덱스에 있는 요소 삭제)
peek	함수	stack의 맨 위에 있는 요소 삭제 (배열의 마지막 요소 확인)
lefts	함수	stack에 있는 모든 요소를 문자열로 반환
clear	함수	stack에 있는 모든 요소 삭제
empty	함수	stack에 남은 요소가 있는지 확인

 

위를 활용하여 스택을 구현하면 다음과 같이 된다.

 

class Node {
  constructor(value) {
    // stack에 추가할 값 (value는 인자로 받아야 함.)
    this.value = value;
    // stack에서 위 value 이전에 들어간 값(한 칸 아래의 값)
    this.next = null;
  }
}

class Stack {
  constructor() {
    // stack에서의 가장 윗부분 (마지막 요소)
    this.top = null;
    // stack에서의 가장 아래부분 (첫번째 요소)
    this.bottom = null;
    // 스택의 길이 (스택 안의 요소 개수)
    this.length = 0;
  }
  // 스택에 쌓인 가장 마지막 원소를 확인하는 메소드
  peek() {
    return this.top;
  }
  // stack의 맨 위(마지막 요소로)에 데이터를 추가하는 메소드
  push(value) {
    // newNode 생성 (stack에 추가될 값을 생성하는 것임)
    const newNode = new Node(value);
    
    // stack의 길이가 0이라면
    if (this.length === 0) {
      // stack의 맨 위(마지막 원소)에는 아까 생성한 newNode가 들어감.
      this.top = newNode;
      // stack의 맨 아래(첫번째 원소)도 마찬가지 (원소가 하나밖에 없으므로 맨 위 값과 맨 아래 값이 같음)
      this.bottom = newNode;
      // stack의 길이가 1 이상일 경우
    } else {
      // holdingPointer 변수에 stack에서 가장 위에 있는 원소를 할당해줌. (아직 새 원소 들어가기 전)
      const holdingPointer = this.top;
      // stack의 윗부분을 newNode로 업데이트 해 준다.
      this.top = newNode;
      // stack의 가장 위에 있는 노드의 이전 노드는 holdingPointer가 된다.
      this.top.next = holdingPointer;
    }
    // newNode를 추가하고 나면 stack의 길이 1 증가
    this.length++;
    // stack 반환
    return this;
  }
  // stack의 맨 위 요소를(마지막 원소를) 삭제하는 메소드
  pop() {
    // stack의 맨 마지막 요소가 존재하지 않을 때, 삭제할 수 없으니 그냥 null 반환 후 끝
    if (!this.top) return null;
    // stack의 맨 위(마지막) 요소와 맨 아래(처음) 요소가 일치할 때
    if (this.top === this.bottom) {
      // 원소를 제거하면 stack의 맨 아래(처음) 요소가 없어지는 것이므로
      this.bottom = null;
    }
    // top은 한 칸 아래에(이전에) 있었던 요소가 됨.
    this.top = this.top.next;
    // 하나 삭제했으므로 stack의 길이 1 감소
    this.length--;
    // stack 반환
    return this;
  }
}

 

위에서 만든 stack 클래스를 다음과 같이 이용해 볼 수 있다.

 

// Stack 클래스의 인스턴스 myStack 생성
const myStack = new Stack();
console.log(myStack);     // Stack {top: null, bottom: null, length: 0}

// 3개의 Node Stack에 추가
myStack.push('google');
myStack.push('facebook');
myStack.push('udemy');
console.log(myStack);     // Stack {top: Node, bottom: Node, length: 3}
console.log(myStack.top);     // Node {value: 'udemy', next: Node}
console.log(myStack.peek());     // (바로 위와 같은 결과를 볼 수 있는 코드) Node {value: 'udemy', next: Node}
console.log(myStack.bottom);     // Node {value: 'google', next: null}

// 추가한 3개 Node 모두 삭제
myStack.pop();
myStack.pop();
myStack.pop();
console.log(myStack);     // Stack {top: null, bottom: null, length: 0}

 

 

 

📋 Stack Overflow

재귀 함수를 무한 호출했을 때 나오는 대표적인 에러이다.

 

📍 스택과 연관된 함수 실행 원리

아래와 같은 예시 코드를 살펴보자.

 

function a(data) {
  b(data + 1);
}

function b(data) {
  c(data + 1);
}

function c(data) {
  console.log('스택이 내부적으로 사용되었습니다 ' + data);
}

a(1);     // 스택이 내부적으로 사용되었습니다 3

 

위의 경우 우선 a 함수가 1이라는 인수를 전달받아 스택에 쌓이게 된다.

a 함수 안에서 b 함수가 실행되므로 b 함수 실행을 위해 stack에서 a 위에 b 함수가 쌓이게 된다. b 함수는 1 + 1인 2를 인수로 전달받게 된다.

또, b 함수 내에서 c 함수가 실행되므로 c 함수 실행을 위해 stack에서 b 함수 위에 c 함수가 쌓이게 된다. c 함수는 2 + 1인 3을 인수로 전달받게 되고 console.log가 실행되어 '스택이 내부적으로 사용되었습니다 3'이 출력되게 된다.

이후에 c 함수가 종료되면 stack에서 pop되게 된다.

c 함수가 종료되면 b 함수도 끝이므로 b 함수도 pop되고, b 함수가 끝나면 a 함수도 끝이므로 마지막으로 a 함수가 pop되게 된다.

즉, stack에는 [a 함수, b 함수, c 함수] 이렇게 쌓이게 되고, pop될 때는 c 함수부터 차례로 pop된다.

 

다음과 같은 재귀 함수에서도 같은 원리로 동작한다.

 

function d(data) {
  if (data == 50) {
    console.log('재귀 함수의 스택입니다 ', data);
  } else {
    d(data + 1);
  }
}

d(1);     // 재귀 함수의 스택입니다 50

 

위의 경우 data가 50이 되기 전까지는 data + 1이 되면서 계속 stack에 함수 d가 누적되게 된다.

즉, data가 1일 때부터 50이 될 때까지 stack에 [함수 d, 함수 d, 함수 d,......] 이런 식으로 50번 쌓인다.

data가 50이 되면 console.log가 실행되어 '재귀 함수의 스택입니다 50'이 출력되고 undefined를 반환하면서 50번째 함수(stack에서 가장 위에 있는 함수)가 종료되고 stack에서 pop되게 된다.

50번째 함수가 종료되면 49번째 d 함수도 끝이므로 pop이 된다. 이런 식으로 1번째 함수까지 pop되게 된다.

 

stack overflow는 다음과 같이 정지 조건을 달지 않고 재귀 함수를 계속 돌릴 때 나타난다.

 

function d(data) {
    d(data + 1);
}

d(1);     // Uncaught RangeError: Maximum call stack size exceeded

 

위와 같은 경우 stack 메모리가 다 찰 때까지 함수 d가 계속 쌓이게 되고, 결국 stack overflow가 일어나 프로그램이 에러를 뱉어버린다.