[Java] - Stack & Queue

자바에서 제공하는 Stack과 Queue에 대해 알아보자.
스택과 큐 개념 자세한 설명은 자료구조 - 스택/큐 포스팅 참조

스택과 큐를 구현하기 위해서 어떤 컬렉션 클래스를 사용하는게 좋을까?

• 스택
  • 순차적 데이터 추가/삭제
  • ArrayList와 같은 배열기반의 컬렉션이 적합
• 큐
  • 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제
  • 즉 중간에 데이터 추가/삭제가 쉬운 LinkedList가 적합

간단하게 자바 Stack과 Queue를 사용하는 예제를 살펴보자.

실행

Stack<Integer> st = new Stack<>();
Queue<Integer> q = new LinkedList<>();   //  Queue 인터페이스의 구현체인 LinkedList 사용

st.push(1);
st.push(2);
st.push(3);

q.offer(1);
q.offer(2);
q.offer(3);

System.out.println("=====Stack=====");
while (!st.empty())
    System.out.println(st.pop());

System.out.println("=====Queue=====");
while (!q.isEmpty())
    System.out.println(q.poll());

결과

=====Stack=====
3
2
1
=====Queue=====
1
2
3

• 큐는 먼저 넣은것이 먼저 꺼내지는 (FIFO)
• 스택은 먼저 넣은것이 나중에 꺼내지는 (LIFO)
• 자바에서 스택은 Stack 클래스 로 제공하고 있지만 큐는 Queue 인터페이스로 정의해놨다.
  • Queue 인터페이스를 구현한 클래스 중 하나를 선택해서 사용
  • 위의 예제에서는 LinkedList 사용
  • 구현 클래스 참고
    
    

---

PriorityQueue

• Queue 인터페이스의 구현체 중 하나
• 저장한 순서에 관계없이 우선순위(priority)가 높은 것부터 꺼냄
• null은 저장할 수 없음
• 각 요소를 '힙(heap)'이라는 자료구조로 저장
• 힙에 대한 자세한 내용은 자료구조 - 힙 포스팅 참고
  

실행

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(10);
pq.offer(3);
pq.offer(6);
pq.offer(2);

while (!pq.isEmpty())
    System.out.println(pq.poll());

결과

2
3
5
6
10

저장순서는 5, 10, 3, 6, 2 인데 출력 순서는 2, 3, 5, 6, 10 인 것을 확인할 수 있다.
기본 생성자는 최소힙을 사용하므로 최대힙 즉 우선순위가 높은 순서대로 출력하고 싶다면 아래와 같이 사용하면 된다.

Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

---

Deque(Double-Ended Queue)

• Deque(덱 또는 디큐)은 양쪽 끝에 추가/삭제 가능

• Deque의 조상은 Queue이고, 구현체로는 ArrayDeque, LinkedList 등이 있다.

• 스택과 큐를 하나로 합쳐놓은 것과 같다.

  • 어느쪽으로든 사용가능

  • 덱 메소드에 대응하는 큐와 스택의 메소드

    Deque	Queue	Stack
    offerLast()	offer()	push()
    pollLast()	-	pop()
    peekFirst()	peek()	-
    peekLast()	-	peek()

아래는 Deque 사용예제이다.

실행

Deque<Integer> deque = new ArrayDeque<>();

//  Queue mode
deque.offerLast(1);
deque.offerLast(2);
deque.offerLast(3);

int one = deque.pollFirst();
int two = deque.pollFirst();

System.out.println(one);
System.out.println(two);
System.out.println(deque);

//  Stack mode
deque.offerLast(4);
deque.offerLast(5);

int five = deque.pollLast();
int four = deque.pollLast();
System.out.println(five);
System.out.println(four);
System.out.println(deque);

결과

1
2
[3]
5
4
[3]

---

References

• 남궁성, 『자바의 정석』, 도우출판(2016)