Skip to content

13. Stacks + Queues.md

Latest commit

 

History

History
222 lines (164 loc) · 5.29 KB

13. Stacks + Queues.md

File metadata and controls

222 lines (164 loc) · 5.29 KB

Stacks + Queues

Stacks

목표

  1. 스택이란 무엇인가?
  2. 스택은 어디에 사용하는가?
  3. 스택 구현하기

1. 스택이란 무엇인가?

LIFO : Last In First Out

마지막에 들어간것이 처음으로 제거되는 자료구조입니다.

책같이 쌓여있는 물건을 맨 위에서부터 꺼내는 방식과 같습니다.

2. 어디에 사용하는가?

  • 재귀에서 사용했던 Call Stack도 Stack입니다.
  • 함수 호출을 관리할떄 사용합니다.
  • 워드에서 Undo(Ctrl + z) / Redo를 할때 사용합니다.
  • 라우팅(우리가 방문한 기록)

3. 구현

1. 배열을 사용해서 구현할 수 있습니다.

// 효율적
let stack = [];

stack.push('Google');
stack.push('Instagram');
stack.push('youtube');

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

// 비효율적
// shift와 unshift가 index를 바꿈
let stack2 = [];

stack2.unshift('Google');
stack2.unshift('Instagram');
stack2.unshift('youtube');

console.log(stack2.shift());
console.log(stack2.shift());
console.log(stack2.shift());

2. Singly Linked List를 사용해서 구현할 수 있습니다.

  • pop과 push를 사용하게 되면 pop을 사용할 때 마지막까지 Loop를 사용해야하기 때문에 메모리 소모가 많습니다.
  • 따라서 unshift와 shift를 사용해서 Stacks를 구현하겠습니다.
class Stack {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
  push(val) {
    let newNode = new Node(val);
    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    } else {
      let temp = this.first;
      this.first = newNode;
      this.first.next = temp;
    }
    return ++this.size;
  }
}

  • Pushing 의사코드

    1. 함수는 값을 인자로 받습니다.
    2. 받은 값을 이용해 새 노드를 만듭니다.
    3. if 노드가 없으면 first와 last 프로퍼티를 새로 생성한 노드로 지정합니다.
    4. 적어도 하나 이상의 노드가 존재한다면 stack 맨 처음에 노드를 추가합니다.
    5. 새로 생성한 노드를 first로 지정합니다.
    6. 이전에 생성한 노드의 next를 지정합니다.
    7. 사이즈를 1 증가시킵니다.

  • Push 구현

      push(val) {
    let newNode = new Node(val);
    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    } else {
      let temp = this.first;
      this.first = newNode;
      this.first.next = temp;
    }
    return ++this.size;
  }

  • Pop 의사코드

    1. if 스택에 아무것도 없으면 return null
    2. 스택의 첫번째 프로퍼티를 저장할 임시 변수를 만들고 저장합니다.
    3. if 노드 한개만 있으면, first와 last 프로퍼티를 null로 합니다.
    4. if 노드가 한개 이상이면 temp에 저장된 첫번째 노드의 next를 새 first로 지정합니다.
    5. 사이즈를 1 감소합니다.
    6. 제거한 node를 return 합니다.

  • Pop 구현

      pop() {
    if (!this.fist) return null;
    let temp = this.fist;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return temp.val;
  }

BIG O of Stacks

  • Insertion - O(1)
  • Removal - O(1)
  • Searching - O(N)
  • Access - O(N)

Stacks 정리

  • 스택은 LIFO인 자료구조 입니다. 가장 마지막에 들어간 값이 맨 처음으로 출력됩니다.
  • 스택은 함수 호출에 사용되고, undo/redo,라우팅(브라우저 기록)에도 사용됩니다.
  • JavaScript에는 built in 자료구조가 없지만 비교적 쉽게 구현할 수 있습니다.

Queue

목표

  • 큐 정의
  • Use case
  • 구현

1. 큐란 무엇인가?

FIFO : First In First Out

처음 들어간 밸류가 처음 나오는 자료구조입니다.

2. 어디에 사용하는가?

  • 백그라운드 작업
  • Uploading
  • Printing / Task 작업

3. 구현

  • Enqueue 의사코드
  1. 함수는 값을 인자로 받습니다.
  2. 인자로 받으 값으로 새 노드를 만듭니다.
  3. if 노드에 아무것도 없으면, 새로 만든 노드를 first와 last로 설정합니다.
  4. 그렇지 않으면, 새로만든 노드를 last의 next로 지정하고 그 노드를 last로 다시 설정합니다.

  • Enqueue 구현

      enqueue(val) {
    let newNode = new Node(val);
    if (!this.first) {
      this.first = newNode;
      this.lats = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    return ++this.size;
  }

  • Dequeue 의사코드

    1. if first 프로퍼티가 없으면 return null을 합니다.
    2. first 프로퍼티를 변수에 저장합니다.
    3. if (this.first === this.last)이면 first와 last를 null로 설정합니다.
    4. if 노드가 한개보다 많으면, first 프로퍼티로 first의 next를 설정합니다.
    5. 길이를 1 감소시킵니다.
    6. 삭제한 노드를 return 합니다.

  • Dequeue 구현

      dequeue() {
    if (!this.first) return null;
    let temp = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return temp.value;
  }