스택(Stack)과 큐(Queue)

스택 ?

• [ ] 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In Fisrt Out) 형식의 자료구조이다.

스택 관련 메서드 - Java

• Object push(Object item): 객체(item) 하나를 Stack의 가장 위에 추가한다.
• Object pop(): 스택에서 가장 위에 저장된 객체를 반환하고 삭제한다.
• Object peek(): 스택의 가장 위에 있는 객체를 반환한다.
• boolean empty(): 스택이 비어있으면 true를 반환한다.
• int search(): 인자로 받은 값을 스택에서 검색하여 해당 위치를 반환한다. ( 찾는 값이 스택에 없을 경우엔 -1을 반환 ! )

스택을 사용하면 좋은 경우 ?

• 짝꿍(Pair)의 개념으로 자신의 짝을 찾는 문제일 때 ! ( ex: 이웃한 값이 충돌해서 사라지는 경우 )
• 입력값에 괄호()가 있는 문제일 때 !

• [ ] 사실 Java에서 이제 Stack은 레거시 코드이기 때문에, Deque 인터페이스를 구현한 클래스(ArrayDeque 등)를 스택 용도로 사용할 것을 권장하고 있다 ! → ArrayDeque는 비동기적으로 동작해서 더 빠른 성능을 보인다. ( 멀티코어에선 Stack처럼 동기적으로 동작하는 것은 사실상 이점이 없다. )

큐 ?

• [ ] 한 쪽 끝에서 자료가 삽입되고, 반대쪽 끝에서 자료가 삭제되는 FIFO(First In First Out) 형식의 자료구조이다.

큐을 사용하면 좋은 경우 ?

• 너비우선탐색(BFS)에 많이 사용된다 !
• 자료가 원형(순환) 구조를 이루 때 !

• [ ] 자바에선 큐(Queue)를 인터페이스로만 정의해놓고 스택처럼 별도의 클래스를 제공하지 않는다. → 대신 이를 구현한 여러 클래스들이 있는데 그 중에 하나가 삽입/삭제가 쉬운 LinkedList 클래스이다.

Queue<Integer> queue = new LinkedList<>();

• [ ] 큐의 연산엔 다음과 같은 것들이 있다.

큐 관련 메서드 - Java

• boolean offer(Object o): 큐에 데이터를 삽입하고, 성공하면 true, 실패하면 false를 반환한다.
  • boolean add(Object o): 같은 기능이지만, 저장공간이 부족하면 예외(IllegalStateException)를 던진다.
• Object poll(): 큐에서 가장 앞에 있는 객체를 꺼내서 반환하고 삭제한다.
  • Object remove(): 같은 기능이지만, 예외(NoSuchElementException)를 던진다.
• E peek(): 큐의 가장 앞에 있는 **데이터(첫 번째 데이터)**를 반환하지만, 큐에서 삭제하지는 않는다. ( 큐가 비어있으면 null을 반환한다. )

큐를 순회하는 방법

Iterator<Integer> it = queue.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}