스택과 큐

스택 (Stack)

정의

데이터를 일시적으로 저장하기 위해 사용하는 자료구조로 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)구조 입니다.

 

스택에 데이터를 넣는 작업을 푸시(push), 데이터를 꺼내는 작업을 팝(pop)이라고 합니다.

 

스택 구조

 

스택에는 ArrayList와 같은 배열기반의 컬렉션 클래스가 적합

 

사용되는 메서드

boolean empty()	Stack이 비어있는지 알려준다.
Object peek()	Stack의 맨 위에 저장된 객체를 반환. pop()과 달리 Stack에서 객체를 꺼내지 않음. (비었을 때는 EmptyStackException 발생)
Object pop()	Stack의 맨 위에 저장된 객체를 꺼낸다. (비었을 때는 EmptyStackException 발생)
Object push(Object item)	Stack에 객체(item)를 저장한다.

 

 

 

큐 (Queue)

정의

스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조로 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)구조로 되어 있다.

 

큐 구조

 

데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로, ArrayList와 같은 배열기반의 컬렉션 클래스를 사용한다면 데이터를 꺼낼 때마다 빈공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적이다.

 

큐는 ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 적합하다.

 

사용되는 메서드

boolean offer(Object o)	Queue에 객체를 저장. 성공하면 true, 실패하면 false를 반환
Object poll()	Queue에 객체를 꺼내서 반환, 비어있으면 null을 반환
Object peek()	삭제없이 요소를 읽어 온다. 비어있으면 null을 반환

 

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

 

※ 추가

우선순위 큐 (Priority Queue)

Queue 인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위(priority)가 높은 것부터 꺼내게 된다.

null은 저장할 수 없으며, null을 저장시 NullPointerException이 발생한다.