(Typescript) 데이터 구조: 스택

by

스택은 어떻게 생겼습니까?


스택 속성

  • 검색에는 O(n) 시간이 걸립니다.

  • 추가 및 제거에는 O(1) 시간이 걸립니다.

  • top으로 최상위 노드를 기억하십시오.
  • 쌓인 보드 모양입니다.

데이터 노드 구현

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

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

이전 및 다음 속성이 있습니다.

value 속성을 통해 데이터를 받고 있는데 숫자 데이터만 받기로 했습니다.

* 이 글에서 스택은 이중 연결 리스트나는 .

* 스택은 단일 연결 리스트이렇게도 구현할 수 있지만 편의상 이중 연결 리스트나는 .

(이중 연결 리스트 개념)

(Typescript) 데이터 구조: 이중 연결 목록

단일 연결 리스트 다음에는 이중 연결 리스트가 옵니다.

단방향 연결 리스트의 개념을 숙지하신 후 다시 오시는 것을 추천드립니다 🙂 (Typescript) 데이터 구조: 단방향 연결 리스트 데이터 구조를 배포합니다.

cheolsker.

구현 스택

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());

콘솔 출력

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

Related Posts: