Stack & Queue

• 스택 : LIFO 구조, 마지막에 저장된 것을 제일 먼저 꺼내게 된다.
  (Last In First Out), 밑이 막힌 상자

push : 저장
pop : 추출

스택을 구현하려면 배열, 링크드 리스트 모두 사용 가능하나
배열이 가장 효율적이다.
배열은 순차적 추가 삭제를 하기 때문

• 큐(Queue) : FIFO 구조, 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다.
  (First In First Out), 줄서기
  

offer : 저장
poll : 추출

큐를 구현할 때는 배열, 링크드 리스트 중 링크드 리스트가 가장 효율적이다
저장은 순차적으로, 삭제는 자리이동 없이 가능하기 때문이다.

스택은 class, 큐는 interface를 가지고 있다.

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

• Queue (인터페이스로 구성 되어있다)
  boolean add(Object o) : 지정된 객체를 Queue에 추가한다. 성공하면 true를 반환,
  저장공간이 부족하면 IllegalStateException 발생
  Object remove() : Queue에서 객체를 꺼내 반환, 비어 있으면 NoSuchElementException발생
  Object element() : 삭제없이 요소를 읽어온다. peek과 달리 Queue가 비었을 때 NoSuchElementExeption 발생
  boolean offer(Object o) : Queue에 객체를 저장, 성공하면 true, 실패하면 false를 반환
  Object poll() : Queue에서 객체를 꺼내서 반환, 비어있으면 null을 반환
  Object peek() : 삭제없이 요소를 읽어 온다. Queue가 비어있으면 null을 반환

Queue는 인터페이스로 구성되어있기 때문에 사용방법은
1. Queue를 직접구현
2. Queue를 구현한 클래스를 사용