스택(Stack), 큐(Queue)

스택

스택은 가장 나중에 들어간 원소가 가장 먼저 나오는 구조이다. (LIFO)

사용 사례

• 스택 메모리
  • 예를 들어 StackOverFlowError는 스택 메모리 공간을 다 썼을 때 발생하는 에러로, 주로 재귀 함수에서 탈출하지 못하면 발생한다.

자바에서의 스택 구현

• 자바는 Stack 클래스를 제공한다. Stack 클래스 외에도 LinkedList와 ArrayList를 통해 구현할 수 있다.
• 데이터 조회: Top에 있는 원소를 조회할 때는 O(1)의 시간 복잡도를 갖는다. 하지만 Top이 아닌 원소를 조회할 때는 해당 데이터를 찾을 때까지 수행해야 하므로 O(N)의 시간 복잡도를 갖는다.
• 데이터 삽입: LinkedList를 통한 구현에서는, 단순히 새로운 원소가 Top에 있는 원소를 가리키도록 참조를 변경하고 head가 새로운 원소를 가리키면 된다. 따라서 O(1)의 시간 복잡도를 갖는다. ArrayList를 통한 구현에서도, 배열의 크기가 부족하여 새로운 배열을 생성하고 데이터를 복사하는 상황이 아니라면 O(1)의 시간 복잡도를 갖는다.
• 데이터 삭제: 가장 끝 원소를 삭제하면 되므로 O(1)의 시간 복잡도를 갖는다.

큐

큐는 가장 먼저 들어간 원소가 가장 먼저 나오는 구조이다. (FIFO)

사용 사례

• producer/consumer architecture
  • 예를 들어 OutOfMemoryError는 힙 메모리를 다 썼을 때 발생하는 에러로, 내부적으로 큐를 사용했는데 데이터가 계속 쌓이기만 할 경우 이 에러가 발생할 수 있다.

자바에서의 큐 규현

• 자바에서는 Queue 인터페이스를 제공한다. Queue는 인터페이스이므로 주로 LinkedList를 통해 구현한다.
• 데이터 조회: 가장 끝에 있는 원소를 조회할 때는 O(1)의 시간 복잡도를 갖는다. 하지만 가장 끝에 있는 원소가 아닌 특정 데이터를 찾고자 할 때는 해당 데이터를 찾을 때까지 수행해야 하므로 O(N)의 시간 복잡도를 갖는다.
• 데이터 삽입: O(1)의 시간 복잡도를 갖는다.
• 데이터 삭제 : O(1)의 시간 복잡도를 갖는다.