[JAVA] Stack, Queue

1. Stack 과 Queue

 

Stack 은 LIFO (last in first out) 의 구조로 데이터를 저장하고 추출하는 자료구조이고, Queue 는 FIFO (first in first out) 의 구조로 데이터를 저장하고 추출하는 자료구조이다. 일반적으로 stack 은 데이터의 저장과 추출에 push 와 pop, queue 는 offer 와 poll 이라는 용어를 사용한다.

 

스택은 자료구조의 가장 마지막에서 순차적으로 데이터가 저장되거나 출력되기 때문에 ArrayList 와 같은 배열 기반의 컬렉션 클래스로 구현하면 적합하다. 하지만 큐의 경우 데이터의 제거가 가장 첫번째 데이터부터 수행되기 때문에 ArrayList 보다는 데이터의 추가, 삭제에 용이한 Linkedlist 로 구현하는 것이 더 적합하다.

 

자바에서는 스택을 Stack 이라는 자료구조로 따로 구현하여 제공한다. 반면에 큐의 경우 Queue 라는 인터페이스를 정의해놓았을 뿐 별도의 클래스는 제공하지 않는다. 대신 Linkedlist 나 PriorityQueue 와 같이 Queue 인터페이스를 구현해놓은 다양한 클래스들 중에서 알맞은 클래스를 선택하여 사용해야한다.

 

int[] datas = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

Stack<Integer> stack = new Stack<>();
Queue<Integer> queue = new Linkedlist<>();
for(int data : datas) {
    stack.push(data);
    queue.offer(data);
}

while(!stack.isEmpty()) System.out.print(stack.pop() + " ");
# 9 8 7 6 5 4 3 2 1 0

while(!queue.isEmpty()) System.out.println(queue.poll());
# 0 1 2 3 4 5 6 7 8 9

 

2. PriorityQueue

 

Queue 인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위 (priority) 가 높은 것부터 추출하도록 한다. heap 이라는 자료구조를 사용하여 구현되어 있으며 null 값은 저장할 수 없다.

 

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(2);
pq.offer(1);

// 3, 2, 1 순서대로 입력했지만 오름차순으로 정렬되어 1, 2, 3 순서로 출력된다.
while(!pq.isEmpty()) System.out.println(pq.poll());
/*
1
2
3
*/

 

3. Deque

 

Queue 의 변형으로 각각의 끝에서 입력과 출력이 각각 이루어지는 일반 Queue 와는 달리 양쪽 끝 모두가 입력과 출력을 수행할 수 있도록 구현되어있다. Deque 의 조상은 Queue 이며, 구현체로는 ArrayDeque 와 LinkedList 등이 있다.

 

Deque	Queue	Stack	설명
offerLast()	offer()	push()	자료구조의 가장 마지막 인덱스에 값을 저장한다.
pollLast()		pop()	자료구조의 가장 마지막 인덱스의 값을 추출한다.
pollFirst()	poll()		자료구조의 가장 첫번째 인덱스의 값을 추출한다.
peekFirst()	peek()		자료구조의 가장 첫번째 인덱스의 값을 조회한다.
peekLast()		peek()	자료구조의 가장 마지막 인덱스의 값을 조회한다.