스택(Stack), 큐(Queue)

출처 - Java의 정석 기초편 (남궁 성)

 

 

1. 개념

- 스택: 밑 막힌 상자, LIFO(Last In First Out), 저장(push)-추출(pop), 배열기반 컬렉션 클래스로 구현(ArrayList)

- 큐: 밑 뚫린 파이프, FIFO(First In First Out), 저장(offer)-추출(poll), 연결기반 컬렉션 클래스로 구현(LinkedList)

 

 

2. Stack

- 스택 사용하려면 클래스 사용

 

Stack st = new stack();
st.push("0");

// Stack 메서드
boolean empty()
Object peek() // 꺼내지 않고 맨 위 객체 반환(보기만 함)
Object pop() // 맨 위에 객체 삭제
Object push(Object item) // 객체 추가
int search(Object o) // 주어진 객체(o) 위치 반환(맨 위:1부터 시작, 못찾으면 -1)

 

 

3. Queue

- 큐는 인터페이스라 객체 생성 불가→큐를 직접 구현, 구현한 클래스 사용

- Java API의 All Known Implementing Classes: Queue인터페이스를 구현한 클래스들 사용

 

Queue q = new Queue(); // 불가!!
Queue q = new LinkedList(); // Queue 구현한 클래스 사용
q.offer("0");

// Queue 메서드
// 예외 발생
boolean add(Object o) // 객체 추가
Object remove() // 객체 삭제
Object element() // 삭제없이 요소 읽기

// 예외 발생 안함
boolean offer(Object o) // 객체 추가
Object poll() // 객체 삭제
Object peek() // 삭제 없이 맨 아래 저장된 객체 반환

 

 

4. 활용

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

- 큐: 최근사용문서, 인쇄작업 대기목록, 버퍼