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

 

스택 - First in First Out, 말 그대로 들어온 순서대로 pop되는 자료구조라는 뜻

큐 - Last in First Out, 말 그래도 나중에 들어온 순서대로 pop되는 자료구조라는 뜻

 

아래코드는 자바스크립트를 활용해 스택 두개로 큐를 구현, 큐 두개로 스택을 구현하는 예제이다.

1. 스택 두개로 큐 구현

큐를 스택으로 구현하기 위해서는 우선 두개의 스택이 필요하다.

constructor에 스택의 역할을 할 배열을 두개 선언하고, 한개는 enqueue(삽입)을 위한 배열, 다른 한개는 dequeue(삭제)를 위한 배열이다.

enqueue는 push를 통해서 일반으로 구현하면 되고, dequeue는 만약 두번째 배열이 비어있다면 해당 배열의 모든 요소를 pop하며 두번째 배열에 할당한다.

이렇게하면 두번째 배열안에 요소들은 위치가 반대로 바뀌고, 이후에 pop를 진행하게 되면 Last in First Out이라는 규칙을 지키면서 큐와 같은 기능을 구현할 수 있게 되는 것이다. 

• 삽입: O(1)
• 삭제 : O(N) (스택을 전부 비우고 다시 다른 스택에 push)

class QueueUsingStacks {
    constructor() {
        this.stack1 = [];
        this.stack2 = [];
    }

    enqueue(element) {
        this.stack1.push(element);
    }

    dequeue() {
        if (this.stack2.length === 0) {
            while (this.stack1.length !== 0) {
                this.stack2.push(this.stack1.pop());
            }
        }
        return this.stack2.pop();
    }
}

// 사용 예시
const queue = new QueueUsingStacks();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue.dequeue()); // 1
queue.enqueue(3);
console.log(queue.dequeue()); // 2

 

2. 큐 두개로 스택 구현

큐 두개로 스택을 구현할 때도, 두 개의 큐를 번갈아 가며 사용한다. 

push 작업은 현재 비어있는 큐에 데이터를 삽입하며, pop작업은 비어있지 않은 큐에서 데이터를 삭제한다. 

• 삽입: O(1)
• 삭제: O(N)

class StackUsingQueues {
    constructor() {
        this.queue1 = [];
        this.queue2 = [];
    }

    push(element) {
        this.queue2.push(element);
        while (this.queue1.length > 0) {
            this.queue2.push(this.queue1.shift());
        }
        //  queue1 와 queue2 Swap
        let temp = this.queue1;
        this.queue1 = this.queue2;
        this.queue2 = temp;
    }

    pop() {
        return this.queue1.shift();
    }
}

// 사용 예시
const stack = new StackUsingQueues();
stack.push(1);
stack.push(2);

console.log(stack.pop());

stack.push(3);
console.log(stack.pop()); // 3