Section21 - 스택 & 큐

---

---

[스택]

 

데이터의 모음

압축적인 데이터 구조

후입선출(LIFO) - 가장 먼저 넣어진게 나중에 배출

 

- 함수호출상황에서 많이 사용됨

- undo / Redo

- 라우팅(방문기록)

 

[배열로 스택 만들기]

 

const stack = [];

//O
stack.push('google');
stack.push('insta');
stack.push('youtube');

stack.pop();

//X
stack.unshift('create new file');
stack.unshift('resize');
stack.unshift('wrinkle');

stack.shift()

[스택 만들기]

 

class Node {
  constructor(val){
    this.val = val;
    this.next = null;
  }
}

class Stack{
  constructor(){
    this.first = null;
    this.last = null;
    this.size = 0;
  }

  push(val){

    const newNode = new Node(val);

    if(this.size === 0){
      this.first = newNode;
      this.last = newNode;
    } else {
      
      const old = this.first;
      this.first = newNode;
      newNode.next = old;
    }

    return ++this.size;

  }

  pop(){
    if(this.size === 0) return null;
    
    const temp = this.first;
    
    if(this.first === this.last){
      this.last = null;
    }

    this.first = this.first.next;
    this.size--;
    return temp.val;
  }
}

[스택 BIG O]

삽입 - O(1)

제거 - O(1)

검색 - O(N)

접근 - O(N)

 

[스택 Recap]

- 후입선출

- 마지막으로 들어오면 제일 먼저 나감

- 일부언어에 내장되어있을 수 있음

- 걍 배열로 쓰는게 좋음

 

 

[큐]

 

스택의 짝궁

선입선출(FIFO)

 

- 백그라운드 작업

- 업로드

- 프린터

 

[배열로 큐 만들기]

const q = [];
//x
q.push('1');
q.push('2');
q.push('3');

q.shift();

//x
q.unshift('1');
q.unshift('2');
q.unshift('3');

q.pop();

[큐 만들기]

class Node{
  constructor(val){
    this.val = val;
    this.next = null;
  }
}

class Queue{
  constructor(){
    this.first = null;
    this.last = null;
    this.size = 0;
  }

  enqueue(val){
    const newNode = new Node(val);
    if(this.size === 0){
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }

    return ++this.size;
  }

  dequeue(){
    if(this.size === 0) return null;

    const temp = this.first;
    if(this.first === this.last){
      this.last = null;
    }
    this.first = this.first.next;
    this.size --;
    return temp.val;
  }
}

[큐 BIG O]

삽입 - O(1)

제거 - O(1)

검색 - O(N)

접근 - O(N)

 

[큐 Recap]

- 선입선출

- 업무처리에 유용하고, 다양한 데이터 구조에 사용됨

 

+p.s

자료구조부분이 완전히 이해되기 시작하고있음.

뭔가 알고리즘 푸는데 신세계가 보이기 시작하고 있음 히히