[자료구조]스택(Stack)과 큐(Queue)

✅ 스택(Stack)이란?

가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out, 후입선출)을 가진 자료구조이다. 스택은 가장 먼저 추가된 것이 가장 마지막에 제거되는 하나의 방식으로 그러한 구조를 만드는 방법은 여러 가지가 있다. 배열로 스택을 만든다고 가정하면, push와 pop메소드를 이용해 맨 마지막에 데이터를 삽입하고, 맨 마지막 데이터를 삭제하는 구조가 갖춰진다. unshift와 shift도 마찬가지이지만 비효율적이다. 그렇지만 사실 효율성만 따질 때는 배열을 스택으로 이용하지 않는 경우가 더 많다. 왜냐하면 인덱스 기반으로 정보에 접근할 필요가 없으니 인덱스들을 전부 다 가지고 있을 이유가 없다. 

 

재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰임.

🔥 PUSH 의사코드

• value를 받아들이는 함수를 선언하고, 해당 value로 새 node를 생성한다.
• stack에 node가 존재하지 않으면, first와 last속성을 새로 생성한 node로 설정한다.
• 노드가 하나라도 있을 경우에는 현재의 first를 저장하는 변수를 만든다.
• first 속성을 새롭게 생성한 node로 재설정한다.
• 해당 node의 next속성을 이전에 생성했던 변수로 설정한다.
• size 1 증가.

🤔 구현하기

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

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
    }
}

🔥 POP의사코드

• stack에 node가 존재하지 않으면, return null
• 현재 first 속성을 저장해 둘 변수를 생성한다.
• 만약 노드가 하나밖에 없으면 first와 last 속성을 null로 설정한다.
• 노드가 하나보다 많은 경우 first속성을 first.next로 설정해 준다.
• size 1 감소. 제거된 노드 반환

🤔 구현하기

class Stack {
    constructor() {
      ...
    }
    pop() {
        if(!this.first) return null;
        let temp = this.first;
        
        if(this.first === this.last) {
            this.last = null;
        }
        // 노드가 하나일 경우 last가 null이면 first.next도 null
        this.first = this.first.next;
        this.size--;
        return temp.value;
    }
}

🟢 스택의 빅오

Insertion - O(1)

Removal - O(1)

Searching - O(N)

Access - O(N)

✅ 큐(Queue)란?

먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out, 선입선출)을 지닌 자료구조이다. 스택처럼 큐를 코딩하는 방법 또한 많다. 

 

CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용된다. 

배열로 큐를 구현하면 위와 같이 push로 넣고, shift로 제거하거나, unshift로 넣고 pop으로 제거하면 된다. 두 방법 모두 성능이 썩 좋지 않기에 클래스로 작성하는 것이 나을 수 있다.

 

클래스로 구현할 때 연결 리스트를 이용할 것인데 곰곰히 생각해보면 맨 앞에서 추가하고, 맨 뒤에서 제거하는 것보다 맨 뒤에 추가하고 맨 앞에서 제거하는 것이 더 나은 성능을 제공한다. 왜냐하면 제거를 위해서 제거할 대상의 앞의 노드를 추적해야하기 때문이다. 이해했다면 직접 구현해보자.

🔥 Enqueue 의사코드

• value를 받아들이는 함수를 선언하고, 해당 value로 새 node를 생성한다.
• queue에 node가 존재하지 않으면, first와 last속성을 새로 생성한 node로 설정한다.
• 노드가 있는 경우, 현재 last의 next 속성이 새로운 node가 되도록하고, last 포인터를 맨 끝에있는 새로운 노드로 설정한다.
• size 1 증가.

🤔 구현하기

class Queue {
    constructor() {
    	...
    }
    enqueue(val) {
        let 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 의사코드

• 노드가 없다면, return null
• first 속성을 변수에 저장한다.
• first와 last가 같다면 null로 설정한다.
• 노드가 한개보다 많다면 first 속성의 next를 first로 설정한다.
• size 1 감소.

🤔 구현하기

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;
}

🟢 큐의 빅오

Insertion - O(1)

Removal - O(1)

Searching - O(N)

Access - O(N)