자바의 정석 - Stack과 Queue

스택과 큐

• 스택(Stack)
  • LIFO(Last In First Out)구조, 마지막에 저장된 것을 제일 먼저 꺼냄
  • 밑이 막힌 구조
  • 저장(push), 추출(pop)
  • 배열이 유리
    -> 배열은 순차적으로 추가하고 순차적으로 삭제하기 때문에
• 큐(Queue)
  • FIFO(First In First Out)구조, 제일 먼저 저장한 것을 제일 먼저 꺼냄
  • 밑이 뚫린 구조
  • 저장(offer), 추출(poll)
  • 링크드 리스트가 유리
    -> 배열로 하게된다면 0-1-2-3에서 0을 삭제했을 때 1-2-3이 앞으로 당겨지기 때문에 비효율적
    but 링크드 리스트는 0-1-2-3에서 0을 삭제해도 자리이동을 하지않고 연결만 바꿔주기 때문에 효율적

---

스택과 큐(Stack & Queue)의 메서드

• 스택
  • 객체 생성 가능, Stack st = new Stack();
  • boolean empty() - 스택이 비어있는지
  • Object peek() - Stack 맨 위에 저장된 객체 반환 (꺼내진 않음)
  • Object pop() - Stack 맨 위에 저장된 객체를 꺼냄
  • Object push(Object item) - Stack에 객체를 저장
  • int search(Object o) - Stack에서 주어진 객체 찾아서 위치 반환 (못찾으면 -1 반환)
• 큐
  • 인터페이스라서 객체 생성 불가능
  • boolean offer(Object o) - Queue에 객체를 저장
  • Object poll() - Queue에 객체를 꺼내서 반환. 비었으면 null 반환(삭제)
  • Object peek() - 삭제없이 요소를 읽어옴

---

큐 - interface를 구현한 클래스 찾기

• 큐는 interface라서 객체 생성이 불가능하지만 2가지 방법을 통해 객체 생성 가능
  • 큐를 직접 구현
  • 큐를 구현한 클래스를 사용
    -> LinkedList가 한 예시

Queue q = new LinkedList();
q.offer();

---

예제

class Ex1 {
	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()); // 큐에서 요소 하나를 꺼내서 반환
		}
	}
}