자바스크립트 자료구조 Ⅲ

young-gue Park·2023년 1월 14일

JavaScript 스택 큐

JavaScript

목록 보기

6/20

⚡ 자바스크립트로 보는 자료구조 Ⅲ

📌 스택(Stack)

Last In First Out (후입선출)
가장 나중에 들어온 요소가 가장 먼저 나가는 선형 자료구조
ex) 프링글스 통에서 과자 꺼내기
Push(넣기), Pop(빼기)의 과정을 통해 Top 요소를 넣거나 뺀다.

💡 스택 메모리: 함수가 호출되며 생성되는 지역변수, 매개변수가 저장되는 메모리 영역

배열로 표현하는 것이 유리하다.

// 배열로 구현한 스택
const stack = [];
console.log(stack[0]);
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack);

// Pop
stack.pop();
console.log(stack);

// Get Top
console.log(stack[stack.length-1]);

🖨 출력 결과

출력 결과

📌 큐(Queue)

First In First Out (선입선출)
가장 먼저 들어온 요소가 가장 먼저 나가는 선형 자료구조
ex) 대기열
Enqueue(넣기)롤 통해 Rear에 요소를 넣고, Dequque(빼기)를 통해 Front 요소를 뺀다.
Linear Queue와 Circular Queue가 존재한다.

🔷 선형 큐(Linear Queue)

배열로 표현 가능하나 삽입 후 배열 요소를 앞으로 당기는 과정에서 선형 시간이 소요되며 front와 rear가 무한정으로 커질 수 있다.
연결 리스트로 표현하는 것이 유리하다.

❗ shift 함수는 절대 쓰지 말 것, Queue에서 기대하는 로직이 실행되지 않는다.

// 선형 큐 (배열로 구현)
class Queue {
    constructor() {
        this.queue = [];
        this.front = 0;
        this.rear = 0;
    }

    enqueue(value) {
        this.queue[this.rear++] = value;
    }

    dequeue() {
        const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front += 1;
        return value;
    }

    peek() {
        return this.queue[this.front];
    }

    size() {
        return this.rear - this.front;
    }
}

🖥 테스트 코드

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(4);
queue.enqueue(8);
console.log(queue.dequeue());
queue.enqueue(7);
console.log(queue.size());
console.log(queue.peek());
console.log(queue.dequeue());
console.log(queue.dequeue());

🖨 출력 결과

연결 리스트로 표현한 선형 큐

// 연결 리스트로 구현한 큐
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class Queue2 {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    enqueue(newValue) {
        const newNode = new Node(newValue);
        if (this.head === null) {
            this.head = this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.size+=1;
    }

    dequeue() {
        const value = this.head.value;
        this.head = this.head.next;
        this.size -= 1;
        return value;
    }

    peek() {
        return this.head.value;
    }
}

🖥 테스트 코드

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(4);
queue.enqueue(8);
console.log(queue.dequeue());
queue.enqueue(7);
console.log(queue.size);
console.log(queue.peek());
console.log(queue.dequeue());
console.log(queue.dequeue());

🖨 출력 결과

🔷 환형 큐(Circular Queue)

Front와 Rear가 이어져있는 큐이다.
연결 리스트로 구현해도 별 다른 이점이 없기 때문에 주로 배열로 구현한다.

// 배열로 구현한 환형 큐
class CircularQueue {
    constructor(maxSize) {
        this.maxSize = maxSize;
        this.queue = [];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    enqueue(value) {
        if(this.isFull()) {
            console.log("Queue is full.");
            return;
        }
        this.queue[this.rear] = value;
        this.rear = (this.rear + 1) % this.maxSize;
        this.size+=1;
    }

    dequeue() {
        const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front = (this.front+1) % this.maxSize;
        this.size -= 1;
        return value;
    }

    isFull() {
        return this.size === this.maxSize;
    }

    peek() {
        return this.queue[this.front];
    }
}

🖥 테스트 코드

const queue = new CircularQueue(4);
queue.enqueue(1);
queue.enqueue(4);
queue.enqueue(8);
console.log(queue.dequeue());
queue.enqueue(7);
console.log(queue.size);
console.log(queue.peek());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.isFull());