[Java-11] 컬렉션 프레임웍 - Stack, Queue, Iterator, ListIterator, Enumeration

1. 스택(Stack), 큐(Queue)

1) 스택과 큐의 차이

- 스택은 'LIFO', 큐는 'FIFO'임

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

- FIFO(First In First Out) : 처음에 저장한 데이터를 가장 먼저 꺼내는 구조

 

 

 

- 스택(LIFO)는 0, 1, 2 순으로 저장(push)한 뒤, 2, 1, 0 순으로 추출(pop)

- 큐(FIFO)는 0, 1, 2 순으로 저장(push)한 뒤, 0, 1, 2 순으로 추출(pop)

 

Q. 스택과 큐를 구현하기 위해서는 어떤 컬렉션 클래스를 사용하는 것이 좋을까?

A1. 스택은 순차적으로 데이터를 추가 및 삭제하므로 ArrayList와 같은 배열기반의 컬렉션 클래스가 적합함

A2. 큐는 데이터를 꺼낼 때 항상 첫 번째로 저장된 데이터를 삭제하므로 배열기반의 컬렉션 클래스는 비효율적임. ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 적합함

 

2) Stack의 메서드

 

boolean empty()	Stack이 비어있는지 알려줌
Object peek()	Stack의 맨 위에 저장된 객체 반환 pop()과 달리 Stack에서 객체를 꺼내지는 않음 (비었을 때는 EmptyStackException 발생)
Object pop()	Stack의 맨 위에 저장된 객체를 꺼내서 반환 (비었을 때는 EmptyStackException 발생)
Object push(Object item)	Stack에 객체(item) 저장
int search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환 못 찾으면 -1을 반환 배열과 다르게 위치는 0이 아닌 1부터 시작함

 

3) Queue의 메서드

 

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

 

 

4) 스택과 큐의 활용

 

스택의 활용 - 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로

큐의 활용 - 최근사용문서, 인쇄작업 대기목록, 버퍼(buffer)

 

 

5) PriorityQueue

- Queue인터페이스의 구현체 중 하나

- 저장된 순서에 관계없이 우선순위(priority)가 높은 것부터 꺼냄

- null은 저장할 수 없음 (NullPointerException 발생)

- 저장공간을 배열로 사용하며, 각 요소를 '힙(heap)'이라는 자료구조의 형태로 저장

 

Queue pq = new PriorityQueue();
pq.offer(3);		// pq.offer(new Integer(3)); 오토박싱
pq.offer(1);
pq.offer(5);
pq.offer(2);
pq.offer(4);

Object obj = null;
while((obj = pq.poll())!=null)
	System.out.println(obj);
    

-> 결과는

1

2

3

4

5

의 형태로 나옴 (우선순위는 숫자가 작을수록 높아서)

 

6) Deque(Double-Ended Queue)

- Deque(덱,또는 디큐라고 읽음)은 양쪽 끝에 추가/삭제가 가능

- Deque의 조상은 Queue이며, 구현체로는 ArrayDeque과 LinkedList 등이 있음

- 스택과 큐를 합쳐놓은 것으로, 스택으로 사용할 수도 있고 큐로 사용할 수도 있음

 

 

 

2. Iterator, ListIterator, Enumeration

- 컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스

- Enumeration은 Iterator의 구버전

- ListIterator는 Iterator의 향상된 버전

 

1) Iterator

- 컬렉션에 저장된 각 요소에 접근하는 기능을 가짐

- Collection인터페이스에는 'Iterator(Iterator를 구현한 클래스의 인스턴스)'를 반환하는 iterator()를 정의함

- Collection인터페이스에 정의되어있으므로 List와 Set에도 포함되어 있음.

- 단, 각 컬렉션의 특징에 알맞게 작성되어 있음

 

- Iterator인터페이스의 메서드

 

boolean hasNext()	읽어 올 요소가 남아있는지 확인 있으면 true, 없으면 false 반환
Object next()	다음 요소를 읽어옴 next()를 호출하기 전에 hasNext()를 호출해서 읽어올 요소가 있는지 확인하는 것이 안전함
void remove()	next()로 읽어 온 요소를 삭제

 

Collection c = new ArrayList();
Iterator it = c.iterator();

while(it.hasNext())
	System.out.println(it.next());

 

- 단, Map인터페이스를 구현한 경우에는 iterator()를 직접 호출할 수 없음

- 대신 keySet()이나 entrySet() 같은 메서드를 통해 키와 값을 각각 따로 Set의 형태로 얻어온 후에 다시 iterator()를 호출하여 사용할 수 있음

 

2) ListIterator

- Iterator에 양방향 조회기능을 추가

- List를 구현한 경우만 사용가능함

 

- ListIterator인터페이스의 메서드

 

void add(Object o)	컬렉션에 새로운 객체(o)를 추가
boolean hasNext()	읽어 올 다음 요소가 남아있는지 확인 있으면 true, 없으면 false 반환
boolean hasPrevious()	읽어 올 이전 요소가 남아있는지 확인 있으면 true, 없으면 false 반환
Object next()	다음 요소를 읽어 옴
Object previous()	이전 요소를 읽어 옴
int nextIndex()	다음 요소의 index 반환
int previousIndex()	이전 요소의 index 반환
void remove()	next() 또는 previous()로 읽어 온 요소를 삭제
void set(Object o)	next() 또는 previous()로 읽어 온 요소를 지정된 객체(o)로 변경

 

 

 

3) Enumeration

- Iterator의 구버전

- 가능하면 Enumeration 대신 Iterator를 사용하는 것을 권장

 

- Enumeration 인터페이스의 메서드

 

boolean hasMoreElements()	읽어 올 요소가 남아있는지 확인 있으면 true, 없으면 false 반환
Object nextElement()	다음 요소를 읽어 옴

 

 

 

 

 

 

참고 - Java의 정석 3rd Edition (저자 : 남궁성, 출판 : 도우출판)