TypeScript와 Linked List로 스택 구현하기

스택은 자료구조의 하나로 FIFO(fisrt in first out)의 구조를 가진다. 

타입스크립트를 활용해 배열을 이용하지 않고 스택을 구현해 보자. 

 

Linked List

링크드리스드 자료구조를 이용해 만들 수 있다. 

https://www.geeksforgeeks.org/data-structures/linked-list/ 

Linked List Data Structure - GeeksforGeeks

 

 

/* 규격 정의.  
스택을 변경하거나 다른 종류의 스택을 만들었을 때 사용자는 몰라도 됨. 
인터페이스만 쓰고 있기 때문에 변경할 것이 없다. */
interface Stack {
  readonly size: number;
  push(value: string): void;
  pop(): string;
} // 두가지 기능이 있고, 사이즈라는 속성을 만들어 두었다.

type StackNode = {
  readonly value: string;
  readonly next?: StackNode; // 값이 있거나 없는 경우  StackNode|undefined; 와 같다.
}; // readonly 를 이용해서 값이 한번 정해지면 변경될 수 없도록 한다.

class StackImpl implements Stack {
  private _size: number = 0;
  private head?: StackNode;

  constructor(private capacity: number) {}
  get size() {
    return this._size;
  }
  push(value: string) {
    if (this.size === this.capacity) {
      throw new Error('Stack is full!');
    }
    const node: StackNode = { value, next: this.head };
    this.head = node;
    this._size++;
  }
  pop(): string {
    if (this.head == null) {
      throw new Error('Stack is empty!');
    }
    const node = this.head;
    this.head = node.next;
    this._size--;
    return node.value;
  }
}

const stack = new StackImpl(10);
stack.push('Ellie 1');
stack.push('Bob 2');
stack.push('Steve 3');
stack.push('Vincent 4');

console.log(stack);
/* StackImpl {
  capacity: 10,
  _size: 4,
  head: { value: 'Vincent 4', next: { value: 'Steve 3', next: [Object] } }
}
*/
console.dir(stack, { depth: null });
/*
StackImpl {
  capacity: 10,
  _size: 4,
  head: {
    value: 'Vincent 4',
    next: {
      value: 'Steve 3',
      next: { value: 'Bob 2', next: { value: 'Ellie 1', next: undefined } }
    }
  }
} 
*/
while (stack.size !== 0) {
  console.log(stack.pop());
}
/* 
Vincent 4
Steve 3
Bob 2
Ellie 1
*/

 

출력 값을 보면 뒤에 추가된 노드의 next가 앞의 Node를 가리키고 있는 구조로 스택이 만들어 진다. 

스택에서 값을 제거하면 head는 그 앞의 값을 가리키게 된다. 메모리에 저장되어 있던 제거된 값은

그 어떤 변수에서도 참조되지 않으므로 가비지 컬렉터에 의헤 제거되게 된다.