•
정의
◦
순서가 보존되는 선형 자료구조의 일종으로 LIFO의 메커니즘을 가지고 있다.
•
특징
◦
데이터를 입력되는 순서대로 정렬한다.
◦
LIFO의 메커니즘을 가진다. 즉 입력된 순서의 역순으로 가져오는 방법을 갖고 있다.
◦
동적 메모리
•
시간복잡도
조회 | 검색 | 삽입 | 제거 |
O(n) | O(n) | O(1) | O(1) |
•
용도
◦
재귀적인 특징을 가지고 있어 프로그램을 개발할 때, 자주 쓰이는 자료구조다.
◦
후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록, 깊이우선탐색 등에 사용된다.
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()을 하게 되면 가장 먼저 왔던 데이터가 가장 먼저 출력된다.
▪
비어있지 않을 경우, 그냥 출력하면 된다.
