[알고리즘👽] 15. 스택과 큐

해당 포스팅은 알고리즘 스택과 큐에 대해 다룹니다. Udemy JavsScript 알고리즘 & 자료구조 마스터 클래스를 공부하며 정리한 내용입니다.

스택(Stack) 소개

목표

• 스택의 정의
• 활용 사례 배우기
• 스택에 대한 명령들을 코딩

스택이란?

• 데이터 구조, 데이터의 모음
• 후입선출 원칙을 따르는 데이터의 모음
• 나중에 들어온 것이 먼저 나가는 것.

어떻게 사용하나요?

설거지를 할 경우 가장 최근에 사용한 그릇이 가장 위에 있을 것이다.그릇을 치우려면 가장 위에서부터 치워야 합니다.

스택의 시각화

사용하는 곳

• 함수 호출을 다루는 상황
• Undo / Redo
• Routing(인터넷 방문기록)

배열로 스택 만들기

var stack1 = []

stack1.push("google")
stack1.push("instagram")
stack1.push("youtube")

stack //["google","instagram","youtube"]
//제거시는 pop

var stack2 =[]

stack2.unshift("create new file")
stack2.unshift("resize file")
stack2.unshift("cloned out wrinkle")

stack2
// ["cloned out wrinkle", "resize file", "create new file"]
// 제거시는 shift

push, pop 보다 unshift, shift가 더 효율이 좋지않다.

스크래치로 자신만의 스택 작성하기

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

class Stack {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.first){
            this.first = newNode;
            this.last = newNode;
        } else {
            var temp = this.first;
            this.first = newNode;
            this.first.next = temp;
        }
        return ++this.size;
    }
    pop(){
        if(!this.first) return null;
        var temp = this.first;
        if(this.first === this.last){
            this.last = null;
        }
        this.first = this.first.next;
        this.size--;
        return temp.value;
    }
}

스택의 빅오(BIG O)

Insertion	O(1)
Removal	O(1)
Searching	O(n)
Access	O(n)

💡 요약

• 후입선출의 특성을 가지는 데이터구조. 마지막의 들어온 값이 항상 첫번째로 나간다.
• 실행 취소나 다시 실행 같은 기능에도 사용됩니다. 브라우저를 사용할 때 접속 기록을 추적할 때와 같이 아주 많은 곳에서 쓰인다.
• 자바스크립트에 내장된 데이터 구조는 아닙니다. 하지만 코딩하기 쉽다.

큐(Queue) 소개

스택과 큐는 보통 묶어서 다룹니다.

목표

• 큐의 정의
• 큐의 사용 사례 이해
• 직접 큐 데이터 구조 코딩

큐란?

• 선입 선출 구조 First In First Out

시작하기 전에

• 큐는 어디에나 존재한다. 줄을 서는 모습릉 생각해보라.
• 그러나 프로그래밍에서는 컴퓨터가 정말 익숙하게 하는 일이기도 합니다. 만약 게임을 하고 있거나, 특히 온라인 게임에서 접속하려고 대기하고 있다면 보통 가장 오래 기다린 사람을 추적하는 큐데이터 구조가 있어서 게임에 먼저 접속하도록 해줍니다.
  • Background task
  • Uploading resources
• 보통 무언가 추가하기 위해 사용하는 키워드는 enqueue 이고 삭제할 때 사용하는 것은 dequeue이다.

배열로 큐 빌딩하기

간단하고 짧은 코딩에 최적화 되어있다. 그러나 큐 클래스를 직접 코딩하는 거시 훨씬 더 가볍기 때문에 둘 다 알아둘 필요가있다.

배열을 사용해서 큐 만들기

let q = [];

q.push("FIRST");
q.push("SECOND");
q.push("THIRD");

// q = ["FIRST", "SECOND", "THIRD"];

q.shift();
q.shift();
q.shift();

q.unshift("FIRST");
q.unshift("SECOND");
q.unshift("THIRD");

// q = ["THIRD", "SECOND", "FIRST"];

q.pop();
q.pop();
q.pop();

스크래치로 자신만의 큐 작성하기

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

class Node{
    constructor(value){
        this.value = value;
        this.next = null;
    }
    enqueue(val){
        var newNode = new Node(val);
        if(!this.first){
                this.first = newNode;
                this.last = newNode;
        } else {
                this.last.next = newNode;
                this.last = newNode;
        }
        return ++this.size;
    }
    dequeue(){
        if(!this.first) return null;

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

큐의 빅오 (BIG O)

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

💡 요약

• 큐는 선입선출(FIFO), 스택은 후입선출
• 큐는 업무처리할 때 유용하고 우리가 앞으로 보게될 더 복잡한 알고리즘과 데이터 구조에 사용된다.
• 삽입과 제거는 O(1)