1103 | 자바의 정석 기초편 :: ch11-15~11-21

스택과 큐 (Stack & Queue)

 

✔ 스택 (Stack)

: 밑이 막힌 상자

: LIFO구조. Last in First Out. 마지막에 저장된 것을 제일 먼저 꺼내게 된다.

: 넣는걸 push, 꺼내는걸 pop

: 배열이 유리

 

✔ 큐(Queue)

: 줄서기

: FIFO구조. First in FIrst out. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다.

: 넣는걸 offer, 꺼내는걸 poll

: LinkedList가 유리

 

 

---

스택과 큐의 메서드

 

✔ Stack의 메서드

: 스택은 클래스이므로 Stack st = new Stack(); 객체생성 가능.

메서드	설명
boolean empty()	stack이 비어있는지 알려준다
Object peek() // 맨위 객체를 보기만 함	Stack의 맨 위에 저장된 객체를 반환. pop()과 달리 Stack에서 객체를 꺼내지 않음. (비었을때는 EmptyStackException 발생)
Object pop() // 삭제	Stack 의 맨 위에 저장된 객체를 꺼낸다.  비었을때는 EmptyStackException발생
Object push(Object item) // 추가	Stack에 item 객체 저장
int search(Obejct o) // Arrays.indexOf()와 비슷	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환 못찾으면 -1 반환 배열과 달리 위치는 0이 아닌 1부터 시작

 

 

✔ Queue의 메서드

: Queue는 인터페이스이므로 Queue q = new Queue(); 불가. 객체생성 불가.

: Queue를 직접 구현하던가 Queue를 구현한 클래스를 사용. (클래스는 java api에서 Queue를 조회하면 Implementing classes가 있음)

: LinkedList가 대표적. Queue q = new LinkedList(); q.offer("0");

	메서드	설명
예외 발생	boolean add(Object o) // 추가 & 예외발생	지정된 객체를 Queue에 추가. 성공하면 true 저장공간 부족시 illegalStateException발생
	Object Remove() // 삭제 & 예외발생 (try-catch로처리)	Queue에서 객체를 꺼내 반환 비어있으면 noSuchElementException 발생
	Object element()	삭제 없이 요소를 읽어온다. peek과 달리 queue가 비었을때 NoSuchElementException발생
예외 없음 이 세개를 중점으로 보기	boolean offer (Object o) // 추가 & 예외없음	Queue에 객체를 저장. 성공하면 true, 실패하면 false 반환
	Object poll() // 삭제 & null만 반환하고 예외없음 if(obj==null) > 예외 처리	Queue에서 객체를 꺼내서 반환. 비어있으면 null 반환
	Object peek()	삭제 없이 요소를 읽어온다. Queue가 비어있으면 null 반환

 

✔스택의 활용 예

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

 

✔ 큐의 활용 예

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