Algorithm 문제를 풀다보면 Stack, Queue를 자주 접할 수 있다.
오늘은 간단하게 개념을 확인하고 Java에서 사용하는 방법을 정리해보겠다.

Stack, Queue란?

• Stack: 마지막에 저장한 데이터를 가장 먼저 꺼낸다. LIFO(Last In First Out)
• Queue: 먼저 들어간 데이터를 가정 먼저 꺼낸다. FIFO(First In First Out)

Stack

Stack<Integer> stack = new Stack<>();

stack.push(1);
stack.push(2);
stack.peek();	// 2를 return, stack = [1, 2]
stack.pop();	// 2를 return, stack = [1]

추가

• push(object item): Stack에 객체(item) 저장한다.

삭제

• peek(): Stack의 맨 위의 저장된 객체를 반환하고, 객체를 꺼내지 않는다.
  • Stack이 비어 있을 경우 EmptyStackException 발생시킨다.
• pop(): Stack의 맨 위에 저장된 객체를 반환하고, 객체를 꺼낸다.
  • Stack이 비어 있을 경우 EmptyStackException 발생시킨다.
• clear(): Stack의 전체 값을 제거한다. (초기화한다.)

기타

• isEmpty(): Stack이 비어있는지 boolean으로 반환한다.
• size(): Stack의 크기를 출력한다.
• contains(object item): Stack에 item이 있는지 확인한다.

Queue

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

queue.offer(1);
queue.offer(2);
queue.peek();	// 1을 return, queue = [1, 2]
queue.poll();	// 1을 return, queue = [2]

Queue에서는 구현체로 LinkedList를 사용한다.
혹시 ArrayList와 LinkedList가 떠오르는가? ArrayList는 순차적으로 데이터를 추가/삭제하는 경우, LinkedList는 중간 데이터를 추가/삭제하는 경우 유리하다.

Queue는 그림처럼 front와 rear가 존재한다. 만약 ArrayList를 사용한다면 데이터를 삭제한다(poll)면 첫번째 데이터를 꺼내오고, 동시에 모든 데이터가 공간을 채우기 위해 이동하는 데이터 복사가 발생하여 매우 비효율적이다. 이런 이유로 Queue는 ArrayList보다 데이터의 추가 삭제가 쉬운 LinkedList를 사용한다.

추가

• offer(object item): Queue에 객체(item)를 저장한다.
• add(object item): Queue에 객체(item)를 저장한다.
  • 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생시킨다.

삭제

• poll(): Queue 맨 위에 저장된 객체를 반환하고, 객체를 꺼낸다.
  • Queue가 비어 있을 경우 null 발생시킨다.
• remove(): Queue에 첫번재 값을 제거한다.

출력

• peek(): Queue의 맨 위의 저장된 객체를 반환하고, 객체를 꺼내지 않는다.
  • Queue가 비어 있을 경우 null 반환한다.

기타

• isEmpty(): Queue가 비어있는지 boolean으로 반환한다.

Reference

• https://ardor-dev.tistory.com/52
• https://devlog-wjdrbs96.tistory.com/246