스택

젠가를 떠올려보자. 젠가 케이스에 젠가를 정리해서 넣었다면 꺼내려고 할 때 위에서부터 하나씩 꺼내야 할 것이다.

이처럼 데이터를 넣는 곳과 빠지는 곳의 위치가 같은 자료구조를 스택이라고 한다. 이런 구조를 후입선출 구조 (LIFO; Last In First Out)라고 한다.

스택이 비어있을 때 데이터를 꺼내려고 시도하면 스택 언더플로우(Stack Underflow)가 발생하고, 스택이 꽉 차있을 때 자료를 넣으려고 하면 스택 오버플로우(Stack Overflow)가 발생한다.

자바에서는 크게 5가지 메서드를 사용한다

push(x), add(x) : x를 스택의 맨 위에 쌓는다.
- push() 메서드는 자바의 스택 클래스에서 제공하며 추가한 객체를 리턴한다. add() 는 List 클래스에서 제공하며 성공여부 (boolean)을 리턴한다. 스택을 사용할 때는 push를 사용하는 것을 권장한다!
size() : 스택에 쌓인 블럭의 개수를 반환한다.
isEmpty() : 스택이 비어있다면 true, 비어있지 않다면 false를 반환한다.
peek() : 스택의 맨 위에 있는 데이터를 반환한다.
pop() : 스택의 맨 위에 있는 데이터를 반환함과 동시에 스택에서 꺼낸다.

대부분의 연산들은 TOP 영역에서 진행되기 때문에 시간복잡도가 O(1)이 된다. 하지만 serach() 메서드는 특정 데이터를 찾을 때까지 수행하므로 O(n)의 시간복잡도를 갖는다.

큐

편의점 음료수 진열대를 생각해 보자. 점원이 음료수를 냉장고 뒤에서 넣은 걸 우리는 제일 앞에서부터 구매하게 된다.

스택 자료구조와는 다르게 먼저 들어온 데이터가 가장 먼저 나가는 구조이다. 이런 구조를 선입선출 (FIFO; First In First Out) 구조라고 한다. 큐 자료구조는 이 선입선출 구조를 따르고 있다.

자바에서 자주 사용하는 메서드들이다.

offer(x), add(x) : 큐에 값을 넣는다.
- 큐 용량 초과 등의 이유로 값을 넣지 못했을 때, add() 메서드는 예외를 발생시키고 offer() 메서드는 false를 리턴한다.
size() : 큐에 들어있는 데이터의 개수를 반환한다.
isEmpty() : 큐에 데이터가 있다면 false, 없다면 true를 반환한다.
peek() : 큐의 맨 앞에 있는 데이터를 반환한다.
poll() : 큐의 맨 앞에 있는 데이터를 반환함과 동시에 큐에서 삭제한다.

자바에서 큐는 보통 ArrayDeque와 LinkedList로 구현하게 되는데 각각 배열의 특성, List의 특성을 가진다.

큐 자료구조 특성 상, 삽입과 삭제는 양 끝단에서만 일어난다. 중간에서 삽입되거나 삭제되는 경우가 없기 때문에 ArrayDeque가 배열의 특성을 가져도 시간복잡도 O(1)으로 리스트와 별 차이가 없게 된다.

또한 다음 노드에 대한 참조를 유지할 필요가 없기 때문에 더 적은 메모리를 사용한다! 알고리즘 문제풀이에 큐를 쓰면 LinkedList로 구현했었는데 ArrayDeque를 사용해야겠다..