공부했던 자료 정리하는 용도입니다. 재배포, 수정하지 마세요. 스택(Stack)과 큐(Queue)Stack과 QueueQueue 는 먼저 들어간 데이터를 먼저 꺼내는 FIFO구조로 되어있고, Stack 은 LIFO구조로 되어있어서 마지막에 저장한 데이터를 가장 먼저 꺼내게 된다. Stack 은 수식계산이나 워드프로세서의 undo/ redo, 또는 웹브라우저의 뒤로/앞으로 같은 기능들을 구현할 때 활용되고, 큐는 최근 사용 문서, 인쇄 작업 대기목록, 버퍼(buffer)등의 기능을 구현할 때 활용된다. Stack의 메서드
Queue의 메서드
실행결과
스택과 큐가 어떤구조로 되어있는지 확인하는 예제이다. 넣을 때는 0 , 1 , 2 로 같은 순서의 같은 값을 넣었지만 차이가 있는 것을 확인할 수 있다. Queue 는 먼저 넣은 것이 먼저 나오는 FIFO구조이기 때문에 넣은 순서대로 나오고, Stack 은 나중에 넣은것이 먼저 나오는 LIFO구조이기 때문에 넣은순서와 반대로 꺼내진 것을 알 수 있다. 자바에서는 스택을 Stack 클래스로 구현하여 제공하지만 큐는 Queue 인터페이스만 있고 별도의 클래스가 없다. 그래서 Queue 인터페이스를 구현한 클래스들을 사용해야 한다. PriorityQueueQueue 인터페이스의 구현체 중 하나로, 저장한 순서에 관계없이 우선순위(priority)가 높은 것부터 꺼내게 된다는 특징이 있다. null 을 저장하면 NullPointerException 이 발생한다. PriorityQueue 는 저장공간으로 배열을 사용하며, 각 요소를 힙(heap)이라는 자료구조의 형태로 저장한다. (자료구조의 heap과 JVM의 heap은 이름만 같고 다른 것들이다.) 실행결과
저장 순서가 3 , 1 , 5 , 2 , 4 인데도 출력 결과가 1 , 2 , 3 , 4 , 5 인 것을 확인할 수 있다. 우선순위는 숫자가 작을수록 높아져서 1 이 가장 먼저 출력된다. 숫자가 아닌 객체를 저장하려면 각 객체의 크기를 비교할 수 있는 방법을 제공해야 한다. 배열에 저장된 순서와 실제 우선순위가 다른 것은 PriorityQueue 가 각 요소를 힙이라는 자료구조의 형태로 저장한 것이라서 그렇다. Deque(Double-Ended Queue)Queue와 DequeQueue 의 변형으로, 한쪽 끝으로만 추가/삭제할 수 있는 Queue 와 달리, Deque 는 양쪽 끝에서 추가/삭제가 가능하다. Deque 의 조상은 Queue 이며, 구현체로는 ArrayDeque 와 LinkedList 등이 있다. Deque 는 Stack 과 Queue 를 하나로 합쳐놓은 것과 같아서 Stack 으로 사용할 수도 있고, Queue 로 사용할 수도 있다. |