ch 11-15~18 Stack과 Queue

스택과 큐(Stack & Queue)

• Stack = LIFO(Last In First Out)구조. 저장된 것을 제일 먼저 꺼내게 된다. / 밑이 막힌 상자 (맨 아래 = 처음 저장한 값 / 맨 위 = 마지막에 저장한 값) / 넣는 순서는 아래에서 위지만, 꺼내는 순서는 위에서 아래다.
  
• Queue = FIFO(Fisrt In First Out)구조. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다. / 양끝이 뚫린 상자 (맨 아래 = 처음 저장한 값 / 맨 위 = 마지막에 저장한 값) / 넣는 순서와 꺼내는 순서 모두 아래에서 위다.
• Stack을 만들기 위해서는 순차적으로 추가하고 순차적으로 삭제하는 배열을 사용하는 것이 더 효율적이다.
• Queue를 만들기 위해서는 자리이동이 필요없는 링크드리스트를 사용하는 것이 더 효율적이다.

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

스택의 메서드

• Stack st = new Stack()을 통해 사용한다.
• peek() : 맨 위에 저장된 객체가 무엇인지 조회하는 것
• pop() : 삭제
• push() : 추가
• search() : stack에서 주어진 객체의 위치를 반환 (못 찾으면 -1 반환 / 배열은 0부터 시작하지만 search는 1부터 시작)

큐의 메서드

• offer() : 추가 (예외 발생 x)
• poll() : 삭제 (예외 발생 x)
• remove() : 삭제 (예외 발생)
• add() : 추가 (예외 발생)
• peek() : 요소를 읽어 온다. (Queue가 비어 있으면 null 반환)
• Queue는 인터페이스로 정의되어 있으므로 Queue = new Queue는 불가 (인터페이스라 객체 생성x)

인터페이스를 구현한 클래스 찾기

• 1.Queue를 직접 구현 2.Queue를 구현한 클래스를 사용한다.
• All Known Implementing Classes : Queue를 구현한 클래스 목록
• 그 중 LinkedList가 있으므로 그를 활용한다.

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

• 참조변수를 LinkedList를 사용할 수 있다. (Queue를 썼다는 것은 LinkedList와 ArrayDeque의 공통분모를 사용했다는 것이다.)

ch 11-19~21 Stack과 Queue의 활용

스택과 큐(Stack & Queue)의 활용

• 스택의 활용 예 : 수식계산, 수식괄호검사, 워드포르세서의 undo/redo, 웹브라우저의 뒤로/아픙로
• 큐의 활용 예 : 최근사용문서, 인쇄작업 대기목록, 버퍼(buffer)