Stack과 Queue
자료 구조 스택(Stack)과 큐(Queue)
자료 구조(data structure)란 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 마지막에 저장한 데이터가 가장 먼저 나오는 후입선출(LIFO: Last In First Out) 자료 구조인 스택과 처음에 저장한 데이터가 가장 먼저 나오는 선입선출(FIFO: First In First Out) 자료 구조인 큐가 대표적이다.
- 스택
https://ko.wikipedia.org/wiki/스택
- 큐
https://ko.wikipedia.org/wiki/큐(자료구조)
자바에서는 스택은 Stack 클래스로 큐는 Queue 인터페이스로 제공하고 있으나 Stack 클래스의 경우 사용을 지양하고 있다(참고: https://dev.java/learn/storing-data-using-the-collections-framework/#deprecated). 대신 ArrayList와 같은 순차적으로 데이터를 추가하고 삭제하는 배열 기반의 컬렉션 클래스나 ArrayDeque 클래스로 대체할 수 있다. 큐의 경우 Queue 인터페이스를 구현하는 LinkedList 클래스를 사용하면 된다.
예를 들어 하루에 3잔만 판매하는 카페가 있다고 가정했다. 이 카페에서는 주문 목록을 Stack에 저장하였다.
public class Cafe {
public static void main(String[] args) {
Stack<Order> orderList = new Stack<>();
System.out.println("============= OPEN =============");
Scanner ordering = new Scanner(System.in);
while (orderList.size() < 3) {
System.out.print("주문하실 메뉴를 입력하세요: ");
Order order = new Order(ordering.next());
orderList.push(order);
}
int orderNo = 1;
while (!orderList.isEmpty()) {
System.out.println("\n>>> 주문 확인 중...");
System.out.println("주문번호 " + orderNo + "번 " + "메뉴: " + orderList.peek().getMenu());
System.out.println("\n>>> 음료 제조 중...");
Order order = orderList.pop();
System.out.println(order.getMenu() + " 나왔습니다.");
orderNo++;
}
System.out.println("============= CLOSE =============");
}
}- 실행 결과
문제는 주문한 음료를 고객에게 전달할 때 나타났다. Stack에 주문 목록을 작성해버려 제일 먼저 주문한 고객이 가장 늦게 음료를 받고 말았다. 그래서 Stack 대신 Queue로 주문 목록을 작성해 문제를 해결하였다.
public class Cafe {
public static void main(String[] args) {
Queue<Order> orderList = new LinkedList<>();
System.out.println("============= OPEN =============");
Scanner ordering = new Scanner(System.in);
while (orderList.size() < 3) {
System.out.print("주문하실 메뉴를 입력하세요: ");
Order order = new Order(ordering.next());
orderList.offer(order);
}
int orderNo = 1;
while (!orderList.isEmpty()) {
System.out.println("\n>>> 주문 확인 중...");
System.out.println("주문번호 " + orderNo + "번 " + "메뉴: " + orderList.peek().getMenu());
System.out.println("\n>>> 음료 제조 중...");
Order order = orderList.poll();
System.out.println(order.getMenu() + " 나왔습니다.");
orderNo++;
}
System.out.println("============= CLOSE =============");
}
}
Reference
