Stack과 Queue란

java에서 제공되는 Stack과 Queue를 알아보기 전에 자료구조의 Stack과 Queue의 개념을 알아보자. 물론 둘이 차이가 있다는 것은 아니고 개념을 먼저 살펴보자는 말이다.

Stack은 마지막에 저장한 데이터를 먼저 꺼내게 되는 LIFO(Last In First Out)구조이고 Queue는 처음에 저장한 데이터를 가장 먼저 꺼내는 FIFO(First In First Out)의 구조이다.

스택과 큐를 구현하기 위해서는 어떤 컬렉션 클래스를 사용할까? 우선 스택은 ArrayList와 같이 순차적으로 데이터를 추가하고 삭제하므로 ArrayList를 사용하면 된다.

그리고 큐는 데이터를 꺼낼 때 항상 첫번째 데이터를 삭제하므로 ArrayList를 사용할 경우 데이터를 꺼낼 때 마다 데이터를 꺼내고 모든 데이터를 복사하여 이동하여야하는 메모리적 낭비가 심하게 된다. 그래서 LinkedList로 구현하여 추가/삭제가 쉽게 하는 것이 좋다.

java에서의 Stack과 Queue

java에서 스택은 class로 구현되어 있지만 큐는 class로 구현되어 있지 않고 인터페이스로만 정의해 놓았다. 그 이유는 Queue에 사용법에 따라 다양하게 제공되는 class들을 선택하여 사용하면 되는데. 이는 java의 다형성의 장점을 활용한 것이다. 각 class의 용도를 설명하기에는 너무 많고 어떤 class가 큐에 사용할 수 있는지 확인하려면 java api 문서를 참고하면 되는데

큐 페이지에서 All Known Implementing Classes에 표함되어 있는 class를 사용할 수 있다. 주로 LinkedList, PriorityQueue를 사용하는 것 같다.

실제 Stack과 Queue의 활용

그럼 이제 개념과 java에서 Stack과 Queue를 사용할 수 있게되었다면 어디다 활용을 해야할지 궁금할 것이다. 실생활에서 우리가 사용하고 있는 Stack의 예시로는 인터넷 브라우저의 뒤로가기 기능이다. 뒤로가기를 누르면 가장 늦게 삽입된 데이터로 바로 전에 탐색했던 페이지가 나온다. 그리고 또 뒤로가면 그 다음의 페이지가 나오게된다. 하지만 여기서 앞으로 가기의 기능을 사용하려면 하나의 Stack을 더 사용하면 된다. 뒤로가기를 눌렀을 때 뒤로가기 Stack에서 pop()한 내용을 앞으로가기 Stack에 push()해주고 서로 pop() push()를 반복하면 되는 것이다.

그리고 Queue의 경우 최근 사용한 명령어 리스트를 보는데 사용할 수 있다.

Priority Queue

Queue의 인터페이스 구현체 중 하나로 저장한 순서와 상관없이 우선순위(Priority)가 높은 순서로 꺼내게된다는 특징이 있다. 예를들어 3,1,2,5,4를 Priority Queue에 저장했을 때 출력 결과는 1,2,3,4,5로 확인할 수 있다. Null은 저장할 수 없고 저장하게 된다면 NullPointerException이 뜬다. 또한 Object type도 저장할 수 있는데 이때는 각 객체를 비교할 수 있는 방법을 제공해야한다.

Priority Queue는 기존에 LinkedList의 자료구조가 아닌 Heap의 자료구조 형태를 가지고 있기 때문에 저장할 때 항상 우선순위에 맞게 정렬을 할수 있는 것이다.

heap은 jvm에 구조의 heap과는 다른 개념이다

heap은 항상 부모의 우선순위가 자식보다 크다라는 조건을 만족하는 완전이진트리의 구조이다.

Deque(Dobule-Ended Queue)

Queue의 변형으로 한쪽으로만 추가/삭제를 할수 있는 Queue와 다르게 양쪽 끝에서 추가/삭제가 가능하다. Deque는 ArrayDeque와 LinkedList로 구현할 수 있다.