JAVA 스택 & 큐

김민혁·2021년 5월 19일

스택 자료구조 큐

자료구조

목록 보기

2/3

Stack

입구와 출구가 같은 곳에 데이터를 차곡차곡 쌓아 올리듯 저장하는 자료구조
마지막에 넣은 데이터가 가장 먼저 나오는 LIFO(Last In First Out) 구조

최근에 삽입한 데이터를 가장 먼저 확인할 수 있기 때문에 인터넷 브라우저의 이전 페이지, 다음 페이지와 유사한 기능을 구현할 때 사용할 수 있다
배열과 리스트를 이용해 구현할 수 있다
스택에서의 데이터 삽입/삭제는 가장 마지막 위치에서 일어나기 때문에 O(1)에 가능하다

단, 배열로 구현했을 경우 배열의 사이즈 문제로 시간이 더 소요될 수 있음

Stack의 연산

push

스택에 데이터를 삽입하는 연산
pop

가장 최근에 삽입한 데이터를 꺼내는 연산
peek

가장 최근에 삽입한 데이터를 확인하는 연산

→ pop와 달리 데이터를 꺼내지 않음
isEmpty

스택이 비어있는지 확인하는 연산

JAVA에서 Stack 사용 방법

JAVA에서는 기본적으로 3가지 방법을 이용해 Stack을 사용할 수 있음

Stack 클래스

Stack<T> stack = new Stack<>();
stack.push(데이터); // 데이터 삽입
stack.pop();      // 최근에 삽입한 데이터 추출
stack.peek();     // 최근에 삽입한 데이터 확인
stack.isEmpty();  // 스택이 비었는지 확인

Stack 클래스의 경우 Vector클래스를 상속해 push, pop, peek의 연산에 synchronized 키워드가 적용되어 있음

→ 멀티 쓰레드를 사용하는 경우가 아니라면 성능 저하가 발생할 수 있음

LinkedList 클래스

LinkedList<T> stack = new LinkedList<>();
stack.push(데이터); // 데이터 삽입
stack.pop();      // 최근에 삽입한 데이터 추출
stack.peek();     // 최근에 삽입한 데이터 확인
stack.isEmpty();  // 스택이 비었는지 확인

LinkedList 클래스에 스택에서 사용되는 연산들이 구현되어 있어 사용하면 됨

다만, 스택처럼 사용할 수 있을 뿐이지 기본적으로 리스트이기 때문에 중간에 데이터를 삽입하거나 삭제할 수 있다

Deque 인터페이스 구현체 사용

Deque<T> stack = new ArrayDeque<>();
stack.push(데이터); // 데이터 삽입
stack.pop();      // 최근에 삽입한 데이터 추출
stack.peek();     // 최근에 삽입한 데이터 확인
stack.isEmpty();  // 스택이 비었는지 확인

Deque 인터페이스를 구현한 구현체(ArrayDeque, LinkedBlockingDeque, ...)를 사용하면 됨

정리

데이터 탐색 : O(1)

가장 마지막에 넣은 데이터를 확인하면 되므로 상수시간에 가능함
데이터 삽입 : O(1)

배열로 구현된 경우 배열 사이즈 문제로 시간이 더 소요될 수 있음
데이터 삭제 : O(1)

Queue

스택과 달리 입구와 출구가 따로 있는, 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조

일상에서 '줄을 선다' 라고 생각하는 대부분을 Queue 구조로 생각하면 된다
- 놀이공원 대기열
- 은행 대기열
리스트를 이용해 구현한 경우 데이터의 삽입/삭제는 맨 앞과 맨 뒤 노드의 연결을 추가하거나 끊으면 되기 때문에 O(1)으로 가능하다

Queue의 연산

offer

큐에 데이터를 삽입하는 연산
poll

큐의 맨 앞에 있는 데이터를 꺼내는 연산
peek

큐의 맨 앞에 있는 데이터를 확인하는 연산
isEmpty

큐가 비어있는지 확인하는 연산

JAVA에서 Queue 사용 방법

LinkedList를 이용해 Queue를 사용할 수 있다

Queue<T> queue = new LinkedList<>();
queue.offer(데이터); // 큐 끝에 데이터 삽입
queue.poll();      // 큐 맨 앞의 데이터 꺼냄
queue.peek();      // 큐 맨 앞의 데이터 확인
queue.isEmpty();   // 큐가 비어있는지 확인