큐/스택 알고리즘 문제 with JavaScript

큐(Queue) 데이터 구조

아래는 add, remove, peek 메서드를 포함하는 큐 클래스다

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

	add(record) {
		this.data.unshift(record)
	}

	remove() {
		return this.data.pop()
	}
    
    peek() {
		return this.data[this.data.length - 1]
	}
}

 

큐 Weave

두 개의 큐를 교차로 결합하여 새로운 큐를 반환하기

위에서 만든 큐 클래스를 사용해야 한다

function weave(sourceOne, sourceTwo) {
	const q = new Queue()

	while (sourceOne.peek() || sourceTwo.peek()) {
		if (sourceOne.peek()) {
			q.add(sourceOne.remove())
		}
		if (sourceTwo.peek()) {
			q.add(sourceTwo.remove())
		}
	}

	return q
}

 

스택(Stack) 데이터 구조

아래는 push, pop, peek 메서드를 포함하는 스택 클래스다

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

	push(record) {
		this.data.push(record)
	}

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

	peek() {
		return this.data[this.data.length - 1]
	}
}

 

스택으로 큐 만들기

두 개의 스택을 사용해서 큐 데이터구조를 구현하기

class Queue {
	constructor() {
		this.first = new Stack()
		this.second = new Stack()
	}

	add(record) {
		this.first.push(record)
	}

	remove() {
		while (this.first.peek()) {
			this.second.push(this.first.pop())
		}

		const removedItem = this.second.pop()

		while (this.second.peek()) {
			this.first.push(this.second.pop())
		}

		return removedItem
	}

	peek() {
		while (this.first.peek()) {
			this.second.push(this.first.pop())
		}

		const peekedItem = this.second.peek()

		while (this.second.peek()) {
			this.first.push(this.second.pop())
		}

		return peekedItem
	}
}