[자료구조] Stack와 Queue 정리 (Java)

Stack 이란?

자료 구조 중 하나인 Stack의 사전적 정의는 '쌓다', '더미'이다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있다. Stack은 마지막에 저장한 데이터를 가장 먼제 꺼내게 되는 LIFO(Last In First Out)구조로 되어있다. 

 

 

LIFO (Stack)

 

 

 

 

Stack 사용법

순차적으로 데이터를 추가하고 삭제하는 Stack에는 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합하다. Stack은 다음과 같이 사용하면 된다.

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

// 데이터 삽입
stack.push(1);
stack.push(2);
stack.push(3);

// 데이터 출력
stack.peek(); // 3 출력 (맨 위의 값 출력)

// 데이터 삭제
stack.pop(); // 3 제거
stack.pop(); // 2 제거
stack.pop(); // 1 제거
stack.clear(); // 모든 데이터 제거

 

Queue 란?

Queue의 사전적 의미는 무엇을 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미한다. 이처럼 줄을 지어 순서대로 처리되는 것이 Queue라는 자료구조이다. Queue는 데이터를 일시적으로 쌓아두기 위한 자료구조로 Stack과는 다르게 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)구조로 되어 있다.

FIFO (Queue)

 

 

Queue 사용법

Queue는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로, ArrayList와 같은 배열기반의 컬렉션 클래스를 사용한다면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효울적이다. 그래스 Queue는 ArrayList보다 추가/삭제가 쉬운 LinkedList로 구현하는 것이 적합하다.

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

// 데이터 삽입
q.offer(1);
q.offer(2);
q.offer(3);

// 데이터 출력& 삭제
q.peek(); // 1 출력 (맨 위의 값 출력)
q.poll(); // 1 출력 후 삭제

// 데이터 삭제
q.remove(); // 2 삭제
q.clear(); // 모든 데이터 삭제

 

Stack과 Queue 비교

	설명	특징	사용
Stack	순서가 있는 데이터의 집합	LIFO / 삽입과 삭제를 리스트의 한쪽(top)에서만 함	깊이우선탐색 DFS / 재귀적 함수 호출할 때 사용 / 인터럽트 처리, 수식계산, 서브루틴의 복귀 번지 저장 등에 사용
Queue	순서가 있는 데이터의 집합	FIFO / 삽입은 리스트의 한쪽(rear)에서 하고 삭제는 삽입의 반대쪽(front)에서 함	너비우선탐색 BFS / 컴퓨터 버퍼에 주로 사용 (많은 데이터가 한 번에 입력되고 처리하지 못할 때 버퍼(queue)로 처리함)

 

---

Java로 Stack구현하기 예제보러가기

 

---

✺ 참고

자바의 정석 3rd Edition