[자바의 정석 기초편 chapter 11] 스택과 큐/ Stack 과 Queue

개념부터 잡자

 

🟥 스택(Stack)이란?

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

스택의 저장은 푸시(phsh) 추출은 팝!(pop)

저장은 0 → 1 → 2 순서로 넣었고, 추출할 때는 마지막부터 한다. 2 → 1 → 0

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

 

🟥  큐(Queue)란?

처음에 저장한 데이터를 가장 먼저 꺼내게 되는 피포구조(FIFO: First in First Out)

큐의 저장은 오퍼(offer) 추출은 폴(poll)

 

저장은 0 → 1 → 2 순서로 넣었고, 추출할 때도 저장순으로 한다. 0 → 1 → 2 

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

 

 

 

 

 

그렇다면 스택과 큐 구현은 어떤 컬렉션 클래스를 사용하는 게 좋을 까❓ ❓

순차적으로 데이터를 추가/삭제하는 스택은 ArrayList

데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하는 큐는 LinkedList가 적합하다.

 

큐는 데이터를 꺼낼 때마다 빈 공간을 채우기 위한 복사가 발생하므로 ArrayList는 비효율적임!

 

🟦 Stack의 메서드

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

 

🟪Queue의 메서드

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

 

 

🎈 자바의 정석 예제 11-2

import java.util.*;

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 =");
		while(!st.empty()) {
			System.out.println(st.pop()); // 스택에서 요소 하나를 꺼내서 출력
		}

		System.out.println("= Queue =");
		while(!q.isEmpty()) {
			System.out.println(q.poll()); // 큐에서 요소 하나를 꺼내서 출력
		}
	}
}​

 

 

🎈 자바의정석 예제 11-2 실행결과