자료구조 - (2) 스택과 큐

스택 (Stack)

LIFO (Last In First Out) 구조 : 마지막(최근)에 넣은 것을 먼저 뺀다.
순차적으로 데이터 추가, 삭제하기 때문에 ArrayList와 같은 배열 구조가 적합

• 스택의 구현

Stack stack = new Stack();

사용되는 주요 메서드

메서드	설명
boolean empty()	스택이 비었는지 T/F
Object peek()	스택의 맨 위에 저장된 객체 반환 pop과는 달리 객체를 꺼내지는 않음(비었다면 예외 발생)
Object pop()	스택의 맨 위에 저장된 객체 꺼냄 (비었다면 예외 발생)
Object push(object item)	스택에 객체 저장
int search(Object o)	스택에서 객체 o의 위치 반환 (없으면 -1, 위치는 1부터 시작)

스택의 활용

• 수식계산, 수식 괄호 검사
• 실행 취소, 되돌리기 (undo, redo)
• 역순 문자열 만들기 (가장 나중에 입력된 문자부터 출력)
• 후위 표기법 계산 수식의 괄호 검사(연산자 우선순위 표현을 위한 괄호 검사)
• 웹 브라우저 방문 기록 (가장 나중에 열린 페이지부터 보여줌)

---

큐 (Queue)

FIFO (First In First Out) 구조 : 먼저 넣은 것(오래된 것)을 먼저 뺀다.
데이터의 추가, 삭제가 쉬운 LinkedList로 구현하는 것이 적합

• 큐의 구현

Queue queue = new LinkedList<>();

사용되는 주요 메서드

메서드	설명
boolean add(Object o)	객체를 큐에 추가 (저장공간 부족시 예외 발생)
Object remove()	큐에서 객체 꺼내 반환 (비어있으면 예외 발생)
Object element()	삭제 없이 요소 읽어온다 (peek과 달리 큐가 비었으면 예외 발생)
Object peek()	삭제 없이 요소를 읽어온다 (비어있으면 null)
boolean offer(Object o)	큐에 객체 저장 (저장공간 부족시 false)
Object poll()	큐에서 객체 꺼내 반환 + 삭제됨 (비어있으면 null)

큐의 활용

• 최근 사용 문서
• 버퍼
• 우선순위가 같은 작업 예약
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• BFS ( 너비 우선 탐색) 구현
• 캐시 구현
  
  

---

우선순위 큐

큐의 구현체 중 하나, 저장 순서에 관계없이 우선순위(priority)가 높은 것부터 꺼낸다.

• null 저장 X → NullPointerException 발생
• 숫자가 작은 것이 우선순위 가짐
• 저장공간 - 배열 사용
• 각 요소를 힙(heap)이라는 자료구조 형태로 저장

→ 가장 큰 값, 가장 작은 값을 빠르게 찾을 수 있음

우선순위 큐의 구현

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

System.out.println(pq);  // pq의 내부 배열을 출력
// 출력 : [1, 2, 3]

Object obj = null;

// 큐에 저장 요소 하나씩 꺼내기 
while((obj = pq.poll()) != null){
	System.out.print(obj + " ");
}
// 출력 : 1 2 3 

• 내부 배열 순서 - 입력 순서와 다름

우선순위 큐의 동작과정

1. pq에 값을 offer했을 때의 배열 형태

2. 마지막에 입력받은 2와 2의 부모인 3과 크기를 비교해 자식이 부모보다 작을 경우 서로 자리를 바꾼다.

3. 나머지 자식인 1이 부모인 2보다 값이 작으므로 서로 자리를 바꾼다.

4. 더 이상 부모보다 작은 자식이 없기 때문에 교환 종료, 배열은 [1, 2, 3]의 값을 갖게 된다.

---

Deque (Double-Ended Queue)

Deque는 양쪽 끝에 추가, 삭제가 가능하다. ( 스택 + 큐의 형태 )
ArrayDeque, LinkedList등으로 구현

• Deque의 구현

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

Deque 메서드에 대응하는 큐, 스택의 메서드

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

주요 메서드

• 값 삽입

메서드	설명
add(), addLast()	마지막에 원소 삽입 용량 초과 시 예외 발생
addFirst()	맨 앞에 원소 삽입 용량 초과 시 예외 발생
offer(), offerLast()	마지막에 원소 삽입 삽입 성공 시 true, 용량 제한에 걸리는 경우 false 반환
offerFirst()	맨 앞에 원소 삽입 삽입 성공 시 true, 용량 제한에 걸리는 경우 false 반환

• 값 삭제

메서드	설명
remove(), removeFirst()	맨 앞의 원소 제거 후 해당 원소를 리턴 덱이 비어있는 경우 예외 발생
removeLast()	마지막 원소 제거 후 해당 원소를 리턴 덱이 비어있는 경우 예외 발생
poll(), pollFirst()	맨 앞의 원소 제거 후 해당 원소를 리턴 덱이 비어있는 경우 null 리턴
pollLast()	마지막 원소 제거 후 해당 원소를 리턴 덱이 비어있는 경우 null 리턴

• 원소 확인

메서드	설명
getFirst()	맨 앞의 원소를 리턴 덱이 비어있는 경우 예외 발생
getLast()	마지막 원소를 리턴 덱이 비어있는 경우 예외 발생
peek(), peekFirst()	맨 앞의 원소를 리턴 덱이 비어있는 경우 null 리턴
peekLast()	마지막 원소를 리턴 덱이 비어있는 경우 null 리턴