스택(Stack)과 큐(Queue)

Stack(스택)

 

선형의 자료구조로서 후입선출(LIFO)의 특징을 가진다.

자료의 삽입: push / 자료의 삭제: pop / 가장 상단의 값: top / 가장 상단 값 반환: peek / 스택의 크기: size 

 

Stack<Integer> stk = new Stack<>(); 

라이브러리가 존재하여 다른 자료구조로 구현할 필요가 없음

 

Queue(큐)

 

선형의 자료구조로서 선입선출(FIFO)의 특징을 가진다. 중간에 원소삽입이 불가하며 뒤쪽으로 순서대로 자료를 삽입할 수 있다. LinkedList로 구현한다. 

자료의 삽입: offer / 자료의 삭제: poll / 제일 마지막 값 반환: peek / 스택의 크기: size 

 

** 큐의 매서드

add, remove, element는 예외를 발생시킴 offer, poll, peek은 값을 리턴

 

add : 새로운 원소 추가에 실패하면 IllegalStateException 발생

offer: 새로운 원소 추가 실패하면 -> false

 

remove: 큐에 원소가 없을 때 NoSuchElementException 예외 발생 -> 예외처리하고 싶을 때 사용

poll: 원소가 없으면 null 반환

 

element: 큐에 원소가 없을 때 NoSuchElementException 예외 발생 -> 예외처리하고 싶을 때 사용

peek: 원소가 없으면 null 반환

 

deque(데크/텍)

 

Double Ended Queue의 줄임말로 큐의 양쪽에서 삽입과 삭제를 수행할 수 있도록 한 자료구조

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

위와 같이 구현 가능하다.

 

데이터 삽입

add():

마지막에 원소 삽입 / 용량 초과 시 예외 발생

addFirst(): 

맨 앞에 원소 삽입 / 용량 초과 시 예외 발생

addLast(): 

마지막에 원소 삽입 / 용량 초과 시 예외 발생

offer(): 

마지막에 원소 삽입 / 삽입 성공 시 true, 용량 제한에 걸리는 경우 false 반환

offerFirst(): 

맨 앞에 원소 삽입 / 삽입 성공 시 true, 용량 제한에 걸리는 경우 false 반환

offerLast(): 

마지막에 원소 삽입 / 삽입 성공 시 true, 용량 제한에 걸리는 경우 false 반환

 

데이터 삭제

remove(): 맨 앞의 원소 제거 후 해당 원소를 리턴 / 덱이 비어있는 경우 예외 발생

removeFirst(): 
맨 앞의 원소 제거 후 해당 원소를 리턴 / 덱이 비어있는 경우 예외 발생

removeLast(): 
마지막 원소 제거 후 해당 원소를 리턴 / 덱이 비어있는 경우 예외 발생

poll(): 
맨 앞의 원소 제거 후 해당 원소를 리턴 / 덱이 비어있는 경우 null 리턴

pollFirst(): 
맨 앞의 원소 제거 후 해당 원소를 리턴 / 덱이 비어있는 경우 null 리턴

pollLast(): 
마지막 원소 제거 후 해당 원소를 리턴 / 덱이 비어있는 경우 null 리턴

 

데이터 확인

getFirst(): 
맨 앞의 원소를 리턴 / 덱이 비어있는 경우 예외 발생

getLast(): 
마지막 원소를 리턴 / 덱이 비어있는 경우 예외 발생

peek(): 
맨 앞의 원소를 리턴 / 덱이 비어있는 경우 null 리턴

peekFirst(): 
맨 앞의 원소를 리턴 / 덱이 비어있는 경우 null 리턴

peekLast(): 
마지막 원소를 리턴 / 덱이 비어있는 경우 null 리턴