728x90

Q. 2개의 스택(Stack)으로 큐(Queue)를 만들어라.
(어떠한 array도 만들어서는 안 되며, Stack의 push(), pop(), peek() method만 이용하여 작성해야한다)

정답 예시(Queue from Stacks)

🎈 먼저, Stack의 특징인 LIFO(Last In First Out)와 Queue의 특징인 FIFO(First In First Out)를 생각해야 한다.

Add()

큐의 add()를 구성하고 싶다면, 위의 그림처럼 그냥 1번 스택에 값을 넣어주면 된다. 이건 생각하는 것에 문제가 없다.
(편의상 앞으로 a스택, b스택이라고 이름을 정하고 얘기하겠다)
하지만, remove()와 peek()을 구성할 때 순서에 문제가 생긴다.

peek()

remove()를 구성하기 전에, peek()을 먼저 생각해보자.
a스택에서 마지막에 들어간 값을(this.data[this.data.length -1]) return 해버리면 LIFO 순서로 값이 나와버린다
따라서, 큐의 peek()를 구성할 때 LIFO를 FIFO로 바꿔줘야 한다.
그러기 위해서 a스택의 값을 pop()하여 b스택에 push()한다고 상상해보자. 위의 그림처럼 값이 옮겨질 것이다.
이렇게 값을 옮긴 후 b스택의 마지막 값을 가져오면 Queue의 peek()동일한 결과를 얻어낼 수 있다.

peek()과 구성은 같으며, 값이 제거되느냐, 아니냐의 문제다.
이렇게 값을 옮긴 후 b스택의 마지막 값을 pop()해주면 Queue의 remove()와 동일한 결과를 얻어낼 수 있다.

단, peek()과 remove()에서 모두 b스택으로 옮긴 값은 원하는 처리 후 다시 a스택으로 옮겨줘야한다.

정답

🔮 생성자(constructor)2개의 스택(Stack)을 생성해준다.
(단, Stack class를 가져오거나 따로 작성해둬야 한다)

add()에서는 a스택에 값을 push()한다.

remove()에서는 a스택 값을 b스택으로 옮긴 후 제거한 후, 다시 b스택 값을 a스택으로 옮겨준다.

peek()에서는 remove()와 마찬가지로 스택간 값을 옮겨주고 마지막 값을 가져온 후, 다시 값을 옮겨주면 된다.

큐와 스택 자료구조의 특성을 이해하기 좋은 예제다.

Full Code

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 record = this.second.pop();
 
while (this.second.peek()) {
this.first.push(this.second.pop());
}
 
return record;
}
 
peek() {
while (this.first.peek()) {
this.second.push(this.first.pop());
}
 
const record = this.second.peek();
 
while (this.second.peek()) {
this.first.push(this.second.pop());
}
 
return record;
}
}

+ Recent posts