자료구조 정리4 : Stack & Queue

Kimhojin_Zeno·2023년 3월 29일

queue stack 스택 자료구조 큐

자료구조 정리

목록 보기

4/9

Stack

후입선출

stack이란 서류더미를 생각하면 된다. 마지막으로 위에 놓은 것부터 다시 뺀다.

가장 마지막으로 추가된 요소는 가장 먼저 제거된다

콜스택, 실행취소 같은 상황에서 스택을 쓴다.

stack 구현

배열로 스택을 구현할 수 있다.

var stack = [];

stack.push()

stack.pop()

shift와 unshift를 써도 되지만 그렇게하면 매번 모든 엘리먼트의 인덱스를 수정해야하므로 비효율적이다.

단순히 후입선출만 필요하다면 배열이 아닌 연결 리스트로 구현해도 된다.

배열을 사용하지 않고 클래스로 구현할 수 있다. 단일 연결 리스트, 혹은 이중 연결 리스트를 사용한다.

단일 연결 리스트라면 리스트 맨 뒤에 추가하고 삭제하게 되면 리스트를 매번 순환해야 하니 맨 앞에다 shift와 unshift로 한다. 대신 이름만 push, pop으로 하는 것이다. 이렇게 맨 앞에 추가하고 삭제하면 가장 빠르게 작동할 수 있다. 상수값의 시간을 가진다.

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;   // 이름은 push지만 맨 뒤가 아니라 맨 앞에 추가한다. O(1)의 속도.
            this.first = newNode;
            this.first.next = temp;
        }
        return ++this.size;   // 사이즈를 1 키우고 출력.
    }
    pop(){
        if(!this.first) return null;
        var temp = this.first;
        if(this.first === this.last){
            this.last = null;
        }
        this.first = this.first.next;   // 이름은 pop이지만 맨 뒤가 아닌 맨 앞을 뺀다. 역시 O(1)
        this.size--;
        return temp.value;
    }
}

스택의 Big-O

insertion - O(1)

removal - O(1)

searching - O(n)

access - O(n)

삽입과 삭제가 모두 상수값. 빨리 된다. 스택을 다룰 때는 이것에 신경써야 한다.

탐색이나 인덱스 또는 위치를 사용해서 접근하는 것은 전혀 중요하지 않음. 그런게 필요하다면 다른 데이터구조를 써야 한다.

스택은 삽입과 제거가 가장 우선시된다.

Queue

선입선출

스택과 비슷하지만 순서가 다르다. 선입선출. 먼저 들어온 것이 먼저빠진다.

스택이 책상위에 서류더미라면, 큐는 놀이기구 앞에 줄이다. 가장 먼저 줄선 사람이 먼저 빠진다.

프린트의 대기열처럼 먼저 인쇄 누른 파일이 먼저 나온다.

추가할때 사용하는 키워드는 enqueue, 제거할때는 dequeue

queue 구현

배열을 사용해서 구현하면 push, shift로 구현한다. 단 이때는 shift를 사용해서 모든 엘리먼트에 인덱스가 재배정되는 작업이 불가피하다. 즉 큐를 구현할때는 배열을 사용하는것보다 직접 만드는 것이 성능이 훨씬 좋다.

연결리스트를 사용해서 구현한다.

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

class Queue {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    enqueue(val){  // 큐에 추가
        var newNode = new Node(val);  // 새로 노드를 만들고
        if(!this.first){  // 빈 큐라면 first로.
            this.first = newNode;
            this.last = newNode;
        } else {
            this.last.next = newNode;    // 아니라면 last의 다음에 넣는다.
            this.last = newNode;     // 그리고 last로 한다.
        }
        return ++this.size;
    }

    dequeue(){   // 큐를 뺄때.
        if(!this.first) return null;  // 빈 큐라면

        var temp = this.first;  // 큐의 맨앞 노드를 temp로.
        if(this.first === this.last) {
            this.last = null;   // 큐에 하나 뿐이라면
        }
        this.first = this.first.next;  // 큐의 first를 현재 first의 next로 지정.
        this.size--;   // 사이즈를 줄인다.
        return temp.value;   // 원래 맨앞 노드의 값을 리턴.
    }
}