/ JAVAJUNGSUK

Ch11-15~18. Stack, Queue

자바의 정석 기초편

0. 목차


Chapter11. 컬렉션 프레임웍

Ch11 - 15. Stack과 Queue

Ch11 - 16. Stack과 Queue 메서드

Ch11 - 17. Stack과 Queue 예제

Ch11 - 18. 인터페이스를 구현한 클래스 찾기



Ch11 - 15. Stack과 Queue

▶ Stack이란?

▷ 아래가 막힌 상자
▷ LIFO(Last In First Out) 구조 : 후입선출
▷ 마지막에 저장된 것을 제일 먼저 꺼냄


▶ Queue란?

▷ 양 끝이 뚫린 상자
▷ FIFO(First In First Out) 구조 : 선입선출
▷ 처음에 저장된 것을 제일 먼저 꺼냄


▶ Stack 구현은 배열이 유리

▷ Stack 저장(push) : 순차적
→
[0, 1, 2]
▷ Stack 추출(pop) : LIFO 후입선출
←
[0, 1, 2]
[0, 1]
[0]
[]


▶ Queue 구현은 LinkedList가 유리

▷ Queue 저장(offer) : 순차적
→
[0, 1, 2]
▷ Queue 추출(poll) : FIFO 선입선출
→
[0, 1, 2]
[copy 1, copy 2, null]
[1, 2]
[copy 2, null]
[2]
[]

LinkedList = NO copy
[0]→[1]→[2]
[1]→[2]
[2]
[]




Ch11 - 16. Stack과 Queue 메서드

▶ Stack(class)의 메서드

Stack st = new Stack();
▷ boolean empty()
  • Stack이 비어있는지 알려 줌
▷ Object peek()
  • peek : 꺼내지 않고 맨 위에 뭐가 있는지 보는 것
  • Stack의 맨 위에 저장 된 객체를 반환
  • pop()과 달리 Stack에서 객체를 꺼내지 않음
  • 비어있을 때, EmptyStackException 발생
▷ Object pop()
  • Stack의 맨 위에 저장 된 객체를 반환
  • 비어있을 때, EmptyStackException 발생
▷ Object push(Object item)
  • Stack의 객체(item)을 저장
▷ Object search(Object o)
  • ArrayList의 indexOf()와 비슷
  • Stack에서 주어진 객체(o)를 찾아 그 위치를 반환
  • 못 찾으면 -1 반환
  • 배열과 달리 위치는 0이 아닌 1부터 시작

▶ Queue(인터페이스)의 메서드

  • Queue qu = new Queue();
  • Queue 직접 구현
  • Queue 구현한 클래스를 찾아 사용
    Queue g = new LinkedList();
g.offer("0");
▷ boolean add(Object o)
  • 지정 된 객체를 Queue에 추가
  • 성공하면, true 반환
  • 저장 공간 부족 시, IllegalStateException 발생
▷ Object element()
  • 삭제없이 요소를 읽어 옴
  • peek과 달리 Queue가 비었을 때 NoSuchElementException 발생
▷ Object remove()
  • Queue에서 객체를 꺼내 반환
  • 비어있으면 NoSuchElementException 발생
  • try-catch로 예외처리
▷ Object poll()
  • Queue에서 객체를 꺼내 반환
  • 비어있으면 null 반환
  • if (obj == null) { 예외처리 }
▷ boolean offer(Object o)
  • Queue에 객체를 저장
  • 성공하면, true 반환
▷ Object peek()
  • 삭제없이 요소를 읽어 옴
  • Queue가 비어있으면 null 반환



Ch11 - 17. Stack과 Queue 예제

▶ stack

▷ stack에 0, 1, 2 push()
▷ stack이 비어있는 지 확인 후, pop()
public static void main(String[] args) {
  Stack st = new Stack();
  
  st.push("0");
  st.push("1");
  st.push("2");
  
  System.out.println("Stack pop");
  
  while (!st.empty()) {
    System.out.println(st.pop());
  }
}

// console
Stack pop
2
1
0


▶ Queue

▷ Queue에 0, 1, 2 offer()
▷ Queue가 비어있는 지 확인 후, poll()
public static void main(String[] args) {
    Queue q = new LinkedList();
    
    q.offer("0");
    q.offer("1");
    q.offer("2");
    
    System.out.println("Queue poll");
    
    while (!q.isEmpty()) {
        System.out.println(q.poll());
    }
}

// console
Queue poll
0
1
2



Ch11 - 18. 인터페이스를 구현한 클래스 찾기

▶ Queue 구현한 클래스를 찾아 사용

▷ Queue를 구현한 클래스들
All Known Implementing Classes

AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque,
ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue,
LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue

Queue g = new LinkedList();
g.offer("0");