데이터 구조: 스택 및 큐

스택과 대기열은 면접 중에 질문을 받을 수 있는 일반적인 데이터 구조입니다. 높은 수준에서 Stack과 Queue가 무엇인지 살펴보겠습니다.

스택

스택은 LIFO(Last In First Out) 순서로 작동하는 선형 데이터 구조입니다. 접시 더미를 생각해 보십시오. 각 판은 기존 판 위에 쌓이고 마지막으로 쌓인 판이 먼저 제거됩니다. 스택 데이터 구조는 동일한 방식으로 작동합니다. 데이터는 구조의 끝에 추가되고 조치를 취하면 동일한 구조의 끝에서 제거됩니다.

대기줄

큐는 FIFO(First In First Out) 순서로 작동하는 선형 데이터 구조입니다. 대기열에 대한 일반적인 은유는 매장의 체크아웃 라인입니다. 줄 앞에 있는 사람이 먼저 체크아웃합니다. 큐 데이터 구조는 비슷한 방식으로 작동하며 데이터는 스택의 끝에 추가되고 제거되며 전면에서 처리됩니다.

구현

JavaScript 배열 및 배열 메서드를 사용하여 이러한 데이터 구조를 간단하게 구현해 보겠습니다.

스택

JavaScript 배열과 내장된 배열 메서드인 push 및 pop을 사용하여 간단한 스택 클래스를 만들 수 있습니다. 푸시는 배열 끝에 새 값을 추가합니다. Pop은 배열의 마지막 값을 제거하고 반환합니다. 이를 통해 데이터 구조가 LIFO 순서로 작동할 수 있습니다.

class Stack {
    constructor() {
        this.stack = []
    }

    push(value) {
        this.stack.push(value)
    }

    pop() {
        return this.stack.pop()
    }
}

const stack = new Stack()

stack.push('a') // -> stack: [ 'a' ] 
stack.push('b') // -> stack: [ 'a', 'b' ]
stack.push('c') // -> stack: [ 'a', 'b', 'c' ]

stack.pop() // -> returns 'c', stack: [ 'a', 'b' ]

대기줄

JavaScript 배열과 내장된 배열 메서드 푸시 및 시프트를 사용하여 간단한 대기열 클래스를 만들 수 있습니다. 푸시는 배열 끝에 새 값을 추가합니다. Shift는 배열의 첫 번째 값을 제거하고 반환합니다. 이를 통해 데이터 구조가 FIFO 순서로 작동할 수 있습니다.

class Queue {
    constructor() {
        this.stack = []
    }

    push(value) {
        this.stack.push(value)
    }

    shift() {
        return this.stack.shift()
    }
}

const queue = new Queue()

queue.push('a') // -> queue: [ 'a' ] 
queue.push('b') // -> queue: [ 'a', 'b' ]
queue.push('c') // -> queue: [ 'a', 'b', 'c' ]

queue.shift() // -> returns 'a', queue: [ 'b', 'c' ]

요약

스택과 대기열은 모두 선형 데이터 구조이지만 스택은 LIFO 순서로 작동하고 대기열은 FIFO 순서로 작동합니다. 이러한 구조의 제거 순서가 다르기 때문에 다양한 방식으로 유용할 수 있습니다.