51. Java Stack과 Queue

1. Stack

  1) LIFO 구조다.(Last In First Out)

  2) 마지막에 저장된 것을 제일 먼저 꺼내게 된다.

  3) 저장을 push, 빼는 것을 pop 이라고 한다.

  4) 배열로 구현하기 좋다.

 

2. Queue

  1) FIFO 구조다.(First In First Out)

  2) 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다.

  3) 저장을 offer, 빼는 것을 poll 이라고 한다.

  4) 링크드 리스트로 구현하기 좋다.

 

3. Stack 메서드

  1) Stack은 별도 클래스가 있다. 따라서 아래와 같이 선언 후 사용하면 된다.

     Stack stack = new Stack()

  2) Stack 메서드 종류는 아래와 같다.

    ① boolean empty() : Stack이 비어 있는지 알려준다.

    ② Object peek() : Stack의 맨 위에 저장된 객체를 반환한다. pop()과 달리 객체를 꺼내지 않는다.

    ③ Object pop() : Stack의 맨 위에 저장된 객체를 꺼낸다. 데이터가 없다면 EmptyStackException이 발생한다.

    ④ Object push(Object item) : Stack에 객체(item)를 저장한다.

    ⑤ int research(Object  o) : Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환한다. 못 찾으면 -1을 반환하며, 배열과 달리 0이 아닌 1부터 시작한다.

 

4. Queue 메서드

  1) Queue는 인터페이스로 구성되어 있다.

  2) Queue 메서드는 다음과 같다. 

    ① boolean add() : 지정된 객체를 Queue에 추가한다. 성공하면 true를 반환하며, 실패하면 false를 반환한다. 저장공간이 부족하면 illegalStateException이 발생한다.

    ② Object remove() : Queue에서 객체를 꺼내 반환한다. 비어있으면 NoSuchElementException이 발생한다.

    ③ Object element() : 삭제없이 요소를 읽어온다. peek와 달리 Queue가 비었을 때 NoSuchElementException이 발생한다.

    ④ boolean offer(Object item) : Queue에 객체(item)를 저장한다. 성공하면 true, 실패하면 false를 반환한다.

    ⑤ Object poll() : Queue에서 객체를 꺼내서 반환한다. 비어있으면 null을 반환한다.

    ⑥ Object peek() : Queue에 저장된 제일 첫 번째 객체를 읽어온다. 삭제하지 않는다. Queue가 비어 있으면 null을 반환한다.

    

5. Queue 사용하기

  1) Queue를 직접 구현한다.

  2) Queue를 구현한 클래스를 사용한다.

    ① Java api에서 Queue를 찾으면 Queue를 구현한 클래스를 쓰면 된다.(LinkedList가 Queue를 구현한 클래스다.)

    ② Queue q = new LinkedList(); 와 같은 방식으로 사용하면 된다.

 

6. Stack과 Queue 활용

  1) Stack 활용 : 수식계산, 수식괄호검사, 웹브라우저의 뒤로/앞으로 등

    ① 수식괄호검사 : 문자열의 길이만큼 반복하고, 각 문자가 수식인지 확인한다. 만약 '(' 는 push하고 ')'는 pop해서 마지막에 stack이 비어 있는지 확인한다.

  2) Queue 활용 : 최근 사용문서, 인쇄작업 대기목록, 버퍼 등

    ② 최근 사용 문서 : Queue에 가장 처음 들어간 최근 사용문서 이름을 넣는다. 순차적으로 넣은 후, 일정 개수 이상이 되면 제일 처음 들어간 문서 이름을 poll 한다.