Stack과 Queue

Stack

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

Stack은 순차적으로 데이터를 추가하고 삭제하기 때문에 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합하다.

 

메서드

boolean empty() : Stack이 비어있는지 알려ㅜㄴ다.

Object peek() : Stack의 맨위에 저장된 객체를 반환. pop()과 달리 데이터를 객체에서 꺼내지는 않는다.

Object pop() : Stack의 맨위에 저장된 개개체를 꺼낸다.

Object push(Object o) : Stack에 객체 o를 저장한다.

int search(Object o) : Stack에서 객체 o의 위치를 반환한다. Stack에 존재하지 않으면 -1반환

 

스택은 수식괄호검사, 웹브라우저의 뒤로/앞으로 등에 사용된다.

 

Queue

 큐 : 처음에 저장한 데이터를 가장먼저 꺼내어 삭제하게되는 FIFO(First In First Out)구조로 되어있다. 큐는 한방향으로 넣고 한방향으로 빼는 파이프와 같은 구조로 되어있다.

Queue는 꺼낼때 항상 첫번째 저장된 데이터를 삭제한다.

배열기반 컬렉션 클래스에서는 데이터를 꺼낼때마다 빈공간을 채우기위해 데이터 복사가 발생하므로 비효율적이다. 

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

 

메서드

boolean add(Object o) : Queue에 객체 o를 추가한다.

Object remove() : Queue에서 객체를 삭제 반환한다.

Object element() : 삭제없이 요소를 읽어온다.

boolean offer(Object o) : Queue에 객체 o를 저장한다.

Object poll() : Queue에서 객체를 꺼내서 반환한다.

Object peek() : 삭제없이 요소를 읽어온다.

 

Queue는 인터페이스이다. 그러므로 사용하기 위해서는 Queue인터페이스를 상속받아 구현되어있는 LinkedList클래스를 사용한다.

 

Queue는 최근사용문서, 버퍼 등에 사용된다.

 

Priority Queue

Queue인터페이스의 구현체중 하나로, 저장한 순서에 상관없이 우선순위(priority)가 높은 순서대로 꺼내는 특징있다.

PriorityQueue는 저장공간으로 배열을 사용하며 heap 자료구조의 형태를 가진다.

 

poll을 통해 Priority Queue에 저장된 객체들을 꺼낼경우 우선순위 순서대로 꺼내진다.