Stack 두 개로 Queue 한 개
•
하나의 stack에는 enqueue, 나머지 하나의 stack은 dequeue를 구현한다.
◦
enqueue
public void enqueue(int value) {
stack1.push(value);
}
Java
복사
▪
instack에 push()한다.
◦
dequeue
public int dequeue() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
Java
복사
▪
outsatck이 비어있을 경우, instack의 모든 요소를 pop() 후 outstack에 push()한다.
▪
outstack.pop()을 하게 되면 가장 먼저 왔던 데이터가 가장 먼저 출력된다.
▪
비어있지 않을 경우, 그냥 출력하면 된다.
Queue 두 개로 Stack 한 개
•
하나의 queue에는 push, 하나의 queue는 pop을 구현한다.
◦
push
public void push(int value) {
queue1.add(value);
}
Java
복사
▪
q1으로 enqueue하여 데이터를 저장
◦
pop
public int pop() {
if (queue1.isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
while (queue1.size() > 1) {
queue2.add(queue1.remove());
}
int value = (int) queue1.remove();
Queue temp = queue1;
queue1 = queue2;
queue2 = temp;
return value;
}
Java
복사
1.
queue1에 저장된 데이터의 갯수가 1개일 때까지 dequeue를 한 뒤, 추출된 데이터를 queue2에 추가한다.
2.
결과적으로 queue1에는 가장 마지막에 삽입된 데이터만 남게 되고 이를 dequeue()해서 가장 최근에 저장한 데이터를 반환할 수 있다.
3.
다음에 발생할 pop 연산을 위해 queue1과 queue2를 swap해준다.
