Java :: Collection :: 1.4 Stack & Queue

Java의 정석 3판을 보며 공부한 내용을 정리하였습니다.
남궁성님께 많이 배우고 있습니다.

1.4 Stack 과 Queue

Stack, Queue

# Stack ?

그림 1. 스택

마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)구조

예 )
IN : 3 -> 2 -> 1
OUT : 1 -> 2 -> 3

# Queue란?

그림 2. 큐

처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)구조

예 )
IN : 3 -> 2 -> 1
OUT : 3 -> 2 -> 1

---

# 스택과 큐에 알맞는 컬렉션 클래스

그렇다면 스택과 큐는 어떤 컬렉션 클래스를 사용하여 구현하는 것이 좋을까??

순차적으로 데이터를 추가/삭제하는 스택은 ArrayList가 좋을 것 같다.

추가할 때는 앞에서부터 순차적으로 입력되고, 꺼낼 때는 뒤에서부터 꺼내니 아주 적합하다.

그렇다면 큐는 어떨까?
추가할 때는 앞에서부터 순차적으로 입력되지만, 꺼낼 때도 앞에서 꺼내야 한다.
만약 ArrayList를 쓴다면 앞에서 꺼낼 때마다 빈 공간을 채우기 위해 ArrayList의 데이터들의 복사가 발생하므로 비효율적이다.

-> 큐는 삭제시에도 작업이 단순한 LinkedList가 적합하다.

---

# Stack의 메서드

• boolean empty()
  -> Stack이 비어있는지 알려줌
• Object peek()
  -> Stack의 맨 위에 저장된 객체를 반환. pop()과 달리 Stack에서 객체를 꺼내지는 않음(비었을 경우 EmptyStackException발생)
• Object pop()
  -> Stack의 맨 위에 저장된 객체를 꺼낸다.(비었을 때는 EmptyStackException발생)
• Object push(Object item)
  -> Stack에 객체(item)를 저장한다
• int search(Object o)
  -> Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환, 못찾으면 -1을 반환.(배열과 달리 위치는 0이 아닌 1부터 시작)

---

# Queue의 메서드

• boolean add(Object o)
  -> 지정된 객체를 Queue에 추가한다. 성공하면 True를 반환. 저장공간이 부족하면 IllegalStateException 발생
• Object remove()
  -> Queue에서 객체를 꺼내 반환. 비어있으면 NoSuchElementException 발생
• Object element()
  -> 삭제없이 요소를 읽어옴. peek와 달리 Queue가 비었을 때 NoSuchElementException 발생
• boolean offer(Object o)
  -> Queue에서 객체를 꺼내서 반환. 비어있으면 null 반환
• Object poll()
  -> Queue에서 객체를 꺼내서 반환. 비어있으면 null 반환
• Object peek()
  -> 삭제없이 요소를 읽어옴. Queue가 비어있으면 null 반환

---

static public void main(String[] args) {
	Stack st = new Stack();
	Queue q = new 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

Stack은 LIFO
Stack IN : 1 -> 2 -> 3
Stack OUT : 3 -> 2 -> 1

Queue는 FIFO
Queue IN : 1 -> 2 -> 3
Queue OUT : 1 -> 2 -> 3

---

# PriorityQueue

PriorityQueue는 Queue 인터페이스의 구현체 중 하나로,

저장한 순서에 관계없이 우선순위(priority)가 높은 것부터 꺼낸다.

• 저장공간으로 배열을 사용
• 각 요소를 힙(heap)이라는 자료구조의 형태로 저장(힙은 이진 트리의 한 종류로 가장 큰, 작은 값을 빠르게 찾을 수 있다.)
• null은 저장할 수 없다. -> null저장시 NullPointerException 발생
• 숫자가 아닌 객체를 저장할 경우엔 우선순위 비교하는 방법을 제공해야 함

---

# Deque(Double-Ended Queue)

큐의 변형으로 한 쪽으로만 추가/삭제할 수 있는 큐와 달리!
덱은 양쪽 끝에 추가/삭제가 가능하다

_그림 3. 덱(deque)

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

표 1. 덱(Deque)의 메서드에 대응하는 큐와 스택의 메서드