[자료구조] 스택(stack), 큐(queue), 덱(deque)

심해목이·2023년 1월 6일

자료구조

목록 보기

1/5

1. 스택(stack)

한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조. LIFO(Last In Fisrt Out).

스택은 정해진 방향으로만 쌓을 수 있으며 top으로 정한 곳을 통해서만 접근이 가능하다. 새로 삽입되는 데이터는 top이 가리키는 가장 맨 위에 저장되며 자료를 삭제할 때도 top이 가리키는 부분부터 삭제가 가능하다. 스택의 삽입 연산은 push, 삭제 연산은 pop이라 칭한다.

책상에 책을 쌓아두는 경우가 유사한 예시라 볼 수 있겠다. 웹 브라우저에서 뒤로가기를 누르면 바로 이전 페이지로 돌아가는 방식이 스택을 활용한 방식이다.

만약 스택이 비어있을 때 pop연산을 한다면 스택 언더플로우(stack underflow), 스택이 꽉 차있을 때 push연산을 한다면 스택 오버플로우(stack overflow)가 발생한다.

구현

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

class Stack {
    constructor() {
        this.top = null;
        this.length = 0;
    }

    push(data) {
        const newNode = new Node(data);
        if(!this.length) 
            this.top = newNode;
        else {
            const preNode = this.top;
            this.top = newNode;
            this.top.next = preNode;
        }
        this.length++;
        return this;
    }

    pop() {
        if(!this.top) return null //underflow
        const pop = this.top;
        this.top = this.top.next;
        this.length--;
        return pop.data;
    }
}

const stack = new Stack();
console.log(stack);
stack.push('A');
stack.push('B');
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());

2. 큐(queue)

먼저 넣은 데이터가 먼저 나오는 선형 구조. FIFO(First In First Out).

스택과는 반대로 먼저 들어온 데이터가 먼저 나가는 구조이다. 가장 앞부분, 삭제 연산이 수행되는 곳을 front, 삽입 연산이 이루어지는 가장 뒷부분을 rear라 한다. 스택이 top에서만 제한적으로 접근이 이루어지는 것과 차이점을 보인다. 큐의 삽입 연산을 인큐(enQueue), 삭제 연산을 디큐(deQueue)라 칭한다.

놀이공원이나 식당에서 줄을 서서 들어가는 상황과 같다.

만약 큐가 비어있을 때 get연산을 한다면 큐 언더플로우(queue underflow), 큐가 꽉 차있을 때 put연산을 한다면 큐 오버플로우(queue overflow)가 발생한다.

종류

선형 큐
환형 큐 (원형 큐)

참고로, 배열을 사용해 큐를 구현했을 때 한정된 경우로 링크드 리스트를 사용해 큐를 구현하면 환형 큐를 사용하지 않아도 이러한 단점을 극복할 수 있다.

구현

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

class Queue {
    constructor() {
        this.front = null;
        this.rear = null;
    }

    isEmpty() {
        return this.front == null && this.rear == null; //빈 큐면 true 리턴
    }

    enQueue(data) {
        const newNode = new Node(data);
        if(this.isEmpty()) 
            this.front = newNode;
        else
            this.rear.next = newNode;
        this.rear = newNode;
    }

    deQueue() {
        if (this.isEmpty() || this.front === null) return null;
        const pop = this.front.data;
        this.front = this.front.next;
        return pop;
    }
}

const queue = new Queue();
queue.enQueue('A');
queue.enQueue('B');
console.log(queue.deQueue());
console.log(queue.deQueue());
console.log(queue.deQueue());

3. 덱(deque)

양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조의 한 형태.

덱은 Double-ended Queue의 약자로, 두 개의 포인터를 사용하여 양쪽에서 삭제와 삽입을 수행할 수 있다. 스택과 큐를 합친 형태로 생각할 수 있다.

선언 이후 크기 변경이 가능하며 중간에 데이터가 삽입될 때 다른 요소들을 앞, 뒤로 밀 수 있다. 새로운 데이터 삽입 시, 메모리를 재할당하고 복사하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입한다.

스크롤
셸프

구현


class Deque {
    constructor() {
        this.items = [];
        this.length = 0;
    }

    isEmpty() {
        return this.length === 0;
    }

    frontPush(data) {
        this.items.unshift(data);
        this.length++;
    }

    rearPush(data) {
        this.items.push(data);
        this.length++;
    }

    frontPop() {
        if (this.isEmpty()) return null;
        const pop = this.items[0];
        this.items.shift();
        this.length--;
        return pop;
    }

    rearPop() {
        if(this.isEmpty()) return null;
        const pop = this.items[this.items.length-1];
        this.items.pop();
        this.length--;
        return pop;
    }

}

const deque = new Deque;
deque.frontPush('B'); //B
deque.frontPush('A'); //A B
deque.rearPush('C'); //A B C
deque.rearPush('//BD'); //A B C D
console.log(deque.rearPop()); //D
console.log(deque.frontPop()); //A
console.log(deque.rearPop()); //C
console.log(deque.frontPop()); //B
console.log(deque.rearPop()); // null

출처
https://ko.wikipedia.org/wiki/%EC%9C%84%ED%82%A4%EB%B0%B1%EA%B3%BC:%EB%8C%80%EB%AC%B8
https://namu.wiki/w/%ED%81%90%28%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%29
<파이썬 알고리즘 인터뷰> p.260, 책만, 2020

심해목이

곰팡이 진화 과정

다음 포스트

[자료구조] 스택(stack), 큐(queue), 덱(deque)

자료구조

1. 스택(stack)

구현

2. 큐(queue)

구현

3. 덱(deque)

구현

[자료구조] 해시(Hash)

0개의 댓글