•
정의
◦
입력된 순서대로 출력하는 선형 자료구조로 FIFO 메커니즘을 가지고 있다.
•
특징
◦
데이터를 입력된 순서대로 유지한다.
◦
FIFO 메커니즘을 가지므로 입력된 순서대로 출력한다.
◦
동적 메모리다.
•
시간복잡도
조회 | 검색 | 삽입 | 제거 |
O(n) | O(n) | O(1) | O(1) |
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해준다.
