자바에서의 스택과 큐

이번 주 스터디에서는 자료구조 중 스택과 큐에 대해 공부하고 문제를 풀어보는 시간을 가졌습니다.

전에도 스택과 큐에 대해서 공부해봤기 때문에 구조적인 측면에서 이해는 문제가 없었습니다.

하지만 파이썬으로 구현했던 거라 자바로 구현하려고 하니 '어떤 클래스를 사용하고 어떤 메서드를 사용하지?'라는 생각이 들었습니다.

그래서 이걸 간단히 정리해 보려고 합니다.

스택과 큐의 자료구조와 메서드에 대해 정리하겠습니다.

 

스택(Stack)

스택은 LIFO(Last In First Out)의 특징을 가지고 있습니다.

이건 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질을 말합니다.

다르게 표현하면 가장 먼저 들어간 데이터가 가장 마지막으로 나오는 것을 뜻하기도 합니다.

 

재귀적인 함수, 알고리즘에 사용됩니다.

데이터를 삽입 및 삭제에 O(1), 탐색에 O(n) 시간이 걸립니다.

 

자바에서는 Stack 클래스를 구현하여 제공합니다.

Stack 클래스 메서드는 아래와 같습니다.

메서드	내용
boolean empty()	스택이 비어있는지 알려줍니다.
Object peek()	스택의 맨 위에 저장된 객체를 반환합니다. 객체를 꺼내지는 않습니다. 비어있을 때 사용할 경우 예외 오류를 발생시킵니다.
Object pop()	스택 맨 위의 저장된 객체를 꺼냅니다. 비었을 때 사용할 경우 오류를 발생시킵니다.
Object push(Object o)	스탬 맨 위에 o를 저장합니다.
int search(Object o)	스택에서 주어진 객체 o를 찾아서 그 위치를 반환합니다. 못찾으면 -1을 반환합니다. 배열과 달리 위치는 1부터 시작합니다.

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

 

큐(Queue)

큐는 FIFO(First In First Out)의 특성을 가지고 있습니다.

이는 먼저 집어넣은 데이터가 먼저 나오는 성질을 말합니다.

때문에 데이터를 집어넣으면 뒤부터 순차적으로 생성되고 

뺄 때는 가장 처음 데이터부터 나오게 됩니다.

 

삽입 및 삭제에 O(1), 탐색에 O(n)의 시간이 걸립니다.

CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬

너비 우선 탐색(BFS), 캐시 등에 사용됩니다.

 

자바에서 큐의 경우에는 클래스가 아닌 인터페이스를 제공합니다.

물론 구현해 놓은 클래스도 있기 때문에 그중 하나를 사용하면 됩니다.

예시로 ArrayDeque, ConcurrentLinkedDeque, LinkedList가 있습니다.

Deque의 경우에는 앞뒤로 데이터를 넣고 빼는 메서드를 가지고 있습니다.

 

메서드는 아래와 같습니다.

메서드	내용
boolean add(Object o)	지정된 객체를 큐에 삽입합니다. 성공하면 true를 반환합니다. 실패하면 오류를 반환합니다.
Object remove()	큐에서 객체를 꺼내 반환합니다. 비어있을 경우 오류를 발생시킵니다.
Object element()	삭제없이 요소를 읽어옵니다. 비어있을 경우 오류를 발생시킵니다.
boolean offer(Object o)	큐에 객체를 저장합니다. 성공하면 true를 반환합니다.
Object poll()	큐에서 객체를 꺼내서 반환합니다. 비어있으면 null을 반환합니다.
Object peek()	삭제없이 요소를 읽어옵니다. 큐가 비어 있으면 null을 반환합니다.

위 세 개와 아래 세 개의 메서드는 같은 기능을 하지만 오류를 반환하고 하지 않는 차이가 있습니다.

Queue<Integer> q = new LinkedList<Integer>()