자바의 정석8-3 스택과 큐/Iterator, ListIterator, Enumeration

스택과 큐(Stack & Queue)

스택(Stack): 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO 구조

 

 

 

큐(Queue): 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO 구조

 

 

-> 순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList와 같은 배열기반의 컬렉션 클래스 적합, 큐에는 데이터의 추가와 삭제가 쉬운 LinkedList로 구현하는 것이 적합(큐는 항상 첫 번째 저장된 데이터를 삭제하므로, 배열은 첫 번째 데이터 삭제 어려움)

---

Stack & Queue의 메서드

- Stack은 클래스가 있어서 객체 생성 가능 Stack st = new Stack( );

- Queue는 인터페이스로 정의되어 있어서 객체 생성 불가능 Queue q = new Queue( ); xx

---

Stack 메서드

 

메서드	실행
Boolean empty( )	Stack이 비어 있는 지 알려준다.
Object peek( ) (위에 뭐가 있는지 보고, 꺼내지 않음)	Stack의 맨 위에 저장된 객체를 반환. pop( )과 달리 Stack에서 객체를 꺼내지 않음.(비었을 때는 EmptyStackException발생)
Obejct pop( )	Stack의 맨 위에 저장된 객체를 꺼낸다.(비었을 때는 EmptyStackException발생)
Object push(Obejct item)	Stack에 객체(item)을 저장한다.
int search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환, 못찾으면 -1을 반환.(배열과 달리 위치는 0이 아닌 1부터 시작)

 

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( ) 읽기	삭제 없이 요소를 읽어온다. Queue가 비어었으면, null을 반환

 

-> 위에 세개는 예외발생, 보통은 offer와 poll 사용

 

---

Queue 인터페이스를 구현한 클래스 찾기

1) Queue를 직접 구현

2) Queue를 구현한 클래스를 사용(JAVA API에서 Queue인터페이스 찾기)

-> All Known Implementing Classes(Queue를 구현한 클래스 목록)

ex)

LinkedList는 Queue를 구현한 클래스 -> LinkedList를 이용하여 객체생성가능!

Queue q = new LinkedList( ); 참조변수의 타입을 가능하면 조상타입으로 하는게 좋음

q.offer( );

---

예제1) 스택과 큐에 각각 "0", "1", "2"를 같은 순서로 넣고, 꺼내는 프로그램

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Ex11_2 {

	public static void main(String[] args) {
		Stack st = new Stack();
		Queue q = new LinkedList(); // Queue인터페이스의 구현체인 LinkedList를 사용해 객체 생성
		
		st.push("0");
		st.push("1");
		st.push("2");
		
		q.offer("0");
		q.offer("1");
		q.offer("2");
	
		System.out.println("= stack =");
		System.out.println("맨 위의 저장된 객체는? " + st.peek());
		while(!st.empty()) {
			System.out.print(st.pop()+"\n"); // 스택에서 요소 하나를 꺼내기
		}
		
		System.out.println("= queue =");
		while(!q.isEmpty()) {
			System.out.print(q.poll()+"\n"); // 큐에서 요소 하나를 꺼내기
		}
	}
}

<출력값>

= stack =
맨 위의 저장된 객체는? 2
2
1
0
= queue =
0
1
2

---

스택과 큐(Stack & Queue)의 활용

 

 

예제1) 웹브라우저의 ‘뒤로’, ‘앞으로’ 버튼의 기능을 구현한 것. 이 기능을 구현하기 위해서 2개의 스택을 사용

 

import java.util.Stack;
public class StackEx1 {
	
	public static Stack back = new Stack();
	public static Stack forward = new Stack();

	public static void main(String[] args) {
		goURL("1.구글");     // back 스택에 사이트 추가
	    goURL("2.네이버");
	    goURL("3.다음");
	    goURL("4.네이트");
	    
	    printStatus();
	    
	    goBack();
	    System.out.println("= '뒤로' 버튼을 누른 후 =");
	    printStatus();
	    
	    goBack();
	    System.out.println("= '뒤로' 버튼을 누른 후 =");
	    printStatus();
	    
	    goForward();
	    System.out.println("= '앞으로' 버튼을 누른 후 =");
	    printStatus();
	    
	    goURL("codechobo.com");
	    System.out.println("= 새로운 주소로 이동 후 =");
	    printStatus();
	    
	}
	public static void goURL(String url) {
		back.push(url);  // 스택에 url 순서대로 추가
		if(!forward.empty())  // forward 스택이 비어 있지 않으면, forward 스택을 비우기
			forward.clear();   
	}
	public static void printStatus() {
		System.out.println("현재 화면은 '" + back.peek() + "' 입니다.");
		System.out.println();
	}
	public static void goBack() {
		if(!back.empty())               // back 스택이 비어있지 않으면, 
			forward.push(back.pop());	// back 스택에서 삭제한 것을 forward 스택에 추가
	}
	public static void goForward() {
		if(!forward.empty())            // forward 스택이 비어있지 않으면,
			back.push(forward.pop());   // forward 스택에서 삭제한 것을 back 스택에 추가
	}
}

---

예제2) 입력한 수식의 괄호가 올바른지 체크하는 예제 ‘(‘를 만나면 스택에 넣고 ‘)’을 만나면 스택에서 ‘(‘를 꺼낸다.

ex) ((2+3)*1) => 일치  / (2+3)*1) => 불일치(괄호가 남아있음) / (2+3)*1) => 불일치(예외발생, 남아있는 괄호가 없는데 pop을 해서)

괄호가 남아있지 않다면 수식이 일치하고 괄호가 남아 있다면 수식이 일치하지 않다.

import java.util.EmptyStackException;
import java.util.Stack;

public class Ex11_3 {

	public static void main(String[] args) {

		Stack st = new Stack();
		String expression = "((2+3)*1+3)";
		
		System.out.println("Expression:" + expression);
		
		try { 
			for(int i = 0; i < expression.length(); i++) {
				char ch = expression.charAt(i); // 여기서 괄호 말고 숫자나 부호는 스택과 상관 없음
				if (ch=='(') {        // 여는 괄호이면 스택에 집어넣고
					st.push(ch+"");
				} else if (ch==')') { // 닫는 괄호이면 스택에서 빼기
					st.pop();
				}                     // 괄호의 갯수가 대칭이면 스택은 비어있어야 함
			}
			if(st.isEmpty()) { // 스택이 비어있으면, st.empty()가능
				System.out.println("괄호가 일치합니다.");
			}else {
				System.out.println("괄호가 일치하지 않고, 괄호가 남아있어요");
			}
		} catch (EmptyStackException e) {  // 스택에서 pop을 다 해서 데이터가 없는데 또 pop을 하면 예외발생 
			System.out.println("괄호가 일치하지 않고, 스택에는 값이 없어요 빼라고 하지 마세요!"); // 에) 여는 괄호보다 닫는 괄호가 더 많을 때
		}//try
	}
}

---

Iterator, ListIterator, Enumeration

- 컬렉션에 저장된 데이터를 접근하는데(읽어오는데) 사용되는 인터페이스

- Enumeration은 Iterator의 구버전

- ListIterator는 Iterator의 접근성을 향상시킨 것(단방향 -> 양방향, next 말고도 previous도 있음) -> ListIterator는 잘 사용하지 않음.

-> Iterator주로사용!

 

Iterator 인터페이스의 메서드

 

메서드	설명
Boolean hasNext( )	읽어 올 요소가 남아있는지 확인한다. 있으면 true, 없으면 false를 반환한다.
Object next( )	다음 요소를 읽어 온다. next( )를 호출하기 전에 hasNext( )를 호출해서 읽어올 요소가 있는지 확인하는 것이 안전하다.
void remove( )	next( )로 읽어온 요소를 삭제한다. next( )를 호출한 다음에 remove( )를 호출해야 한다.(선택적 기능)

-> hasNext( )로 읽어올 요소가 남아있는지 확인하고 있으면 next( )로 다음 요소를 읽기

 

Enumeration 인터페이스의 메서드

 

메서드	설명
Boolean hasMoreElements( )	읽어 올 요소가 남아있는지 확인한다. 있으면 true, 없으면 false를 반환한다.
Object nextElement( )	다음 요소를 읽어 온다. nextElement( )를 호출하기 전에 hasMoreElements( )를 호출해서 읽어올 요소가 남아있는지 확인하는 것이 안전하다. Iterator의 next( )와 같다.

 

Iterator

- 컬렉션 인터페이스에 저장된 요소(List, Set, Map)들을 읽어오는 방법을 표준화한 것

 

 

- hasNext( )로 확인하고 next( )읽어 오기가 중요!

- 컬렉션 클래스에 대해 iterator( )를 호출해서 Iterator 객체를 얻은 다음, 반복문, 주로 while문을 사용해서 컬렉션 클래스의 요소들을 읽어올 수 있음

 

 

- Iterator it = list.iterator( ); -> Iterator 객체를 반환!

- ArrayList대신 Collection인터페이스를 구현한 다른 컬렉션 클래스에 대해서도 이와 동일한 코드를 사용할 수 있다.

- 이렇게 Iterator같이 공통 인터페이스를 정의해서 표준을 정의하고 구현하게 해서 코드의 일관성을 유지하고 재사용성을 극대화함 -> 객체지향 프로그래밍의 중요한 목적 중 하나

 

---

예제1)

 

import java.util.*;

public class Ex11_5 {

	public static void main(String[] args) {
		Collection c = new ArrayList(); // ArrayList는 Collection의 자손
		c.add("1");
		c.add("2");
		c.add("3");
		c.add("4");
		c.add("5");
		
		Iterator it = c.iterator(); // list에서 iterator 호출해서 iterator 객체 반환
		
		while(it.hasNext()) {
			Object obj = it.next();
			System.out.print(obj);
		}	
		
		// iterator는 일회용이라 다쓰고나면 다시 얻어와야 한다. 
		it = c.iterator();  // 새로운 iterator객체를 얻는다.
		while(it.hasNext()) {
			Object obj = it.next();
			System.out.print(obj);
		}
	} // main
}

 

<출력 값>

1234512345

 

참조변수의 타입을 ArrayList가 아닌 Collection타입으로 하는 이유

- Collection에 없고 ArrayList에만 있는 메서드를 사용하는 게 아니라면, Collection타입의 참조변수로 선언하는 것이 좋다.

- 만약 Collection인터페이스를 구현한 다른 클래스, LinkedList로 바꿔야 한다면 선언문 하나만 변경하면 나머지 코드는 검토하지 않아도 되기 때문(참조변수 타입이 Collection이기 때문에 Collection에 정의되지 않은 메서드는 사용되지 않았을 것)

---

MAP과 Iterator

- Map에는 iterator()가 없고 Collection(List, Set)에만 있다.

- Map은 키와 값을 쌍으로 저장하기 때문

 

-> keySet( ), entrySet( ), values( )를 호출해서 거기에서 Iterator( )를 호출 해야 함 (keySet과 entrySet은 반환타입 set, vaules는 collection)

-> key와 value => entry

 

Map map = new HashMap( ); … Iterator it = map.entrySet( ).iterator( )	Set eSet = map.entrySet( ); Iterator it = eSet.iterator( );
두 코드는 동일함

 

 

(1) map.entrySet( )의 실행결과는 Set이므로

(2) map.entrySet( )를 통해 얻은 Set인스턴스의 iterator( )를 호출해서 Iterator인스턴스를 얻는다.

(3) 마지막으로 Iterator인스턴스의 참조가 it 참조변수에 저장된다.