[Typescript] 자료구조 : 스택 (Stack)

 

스택의 모습

 

 

 

 

스택의 특징

• 탐색 시, O(n) 만큼 소요됩니다.
• 추가, 삭제 시, O(1) 만큼 소요됩니다.
• 최상위 노드를 top을 통해 기억하고 있습니다.
• 접시 쌓는 것과 비슷한 모양을 가지고 있습니다.

 

 

 

 

데이터 노드 구현하기

class Node {
    value: number;
    prev: Node | null = null;
    next: Node | null = null;

    constructor(value: number) {
      this.value = value;
    }
  }

prev, next 프로퍼티가 있습니다.

value 프로퍼티로 데이터를 받고 있고, 숫자 데이터만 받기로 정했습니다.

 

 

* 이번 글에서는 스택을 이중 연결 리스트를 이용해서 구현하기로 했습니다.

* 스택은 단방향 연결 리스트로도 구현 가능합니다만, 편의를 위해서 이중 연결 리스트를 사용하기로 했습니다.

 

 

 

[ 이중 연결 리스트 개념 ] 

[Typescript] 자료구조 : 이중 연결 리스트 (doubly-LinkedList)

 

 

 

 

스택 구현하기

class Stack {
    private top: Node | null = null;
    private size = 0;

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

    push(node: Node) {
      if (this.isEmpty()) {
        this.top = node;
        this.size = 1;
        return;
      }

      this.top.next = node;
      node.prev = this.top;
      this.top = node;

      this.size++;
    }

    pop(): Node | null {
      if (this.isEmpty()) {
        console.log("Stack is Empty!");
        return null;
      }

      const node = this.top;

      this.top = node.prev;
      node.prev = null;
      node.next = null;
      this.size--;

      return node;
    }
  }

 

 

 

 

구현한 코드를 테스트 해보기

const stack = new Stack();

stack.push(new Node(1));
stack.push(new Node(2));
stack.push(new Node(3));

console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());

 

console 출력값

Node { next: null, prev: null, value: 3 }
Node { next: null, prev: null, value: 2 }
Node { next: null, prev: null, value: 1 }
Stack is Empty!
null