[Java] 스택 / 큐 / 덱

스택 (Stack)

LIFO(last in, firstout)

리스트의 한쪽 끝에서 수행 되는 선형 리스트 한가지 형태( 삽입(push), 삭제(pop) )

예시	설명
함수 호출	함수 내부에서 사용되는 변수를 스택에 저장. 호출이 끝나면 스택에서 제거
수식 계산	수식에서 괄호를 계산할때 스택 이용
웹 브라우저 방문 기록	방문한 웹 페이지를 스택에 저장. 이전 페이지로 돌아갈때 이용.

 

메서드	설명
push()	스택에 추가, 반환
peek()	마지막 요소 반환
pop()	마지막 요소 제거, 반환
isEmpty()	비어있는지 확인, 비어있으면 true , 아닐경우 false
search()	해당위치 반환, 없으면 -1 반환

---

큐 (Queue)

FIFO(first in , first out)

여러개의 데이터 항목을 일정한 순서대로 나열 하는 형태( push(입력), pop(삭제) )

 

Java에서 큐는 인터페이스의 역할을 수행하며 ArrayDeque, LinkedList, PriorityQueue 등을 통해서 구현체를 구현

예시	설명
프로세스 관리 / 대기열	대기열에 줄을 서서 업무를 처리 하는것이 큐의 예시. 먼저 온 순서대로 업무를 처리
프로세스 관리	프로세스가 CPU를 할당받기 위해 대기하는 큐를 사용
너비 우선 탐색(BFS, Breadth-First Search)	크래프 탐색 알고리즘에서 인접한 노드를 우선으로 방문해야 하는 경우 큐를 사용
캐시(Cache)	캐시 메모리에서 데이터를 저장하고 꺼낼 때 , 가장 오래된 데이터를 먼저 삭제하는 정책을 구현할때 큐를 사용

 

메서드	설명
offer( )	맨 뒤에 요소 추가. 가득 차서 추가할 수 없는 경우 false 반환
add()	맨 뒤에 요소 추가. 추가할 수 없는 경우 illegalStateException 발생
poll()	맨 앞에서 요소 제거 및 반환 . 비어있으면 null 반환
peek()	맨 앞에서 요소 반환 . 비어 있으면 null 반환
clear()	모든 요소 제거

 

---

덱 (Deque)

양 쪽에서 삽입과 삭제가 가능한 자료구조.

스택과 큐의 기능을 모두 가지고 있는 자료구조로 FIFO오 LIFO 개념이 모두 적용 될 수 있음.

예시	설명
양방향 큐(Double-Ended Queue)	앞과 뒤에서 삽입과 삭제가 가능한 덱은 양방향 큐라고 불림
회문(Palindrome) 판별	앞이나 뒤에서 읽을때 동일한 문자열을 검사할때 사용
최대, 최솟값 검색	슬라이딩 윈도우(Sliding Window) 알고리즘을 이용해 최대/최솟값을 검색할 때 사용

 

메서드	설명
addFirst()	맨 앞에 요소 추가
addLast()	맨 뒤에 요소 추가
removeFirst()	맨 앞에서 요소 제거, 반환. 비어있으면 예외발생
removeLast()	맨 뒤에서 요소 제거, 반환. 비어있으면 예외발생
getFirst()	맨 앞에서 요소 반환. 비어있으면 예외발생
getLast()	맨 뒤에서 요소 반환. 비어있으면 예외발생